| Posted by
| Nick Gammon
Australia (23,120 posts) Bio
Forum Administrator |
| Message
| I got inspired after watching the guys on Numberphile unbox a gadget that displays prime numbers:
http://www.youtube.com/watch?v=8UqCyepX3AI
I made a quick version that did a similar thing with an 8-digit LED display:
Totally useless of course, but strangely mesmerizing to watch.
Hardware: Arduino Uno, plus one of these 8-digit display boards from eBay for about $10.
References:
http://en.wikipedia.org/wiki/Primality_test
http://primes.utm.edu/
Code:
// Prime number generator
//
// Author: Nick Gammon
// Date: 8th October 2013
#include <SPI.h>
const int SHOW_EVERY = 500; // how often to echo a prime to the serial port
const unsigned long TIME_TO_WAIT = 500; // mS
// MAX7219 registers
const byte MAX7219_REG_NOOP = 0x0;
// codes 1 to 8 are digit positions 1 to 8
const byte MAX7219_REG_DECODEMODE = 0x9;
const byte MAX7219_REG_INTENSITY = 0xA;
const byte MAX7219_REG_SCANLIMIT = 0xB;
const byte MAX7219_REG_SHUTDOWN = 0xC;
const byte MAX7219_REG_DISPLAYTEST = 0xF;
// 7-segments patterns for digits 0 to 9
const byte digits [10] = {
0b1111110, // 0
0b0110000, // 1
0b1101101, // 2
0b1111001, // 3
0b0110011, // 4
0b1011011, // 5
0b1011111, // 6
0b1110000, // 7
0b1111111, // 8
0b1111011, // 9
};
// send one byte via SPI to MAX7219
void sendByte (const byte reg, const byte data)
{
digitalWrite (SS, LOW);
SPI.transfer (reg);
SPI.transfer (data);
digitalWrite (SS, HIGH);
} // end of sendByte
// send one character (data) to position (pos) with or without decimal place
// pos is 0 to 7
// data can be '0' to '9' plus various other things as below
void sendChar (const byte pos, const char data, const bool dp = false)
{
byte converted;
switch (data)
{
case '0' ... '9' : converted = digits [data - '0']; break;
case '-': converted = 0b0000001; break;
case 'A': converted = 0b1110111; break;
case 'b': converted = 0b0011111; break;
case 'c': converted = 0b0001101; break;
case 'C': converted = 0b1001111; break;
case 'd': converted = 0b0111101; break;
case 'E': converted = 0b1001111; break;
case 'F': converted = 0b1000111; break;
case 'h': converted = 0b0010111; break;
case 'H': converted = 0b0110111; break;
case 'L': converted = 0b0001110; break;
case 'o': converted = 0b0011101; break;
case 'P': converted = 0b1100111; break;
case 'r': converted = 0b0000101; break;
case 'S': converted = 0b1011011; break;
case 't': converted = 0b0000111; break;
case 'u': converted = 0b0011100; break;
case ' ': converted = 0b0000000; break;
case 'I': converted = digits [1]; break;
default: converted = 0b0000001; break; // -
} // end of switch
if (dp)
converted |= 0b10000000;
sendByte (8 - pos, converted);
} // end of sendChar
// write an entire null-terminated string to the LEDs
void sendString (const char * s)
{
byte pos;
for (pos = 0; pos < 8 && *s; pos++)
{
boolean dp = s [1] == '.';
sendChar (pos, *s++, dp); // turn decimal place on if next char is a dot
if (dp) // skip dot
s++;
}
// space out rest
while (pos < 8)
sendChar (pos++, ' ');
} // end of sendString
long candidate;
long found = 5; // Number we found
int count = found - 1;
void setup() {
Serial.begin(115200);
while (!Serial) { }
Serial.println ();
Serial.println ();
SPI.begin ();
sendByte (MAX7219_REG_SCANLIMIT, 7); // show 8 digits
sendByte (MAX7219_REG_DECODEMODE, 0); // use bit patterns
sendByte (MAX7219_REG_DISPLAYTEST, 0); // no display test
sendByte (MAX7219_REG_INTENSITY, 7); // character intensity: range: 0 to 15
sendString (""); // clear display
sendByte (MAX7219_REG_SHUTDOWN, 1); // not in shutdown mode (ie. start it up)
}
unsigned long start;
unsigned long lastShown;
void loop()
{
for (candidate = 3; candidate < 99999999; candidate += 2)
showIfPrime (candidate);
} // end of loop
void showIfPrime (long num)
{
// we are already skipping odd numbers, now skip if divisible by 3
if (num % 3 == 0)
return;
// Only have to check for divisible for the sqrt(number)
long upper = sqrt(num) + 6;
// Check if the number is divisible (start at 6 going up)
for (long cnum = 6; cnum <= upper; cnum += 6)
{
if (num % (cnum - 1) == 0)
return;
if (num % (cnum + 1) == 0)
return;
} // end of checking cnum-1, cnum+1
// echo to serial port for validating
if (++count >= SHOW_EVERY)
{
Serial.print(candidate);
Serial.print(" is prime. Took ");
Serial.print(millis () - start);
Serial.print (" mS. Found ");
Serial.print (found);
Serial.println (" primes.");
start = millis ();
count = 0;
}
found++;
// delay until interval is up
// (this absorbs the calculation time)
while (millis () - lastShown < SHOW_EVERY)
{ }
char buf [10];
sprintf (buf, "%8ld", candidate);
sendString (buf);
lastShown = millis ();
} // end of showIfPrime
The code was written in a bit of a hurry. It doesn't show the first few primes (well, we know what they are). I think it starts at 7, because of the nature of the algorithm. When I timed it at around the 128201 mark (the prime number 128201) it was taking about 10 mS per prime. Of course, this makes the display tick over unreadably fast, so it is throttled back to show a number every 500 mS.
The algorithm skips even numbers (naturally) and also numbers divisible by 3. Then it tests in jumps of 6, plus or minus 1, to see if they are primes, up to the square root of the number we are testing for. It isn't particularly fast, but also doesn't use a lot of memory.
Some of the code was borrowed from my temperature/humidity logger, so there is provision for displaying symbols that aren't actually used in the code.
After 8 days (almost) it is up to 8 digits of display.
That is prime number 1,370,795 from Wolfram Alpha:
PrimePi(21689413) = 1370795
At the rate of two per second you would expect that to take:
1370795 / 2 / 60 / 60 / 24 = 7.9 days
So it is on schedule.
The largest 8-digit prime is 99,999,989, which is prime number 5,761,455 in sequence. Thus it should take:
5761455/ 2 / 60 / 60 / 24 = 33.3 days
Just over 33 days before it wraps around.
|
- Nick Gammon
www.gammon.com.au, www.mushclient.com | | Top |
|
![[Go to top]](/images/gototop.gif){kind=small}
top