Register forum user name Search FAQ

Gammon Forum

Notice: Any messages purporting to come from this site telling you that your password has expired, or that you need to verify your details, confirm your email, resolve issues, making threats, or asking for money, are spam. We do not email users with any such messages. If you have lost your password you can obtain a new one by using the password reset link.
 Entire forum ➜ Electronics ➜ Microprocessors ➜ Arduino generating prime numbers

Arduino generating prime numbers

Postings by administrators only.

Refresh page


Posted by Nick Gammon   Australia  (23,120 posts)  Bio   Forum Administrator
Date Wed 16 Oct 2013 05:07 AM (UTC)

Amended on Mon 25 Nov 2013 09:59 PM (UTC) by Nick Gammon

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

Posted by Nick Gammon   Australia  (23,120 posts)  Bio   Forum Administrator
Date Reply #1 on Fri 29 Nov 2013 11:42 PM (UTC)

Amended on Sat 30 Nov 2013 04:41 AM (UTC) by Nick Gammon

Message
This amended sketch outputs 16-digit prime numbers to two LED displays hooked together.


// Prime number generator
//
// Author: Nick Gammon
// Date:   8th October 2013

#include <BigNumber.h>
#include <SPI.h>

const char FIRST_PRIME_TO_USE [] =  "3456789000054141";

const int CHIP_COUNT = 2;  // how many MAX7219s

// 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;

void sendToAll (const byte reg, const byte data)
  {    
  digitalWrite (SS, LOW);
  for (int chip = 0; chip < CHIP_COUNT; chip++)
    {
    SPI.transfer (reg);
    SPI.transfer (data);
    }
  digitalWrite (SS, HIGH); 
  }  // end of sendToAll


void sendChar (const int which, const char c)
  {
  byte i;
  
  // segment is in range 1 to 8
  const byte segment = 8 - (which % 8);
  // for each daisy-chained display we need an extra NOP
  const byte nopCount = which / 8;
  // start sending
  digitalWrite (SS, LOW);
  // send extra NOPs to push the data out to extra displays
  for (byte i = 0; i < nopCount; i++)
    {
    SPI.transfer (MAX7219_REG_NOOP);
    SPI.transfer (MAX7219_REG_NOOP);  // need 16 bits of NOP
    }    
  // send the segment number and data
  SPI.transfer (segment);
  SPI.transfer (c);
  // start with enough NOPs so later chips don't update
  for (int i = 0; i < CHIP_COUNT - nopCount - 1; i++)
    {
    SPI.transfer (MAX7219_REG_NOOP);
    SPI.transfer (MAX7219_REG_NOOP);  // need 16 bits of NOP
    }    
  // all done!
  digitalWrite (SS, HIGH); 
  }  // end of sendChar
  
// write an entire null-terminated string to the LEDs
void sendString (const char * s)
{
  for (int pos = 0; *s; pos++)
    sendChar (pos, *s++);
}  // end of sendString


BigNumber candidate;
BigNumber one (1);
BigNumber two (2);

void setup() {
  Serial.begin(115200); 

  while (!Serial) { }

  BigNumber::begin ();  

  SPI.begin ();

  sendToAll (MAX7219_REG_SCANLIMIT, 7);      // show 8 digits
  sendToAll (MAX7219_REG_DECODEMODE, 0xFF);  // use digits (not bit patterns)
  sendToAll (MAX7219_REG_DISPLAYTEST, 0);    // no display test
  sendToAll (MAX7219_REG_INTENSITY, 15);      // character intensity: range: 0 to 15
  sendToAll (MAX7219_REG_SHUTDOWN, 1);       // not in shutdown mode (ie. start it up)
  
  // Send "Hello-----------" to save LEDs showing rubbish
  sendString ("\x0C\x0B\x0D\x0D\x30\x0A\x0A\x0A\x0A\x0A\x0A\x0A\x0A\x0A\x0A\x0A");

  Serial.println ();
  Serial.println ();
  Serial.println ("Starting.");

  candidate = BigNumber (FIRST_PRIME_TO_USE);
  if (candidate % two == 0)
    candidate++;
}

void loop() 
{

  for ( ; candidate < BigNumber ("9999999999999999"); candidate += 2)
    showIfPrime (candidate);

  candidate = 3;  // back to start!
}  // end of loop

void rng (BigNumber & result)
{
  result = BigNumber (random ());  
}

bool Miller(BigNumber source, int certainty)
{

  if (source == 2 || source == 3)
    return true;
  if (source < two || source % two == 0)
    return false;
  
  BigNumber d = source - one;
  int s = 0;

  while(d % two == 0)
  {
    d /= two;
    s += one;
  }

  BigNumber a;

  for(int i = 0; i < certainty; i++)
  {
    do
    {
      rng (a);
    } 
    while(a < two || a >= source - two);

    BigNumber x = a.powMod (d, source);
    if(x == one || x == source - one)
      continue;

    for(int r = 1; r < s; r++)
    {
      x = x.powMod(two, source);
      if(x == one)
        return false;
      if(x == source - one)
        break;
    }

    if(x != source - one)
      return false;
  }

  return true;
}  // end of Miller

unsigned long start;
unsigned long lastShown;
long found = 1; // Count of primes we found

void showIfPrime (BigNumber num) 
{

  if (!Miller (num, 10))
    return;

  Serial.print(num);
  Serial.print(" is prime. Took ");
  Serial.print(millis () - start);
  Serial.print (" mS. Found ");
  Serial.print (found);
  Serial.println (" primes.");
  start = millis ();

  char * buf = num.toString ();
  sendString (buf);
  free (buf);
  
  found++;
  lastShown = millis ();

}  // end of showIfPrime


It also writes the results to the serial port along with the time taken to calculate each one. Warning, it can be slow because these big primes take a while.


3456789000054161 is prime. Took 19802 mS. Found 1 primes.
3456789000054197 is prime. Took 27051 mS. Found 2 primes.
3456789000054241 is prime. Took 31141 mS. Found 3 primes.
3456789000054251 is prime. Took 13940 mS. Found 4 primes.
3456789000054253 is prime. Took 9961 mS. Found 5 primes.
3456789000054281 is prime. Took 22816 mS. Found 6 primes.
3456789000054373 is prime. Took 54417 mS. Found 7 primes.
3456789000054391 is prime. Took 17905 mS. Found 8 primes.
3456789000054413 is prime. Took 19691 mS. Found 9 primes.
3456789000054589 is prime. Took 97513 mS. Found 10 primes.
3456789000054601 is prime. Took 14746 mS. Found 11 primes.
3456789000054647 is prime. Took 32316 mS. Found 12 primes.
3456789000054673 is prime. Took 22139 mS. Found 13 primes.
3456789000054701 is prime. Took 22972 mS. Found 14 primes.
3456789000054713 is prime. Took 15024 mS. Found 15 primes.
3456789000054721 is prime. Took 13142 mS. Found 16 primes.
3456789000054751 is prime. Took 24446 mS. Found 17 primes.
3456789000054773 is prime. Took 20418 mS. Found 18 primes.
3456789000054811 is prime. Took 27511 mS. Found 19 primes.
3456789000054827 is prime. Took 16502 mS. Found 20 primes.
3456789000054853 is prime. Took 21296 mS. Found 21 primes.
3456789000054931 is prime. Took 47262 mS. Found 22 primes.
3456789000054977 is prime. Took 31773 mS. Found 23 primes.
3456789000054997 is prime. Took 18609 mS. Found 24 primes.
3456789000055009 is prime. Took 14801 mS. Found 25 primes.
3456789000055063 is prime. Took 35556 mS. Found 26 primes.
3456789000055091 is prime. Took 22643 mS. Found 27 primes.
3456789000055099 is prime. Took 12863 mS. Found 28 primes.
3456789000055109 is prime. Took 13615 mS. Found 29 primes.
3456789000055117 is prime. Took 12613 mS. Found 30 primes.
3456789000055147 is prime. Took 23835 mS. Found 31 primes.
3456789000055199 is prime. Took 34922 mS. Found 32 primes.


So, it can take 30 or more seconds to find one prime.

Example of it in operation:



This version uses Big Numbers to handle the large number of digits, and the Miller-Rabin test for primality testing.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.


14,009 views.

Postings by administrators only.

Refresh page

Go to topic:           Search the forum


[Go to top] top

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.