Sabino Maggi
Anche se ho una collezione molto ampia di scansioni in pdf di vecchi numeri di BYTE Magazine, mi piace ogni tanto leggere qualche fascicolo preso in prestito dalla biblioteca dell’Istituto (del resto qualche tempo fa li ho salvati da una fine stile Fahrenheit 451).
Nonostante la mia passione per la tecnologia, infatti, ci sono dei casi in cui preferisco ancora l’analogico al digitale. Fra cui ci sono i libri e le riviste.
Sfogliando un numero di BYTE dell’89 dedicato a Unix, mi ha incuriosito una lettera sul famoso Crivello di Eratostene, un algoritmo per calcolare i numeri primi che ha più di 2200 anni. L’algoritmo funziona come un setaccio (da cui il nome): elimina uno dopo l’altro i numeri composti lasciando alla fine soltanto i numeri primi.
La lettera su BYTE introduceva all’algoritmo standard e ad una ottimizzazione ben nota, con la quale era possibile velocizzare il calcolo dei numeri primi senza complicarne più di tanto l’implementazione in BASIC.
Il BASIC è stato il linguaggio di programmazione più popolare degli anni 80, gli anni della rivoluzione del personal computer. A quei tempi il BASIC era usato per interagire con il computer stesso – ne costituiva di fatto il sistema operativo vero e proprio – ed ha contribuito a formare le prime generazioni di programmatori che sviluppavano software per il nascente mondo dell’informatica personale. Non è un caso che sia la Apple che la Microsoft abbiano basato i primi prodotti proprio sul BASIC [1,2].
Il listato originale in BASIC è mostrato qui sotto, in una forma (spero) più leggibile rispetto a quanto consentito dall’impaginazione di BYTE (oltre che dall’abitudine di quei tempi di compattare all’estremo i programmi per ridurre il più possibile l’occupazione della memoria). Il programma determina i numeri primi da 1 fino al valore impostato nella variabile max. Per usarlo, bisogna anche impostare il valore di root alla radice quadrata di max (arrotondata ad un numero intero).
max=8192
root=90
DIM flags (max)
FOR num=1 TO max
flags(num)=TRUE
NEXT num
FOR num=2 TO root
IF flags (num) THEN
FOR mult=num*num TO max STEP num
flags(mult)=FALSE
NEXT
END IF
NEXT num
Appena ho visto il programma ho pensato che sarebbe stato immediato tradurlo in Python, un linguaggio che mi piace moltissimo e che considero il migliore compromesso fra potenza e facilità d’uso. Python può essere usato a più livelli, da linguaggio puramente procedurale fino a linguaggio orientato agli oggetti, e quindi si presta bene ad essere usato per imparare i fondamenti delle programmazione.
Nella prima traduzione in Python ho lasciato il più possibile inalterato il codice originale. Le piccole differenze sono dovute alle particolarità sintattiche dei due linguaggi. In Python esiste la funzione max() e non si può usare lo stesso nome per una variabile, gli indici degli array iniziano da 0 e la funzione range(0, N) crea una lista di numeri interi da 0 fino a N-1, e non fino ad N come sarebbe immediato pensare.
num_max = 256
root = 16
flags = []
for num in range(0, num_max + 1):
flags.append(True)
for num in range(2, root):
if flags[num] == True:
for mult in range(num**2, num_max + 1, num):
flags[mult] = False
print("Sieve of Eratosthenes between 1 and %d (BYTE-style): true/false map" %(num_max))
print flags[1:num_max + 1]
print
print("Sieve of Eratosthenes between 1 and %d (BYTE-style): prime numbers" %(num_max))
for num in range(1, num_max + 1):
if flags[num] == True:
print num,
else:
print "-",
Alla fine ho aggiunto il codice per stampare i risultati del calcolo, mostrando prima il contenuto grezzo dell’array (o meglio della lista) usato per determinare se ciascun numero è primo o meno, e poi convertendo l’output in una forma più leggibile.
Per provare il programma, basta copiare il codice in un editor di testo (come i soliti TextWrangler, TextMate, Atom, Brackets, o analoghi), salvarlo sul disco rigido con un nome qualsiasi (diciamo “sieve.py”), ed eseguirlo dal Terminale con il comando
$ python sieve.py
[caption id=”attachment_1305” align=”aligncenter” width=”605”]
Output della traduzione in Python del programma originale in BASIC per il calcolo dei numeri primi.[/caption]
Si può provare a misurare il tempo di esecuzione del programma impostando la variabile num_max ad un valore relativamente grande (e ricordando di modificare anche il valore di root, che deve essere la radice quadrata di num_max).
$ time python ./sieve.py
Per evitare di influenzare la misura è bene cancellare (o commentare) la sezione del codice contenente i comandi di stampa dei risultati, che sono molto lenti rispetto al puro codice di calcolo.
Il mio iMac del 2008 impiega 0.025 secondi per calcolare i numeri primi fino a 10.000, e ben 22.5 secondi per arrivare fino a 25.000.000.
Ma di questo parleremo più diffusamente un’altra volta.
[1] Il primo software prodotto dalla Micro-Soft di Bill Gates e Paul Allen fu proprio un interprete BASIC per l’Altair 8800, il primo microcomputer personale in assoluto. La storia è raccontata nel bel libro di Paul Freiberger e Michael Swaine, “Fire in the Valley: The Making of the Personal Computer”, McGraw-Hill, 2000, ed è riassunta molto bene in questa pagina su Wikipedia (per una volta la versione in italiano di un articolo è allo stesso livello di quella originale).
[2] Steve Wozniak, la mente geniale della Apple degli inizi, scrisse da zero un interprete BASIC per l’Apple I e II, che diventò il più diffuso interprete BASIC degli anni ‘80, un vero riferimento a cui tutti gli altri interpreti BASIC cercavano di ispirarsi.