Dopo aver visto una versione leggermente modificata di un problema tratto da Adventofcode, vediamo un altro contest interessante, tratto dal sito Project Euler, che propone attualmente 815 problemi differenti (più altri 10 aggiunti di recente), che possiamo risolvere con il linguaggio di programmazione che preferiamo.
La filosofia del sito è questa:
Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.
Vediamo il problema numero 14 intitolato Longest Collatz sequence: si tratta di risolvere un problema matematico di questo tipo (appunto la cosiddetta Congettura di Collatz, che empiricamente ha sempre funzionato, ovvero arriva a convergenza, ma in termini generali è tutt'ora un problema irrisolto della matematica):
- numero di partenza N, intero positivo
- se è pari, N = N/2 (fintanto che N=1)
- se è dispari, N = 3N+1 (fintanto che N=1)
Questo esercizio chiede in particolare di valutare fra tutti i numeri inferiori a 1.000.000, quello che genera la sequenza più lunga prima di arrivare a convergenza.
Il programma l'ho scritto in linguaggio C, in modo tale da poter avere la massima efficienza possibile (memorizzo volutamente le variabili nei registri della CPU anziché nella RAM). Questo è il codice e di seguito riportiamo i risultati:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(){
clock_t start = clock();
register unsigned int i,x;
register int sum=0;
register int sum_max=0;
register int pos=-1;
for(i=1;i<=1000000;i++){
x=i;
if(sum>sum_max){sum_max=sum;pos=i-1;}
sum=0;
while(x!=1){
if(x%2==0){
x/=2;
}else{
x=3*x+1;
}
sum+=1;
}
}
clock_t end = clock();
printf("maxiter=%d | N=%d\n",sum_max-1,pos);
printf("%f s\n",(float)(end-start)/CLOCKS_PER_SEC);
return 0;
}
Risultati: il valore N=837799 è il numero che genera la più lunga catena di iterazioni prima di convergere (ovvero 524 termini!). Il tempo di esecuzione del codice, scritto in questo modo molto efficiente, è stato di 0,32 secondi. Giusto un commento, come indicazione generale di Project Euler, abbiamo anche <<One Minute Rule>>, ovvero far girare il codice in meno di un minuto (altrimenti non è sufficientemente efficiente): ovviamente dipende dalla macchina, dal linguaggio di programmazione scelto, questo è un consiglio generale. In ogni caso, il valore di 0,32 secondi dovrebbe essere più che buono insomma! 😀
Osservazioni: sarebbe possibile aggiungere qualche ulteriore ottimizzazione al codice ovvero quando il valore N si trova ad essere pari ad un numero precedentemente valutato, che ha portato ad una convergenza (più o meno lunga), vale la pena uscire direttamente dal ciclo e passare al successivo (dato che sappiamo convergere).
