backup del Post

Calcolo… enigmatico

La notizia è di qualche giorno fa: Nicholas Sze, di Yahoo!, ha calcolato che la cifra decimale numero 2.000.000.000.000.000 di pi greco è uno zero. Il tutto è stato ottenuto con 23 giorni di computazione su mille computer di Yahoo!, o se si preferisce con l’equivalente di 500 anni di CPU. Ma la cosa che forse può sembrare più strana è che Sze non ha affatto calcolato due quadrilioni di cifre decimali, ma si è limitato a trovare la duequadrilionesima, insieme a qualcuna subito prima e subito dopo di essa.

Ma come è possibile un exploit simile? La storia è lunga, ma la parte interessante è piuttosto recente. Solo nel 1761 J. H. Lambert dimostrò che pi greco era irrazionale, ma ho come il sospetto che già i greci avessero dei dubbi al riguardo, e avevano deciso di non pensarci su e nascondere la cosa sotto un tappeto (rotondo). Archimede però aveva preso il toro per le corna, dato che a lui piaceva giocare con i numeri; usando poligoni inscritti e circoscritti al cerchio, dimostrò che π è compreso tra 3 + 1/7 e 3 + 10/71, risultato che rimase insuperato per secoli… anzi, 22/7 era il valore usato in pratica; sempre meglio che il valore di 3 che si trova nella Bibbia, in fin dei conti.

Il passo successivo avvenne alla fine del diciassettesimo secolo, quando i matematici hanno iniziato a divertirsi con le serie infinite. Le serie ricavate dalle funzioni trigonometriche sono storicamente state quelle più utilizzate: come racconta Wikipedia, la prima ad essere stata trovata è quella di Leibniz, che partendo dallo sviluppo della funzione arcotangente di x in 1 dà

π/4 = 1 − 1/3 + 1/5 − 1/7 + 1/9 − 1/11 + …

che a dire il vero non serve assolutamente a nulla dal punto di vista pratico, ed è solo stata uno stimolo per cercare qualcosa di più facilmente calcolabile. Nei secoli sono state ricavate parecchie formule di questo tipo; la più veloce è attualmente l’algoritmo di Salamin-Brent, scoperto indipendentemente dai due matematici e pubblicato nel 1975; esso permette di calcolare N cifre significative in un tempo proporzionale a N log(N) log(log(N)), e credo sia quello con cui è stato prodotto il record attuale di numero di cifre di pi greco (“solo” 2,7 trilioni…)

Nel 1995 però Simon Plouffe se ne uscì con una formula incredibile, mostrata qui a fianco. A prima vista potrebbe non dirvi molto; sembra un po’ complicata, anche se non eccessivamente. Però se la si studia attentamente si può scoprire che possiamo limitarci a considerare pochi valori di n per trovare la k-sima cifra esadecimale, perché quelli precedenti sicuramente non la toccano e quelli seguenti sono troppo piccoli. Tutto qui! Scherzo, naturalmente: a nessuno era venuto in mente che fosse possibile una cosa del genere, e forse non è così incredibile che l’abbia scoperta uno che per un paio d’anni ha detenuto il record mondiale del numero di cifre di π imparate a memoria e che è un coautore della On-Line Encyclopedia of Integer Sequences; un tipo abbastanza pazzo, insomma.

Dopo la formula originale (che trova appunto le cifre in base 16) ne sono state trovate altre più veloci da computare; nessuna purtroppo in base 10, il che spiega perché Sze ha calcolato anche “qualche cifra prima e qualche dopo” quella in duequadrilionesima posizione. In pratica, la conversione in base 10 richiede qualche cifra prima e qualche dopo per essere certi di non aver perso nulla. Ma a che serve tutto questo? A nulla, naturalmente; al più può servire per testare i programmi di calcolo parallelo. La formula usata è infatti altamente parallelizzabile: ecco perché Yahoo! ha potuto usare una grande quantità di elaboratori senza soverchi problemi. Un ultima chicca: l’algoritmo MapReduce di distribuzione operazioni usato da Sze è stato creato… da Google. Chissà se a Mountain View raccoglieranno la sfida e cercheranno qualche altra cifra in posizione ancora più incredibile!