J'ai trouve ça:
Je suis un jour tombé sur un petit programme de 10 lignes, écrit en langage C dans un style pour le moins concis (les développeurs apprécieront), et ayant l'étonnante propriété de calculer les 2 400 premières décimales de Pi (2 399 pour être tout à fait exact, si l'on considère que le premier chiffre 3 représente la partie entière).
L'auteur en est inconnu et le principe appliqué m'échappe totalement.
Voici le petit bijou :
#include <stdio.h>
void main(void)
{
int a = 10000, b, c = 8400, d, e, f[8401], g;
for ( ; b-c ; ) f[b++] = a/5;
for ( ; d = 0, g = c*2 ; c -= 14, printf("%.4d",e+d/a), e = d%a)
{
for (b = c ; d += f[b]*a, f[b] = d%--g, d /= g--, --b ; d *= b);
}
}
Pour les non coutumiers du langage C, en voici une traduction en pseudo-langage :
programme
variables :
a,b,c,d,e,g : entiers
f : tableau_de 8401 entiers (de f[0] à f[8400])
a = 10000
b = 0
c = 8400
tant_que (b différent_de c) faire
f[b] = a / 5
b = b+1
fin_faire
tant_que (c > 0) faire
d = 0
g = 2*c
b = c
tant_que (b > 0) faire
d = d + f[b]*a
g = g-1
f[b] = d modulo g
d = d / g
g = g-1
b = b-1
d = d*b
fin_faire
c = c-14
Imprimer_au_minimum_sur_4_caractères (e+d/a)
e = d modulo a
fin_faire
fin_programme
et si vous n'avez pas de compilateur à portée de la main, en voici le résultat :
314159265358979323846264338327950288419716939937510582097494 459230781640628620899862803482534211706798214808651328230664 709384460955058223172535940812848111745028410270193852110555 964462294895493038196442881097566593344612847564823378678316 527120190914564856692346034861045432664821339360726024914127 372458700660631558817488152092096282925409171536436789259036 001133053054882046652138414695194151160943305727036575959195 309218611738193261179310511854807446237996274956735188575272 489122793818301194912983367336244065664308602139494639522473 719070217986094370277053921717629317675238467481846766940513 200056812714526356082778577134275778960917363717872146844090 122495343014654958537105079227968925892354201995611212902196 086403441815981362977477130996051870721134999999837297804995 105973173281609631859502445945534690830264252230825334468503 526193118817101000313783875288658753320838142061717766914730 359825349042875546873115956286388235378759375195778185778053 217122680661300192787661119590921642019893809525720106548586 327886593615338182796823030195203530185296899577362259941389 124972177528347913151557485724245415069595082953311686172785 588907509838175463746493931925506040092770167113900984882401 285836160356370766010471018194295559619894676783744944825537 977472684710404753464620804668425906949129331367702898915210 475216205696602405803815019351125338243003558764024749647326 391419927260426992279678235478163600934172164121992458631503 028618297455570674983850549458858692699569092721079750930295 532116534498720275596023648066549911988183479775356636980742 654252786255181841757467289097777279380008164706001614524919 217321721477235014144197356854816136115735255213347574184946 843852332390739414333454776241686251898356948556209921922218 427255025425688767179049460165346680498862723279178608578438 382796797668145410095388378636095068006422512520511739298489 608412848862694560424196528502221066118630674427862203919494 504712371378696095636437191728746776465757396241389086583264 599581339047802759009946576407895126946839835259570982582262 052248940772671947826848260147699090264013639443745530506820 349625245174939965143142980919065925093722169646151570985838 741059788595977297549893016175392846813826868386894277415599 185592524595395943104997252468084598727364469584865383673622 262609912460805124388439045124413654976278079771569143599770 012961608944169486855584840635342207222582848864815845602850
Questions
Lors de la mise en ligne de cette page j'avais posé les questions suivantes :
Quelqu'un serait il capable de m'expliquer l'algorithme sur lequel reposent ces quelques lignes de code ?
Pourquoi 2400 ? Pourrait on étendre le principe appliqué à un nombre quelconque de décimales ?
Réponses
J'ai trouvé les réponses à ces épineuses questions dans un livre passionnant et très bien illustré (que je recommande) "Le fascinant nombre Pi" par Jean-Paul Delahaye, aux éditions Pour La Science - Belin (ISBN : 2-9029-1825-9) pages 94 à 98.
L'algorithme utilisé repose sur une série d'Euler :
Pi = 2 (1 + 1/3 + 1.2 / 3.5 + 1.2.3 / 3.5.7 + 1.2.3.4 / 3.5.7.9 + ...)
= 2 somme pour_n=0_à_l'infini de (1.2. ... .n / 1.3. ... (2.n+1))
Avec cette série, on montre que pour connaître Pi avec une précision de N décimales il suffit de sommer
Log2(10N) ~= 3,32.N termes.
Les calculs étant effectués en base 10 000, les chiffres sont affichés par groupe de 4 à la fin du calcul.
Le programme calcule 600 chiffres en base 10 000 équivalant à 2 400 chiffres décimaux.
Le nombre de termes utilisés est 600.4.3,32 ~= 8 400 (arrondi).
Le programme comporte une première boucle d'initialisation, suivie d'une double boucle de calcul et d'impression.
La double boucle exploite la série d'Euler écrite sous la forme de Horner pour limiter le nombre de multiplications :
1 000 Pi ~= 10 000 / 5 ( 1 + 1 / 3 ( 1 + 2 / 5 ( 1 + 3 / 7 ( ... + 8 399 / 16 799 ))))
Pour aboutir, le calcul doit être effectué dès le départ avec un nombre de chiffres de l'ordre de grandeur de celui voulu à la fin.
--------------------------------------------------
------------------------------
Pour avoir d'autres informations sur les algorithmes de calcul du nombre Pi et de bien d'autres constantes je vous conseille de visiter le site de Simon Plouffe.
