Calcolare i numeri primi di Mersenne con Arduino

Post Views: 686

Oggi impareremo come calcolare i numeri primi di Mersenne con un piccolo Arduino, e vedremo come le capacità di calcolo sono interessanti.

Un nostro assiduo lettore, Francesco Paolo, ci ha chiesto un articolo un po’ più “matemagico” per utilizzare l’Arduino come un piccolo calcolatore.

Sempre pronti a raccogliere le sfide, presentiamo quindi l’algoritmo di Lucas-Lehmer implementato su di un Arduino.

I numeri di Mersenne

Marin Mersenne era un teologo, filosofo e matematico vissuto a cavallo tra il XVI ed il XVII secolo. Appassionato di teoria dei numeri, ebbe un ruolo importante come fulcro delle comunicazioni scientifiche in Europa (in particolare si ricorda lo scambio epistolare con Pierre de Fermat). Il religioso ha però legato il suo nome ad una serie di numeri particolari, della forma 2^p-1, con esponente P primo. Quanti di questi numeri, si chiedeva Mersenne, sono effettivamente primi?

La risposta appare quasi incredibile: ad oggi, utilizzando i sistemi di calcolo più potenti, siamo riusciti a scoprirne solo 51. Il più grande di essi, 2^82589933-1, è un mostro di 24.862.048 cifre.

Per calcolare la primalità di tali numeri si fa largo uso di ottimizzazioni varie, aritmetica in precisione multipla e librerie specifiche. Arduino, con il suo formato intero lungo da 32 bit massimi, non è in grado di lavorare su tali strutture, ma l’algoritmo di Lucas-Lehmer utilizzato per il calcolo può essere utilizzato senza problema a fini didattici: con 31 bit saremo in grado di calcolare i primi 8 numeri primi di Mersenne (sino a 2³¹-1), in poco più di tre centesimi di secondo (sopprimendo le stampe).

Niente male per un microcontrollore a 16MHz…

Il codice

Il codice per il calcolo della primalità dei numeri di Mersenne è estremamente semplice: consta del classico loop (che interromperemo con un while(true) al termine del calcolo) ed una funzione che, per ciascun valore dell’esponente p, ne controlla la primalità. Come anticipato, il programma utilizza l’algoritmo di Lucas-Lehmer, che ha complessità quasi lineare (raddoppia al raddoppiare dell’esponente).

/*
 * LL_test I valori calcolati sono esatti solo sino ad M31, a causa dell'ampiezza di s a 64 bit (uint_64)
 * Il timing è però valido, in quanto tarato sul numero di bit del numero da testare
 */
/*
 * Lucas-Lehmer primality test
 */

unsigned long t1, tt;
 
void setup() {
  Serial.begin(115200);

}

void loop() {
  t1 = micros();
  
  const int upb = 31; 
  unsigned long p;
  Serial.println(" Mersenne primes:\n");
  for( p = 2; p <= upb; p += 1 ){
    if(is_mersenne_prime(p) ){
      Serial.print(" M"); Serial.print(p); Serial.println(" è primo!");
      //asm(" ");
    }
  }
    
  tt = micros() - t1;

  Serial.print("Tempo impiegato: ");
  Serial.print((float)tt/1000);
  Serial.println( " millisecondi.");
  while(true);
}

bool is_mersenne_prime( unsigned long p ){
  if( p == 2 ) return true;
  else {
    const unsigned long m_p = ( 1LU << p ) - 1; 
    Serial.print("Sto calcolando M");
    Serial.print(p);
    Serial.print(" ---> ");
    Serial.println(m_p);
    uint64_t s = 4;
    unsigned long k; 
    for (k = 3; k <= p; k++){
      s = (s * s - 2) % m_p;
    }; 
    return s == 0;
  }
}

* LL_test I valori calcolati sono esatti solo sino ad M31, a causa dell'ampiezza di s a 64 bit (uint_64)

* Il timing è però valido, in quanto tarato sul numero di bit del numero da testare

* Lucas-Lehmer primality test

unsigned long t1, tt;

void setup() {

Serial.begin(115200);

}

void loop() {

t1 = micros();

const int upb = 31;

unsigned long p;

Serial.println(" Mersenne primes:\n");

for( p = 2; p <= upb; p += 1 ){

if(is_mersenne_prime(p) ){

Serial.print(" M"); Serial.print(p); Serial.println(" è primo!");

//asm(" ");

}

tt = micros() - t1;

Serial.print("Tempo impiegato: ");

Serial.print((float)tt/1000);

Serial.println( " millisecondi.");

while(true);

}

bool is_mersenne_prime( unsigned long p ){

if( p == 2 ) return true;

else {

const unsigned long m_p = ( 1LU << p ) - 1;

Serial.print("Sto calcolando M");

Serial.print(p);

Serial.print(" ---> ");

Serial.println(m_p);

uint64_t s = 4;

unsigned long k;

for (k = 3; k <= p; k++){

s = (s * s - 2) % m_p;

};

return s == 0;

}

Partiamo dal valore s = 4. Eleviamo al quadrato s, sottraiamo 2 ed eseguiamo il modulo del risultato rispetto a 2^p. Questa operazione ci garantisce che, per quanto grande sia il nostro numero, non avremo mai un risultato maggiore di 2 elevato a P. Ripetiamo sin quando non abbiamo terminato i bit (valore di p). Se al termine di questo algoritmo il valore di s è zero, allora il numero è primo.

Un’occhiata ai risultati

Di seguito il listato con i risultati del calcolo, stampato su serial monitor. Notare che nel secondo caso abbiamo soppresso parte delle stampe di debug, e questo ha reso il codice più veloce di oltre il 100%.

Numeri di Mersenne Arduino — **Elenco risultati con stampa di debug attivata**

E’ facile osservare come il programma cicli su tutti gli esponenti compresi tra 2 e 31, e bufferizzi la stampa sul monitor seriale.

Se siete appassionati di benchmarking, potete anche testare il codice su altre schede magari dotate di microprocessore Cortex, e vedrete come anche i tempi di esecuzione tenderanno a diminuire…

Fateci sapere se siete interessati alla valutazione di algoritmi con Arduino!

Link utili:

Join our groups on Telegram…

… and don’t forget our social channels!

Luigi_Morelli

Definire ciò che si è non risulta mai semplice o intuitivo, in specie quando nella vita si cerca costantemente di migliorarsi, di crescere tanto professionalmente quanto emotivamente. Lavoro per contribuire al mutamento dei settori cardine della computer science e per offrire sintesi ragionate e consulenza ad aziende e pubblicazioni ICT, ma anche perche’ ciò che riesco a portare a termine mi dà soddisfazione, piacere. Così come mi piace suonare (sax, tastiere, chitarra), cantare, scrivere (ho pubblicato 350 articoli scientfici e 3 libri sinora, ma non ho concluso ciò che ho da dire), leggere, Adoro la matematica, la logica, la filosofia, la scienza e la tecnologia, ed inseguo quel concetto di homo novus rinascimentale, cercando di completare quelle sezioni della mia vita che ancora appaiono poco ricche.