Pages: [1]   Go Down
Author Topic: Simple prime number printer  (Read 1649 times)
0 Members and 1 Guest are viewing this topic.
Offline Offline
Jr. Member
**
Karma: 0
Posts: 57
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Since I don't have any hardware yet, I decided to do programming instead.  I created a simple program that echoes a prime number every second, unless it took longer than a second to calculate it. (It would take an EXTREMELY long time to get that far.)  The delay is editable.  The program is 2548 bytes when compiled. It uses what is probably a well known algorithm to find prime numbers. (I just made it up, I'm sure this method already exists)  I know it's not much, but it's the first thing I've ever done on an Arduino besides making a light blink, so I'm happy with it! smiley-grin
Code:
int count = 2; //Start at 2- 1 doesn't count
int printDelay = 1000; //Minimum prime number delay

void setup() {
  Serial.begin(9600);
  Serial.println("Starting...");
}

void loop() {
  unsigned long start = millis();
  if(isPrime(count)) {
    Serial.println(count);
   
    if(millis() - start < printDelay) {
      delay(abs(printDelay - (millis() - start)));
    }
  }
  count++;
}

boolean isPrime(int x) {
  boolean prime = true;
 
  for(int i = 2; i <= x/2; i++) { //Loop every number up to half
    if(x % i == 0) { //If it's divisible...
      prime = false; //It isn't prime!
      break;
    }
  }
 
  return prime;
}

This program could be edited to be a benchmark-type program for Arduinos.
Logged

Australia
Offline Offline
Full Member
***
Karma: 7
Posts: 209
AVR Microcontrollers
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Neat little program.

You are on your way to much fun with arduino.

Prime numbers are great check out:

http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm
Logged

0
Offline Offline
God Member
*****
Karma: 2
Posts: 854
Arduino rocks!
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Cute little project.  Primes are a lot of fun to play with.

When you count through your for loop, you don't need to compare any even numbers (after 2), so you can increment by 2 which should double your program's speed.

If a number is not prime, it will have factors that are prime, so if you want to get a lot more advanced and a lot faster, you can keep a table of all the primes you've already computed and iterate through those instead of testing every odd number every time.  That gets into a programming technique called "dynamic programming".
Logged

Global Moderator
Netherlands
Offline Offline
Shannon Member
*****
Karma: 170
Posts: 12482
In theory there is no difference between theory and practice, however in practice there are many...
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset


Another optimization you only have to test until sqrt(x) +1, 

number bigger than sqrt(x) can't be a divider of x unless there is a number smaller than sqrt(x) that is a divider. // the +1 is to handle rounding errors

if (count % 2 ==0) return false;
for(int i = 3; i <= sqrt(x)+1; i+=2) 

More prime optimizations see my remarks - http://arduino.cc/forum/index.php/topic,63071 -
Logged

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

0
Offline Offline
Faraday Member
**
Karma: 19
Posts: 3420
20 LEDs are enough
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

I would not computer sqrt at all. Instead I would only check till i*i > x. This can be computed without any multiplications because:

(n+1)*(n+1) = n*n+2*n+1, thus

n_0 := 0,
n_(i+1) := n_i+2*i+1 = n+i+i+1

Hence successive square numbers can be computed by addition.

Logged

Check out my experiments http://blog.blinkenlight.net

Global Moderator
Netherlands
Offline Offline
Shannon Member
*****
Karma: 170
Posts: 12482
In theory there is no difference between theory and practice, however in practice there are many...
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

good point Udo!
Logged

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

0
Offline Offline
Faraday Member
**
Karma: 19
Posts: 3420
20 LEDs are enough
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

This is an "old school" assembler code trick smiley-wink
Logged

Check out my experiments http://blog.blinkenlight.net

0
Offline Offline
Faraday Member
**
Karma: 19
Posts: 3420
20 LEDs are enough
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Oops forgot to mention: the recursion is an inhomogenous recurrence equation. Thus the mathmaticians knew this way before this newfangled computer stuff was invented smiley-wink
Logged

Check out my experiments http://blog.blinkenlight.net

Global Moderator
Netherlands
Offline Offline
Shannon Member
*****
Karma: 170
Posts: 12482
In theory there is no difference between theory and practice, however in practice there are many...
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Many math that is invented/discovered has no direct purpose, and someday someone find a use for it. Sometimes that takes decades.

In the Scientific American August 2011 p60++ an interesting article about "Why Math Works", subtitle "is math invented or discovered?" discusses some nice cases.

Logged

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

0
Offline Offline
Faraday Member
**
Karma: 19
Posts: 3420
20 LEDs are enough
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Decades??? Pfft. Think about number theory --> centuries to applications. Millenia to resolution (e.g. transcendence of pi). Others still open probably for a long time to come (Riemann's hypothesis).
Still a lot of stuff to discover or to invent.

I think at the cutting edge it is invention. Once a theory gets hardened discovery follows. What was the point of the article?
« Last Edit: August 15, 2011, 12:45:06 pm by Udo Klein » Logged

Check out my experiments http://blog.blinkenlight.net

Global Moderator
Netherlands
Offline Offline
Shannon Member
*****
Karma: 170
Posts: 12482
In theory there is no difference between theory and practice, however in practice there are many...
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset


It is a mixture of invention and discovery. Concepts are invented, and then the underlying relations are discovered. They follow from the concept. (e.g. complex number theory, the concept is sqrt(-1) == i  and we display it in a plane iso line .

Another question the author asks is what gives mathematics its explanatory and predictive powers? But there is no definitive answer to that one.

Start of the article - http://www.scientificamerican.com/article.cfm?id=why-math-works -
Logged

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

0
Offline Offline
Sr. Member
****
Karma: 1
Posts: 360
I'm 15. I like making things. I like breaking things better.
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

I read that article too -- and thought of it in this thread. A great article that really makes you think.

Basically, it said that the ability of math to predict and explain things (that sometimes havent even been discovered yet) means that it must be natural. What we create is the language used to express it, but not its fundamental concepts.
Logged

Alice asked the Chesire Cat, who was sitting in a tree, "What road do I take?"
The cat asked, "Where do you want to go?"
"I don't know," Ali

0
Offline Offline
Faraday Member
**
Karma: 19
Posts: 3420
20 LEDs are enough
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Interestingly the article cites Einstein but does mention that he also pondered:

Quote
Insofern sich die Sätze der Mathematik auf die Wirklichkeit beziehen, sind sie nicht sicher, und insofern sie sicher sind, beziehen sie sich nicht auf die Wirklichkeit.

Which is usually translated as

Quote
"As far as the laws of mathematics refer to reality, they are not certain, as far as they are certain, they do not refer to reality."

The power of mathmatics is indeed enormous. However if it fails this is usually not attributed to mathmatics but to model flaws. Thus the predictive power is somehow tautological.
Logged

Check out my experiments http://blog.blinkenlight.net

Pages: [1]   Go Up
Jump to: