Exercice de programmation en équipe

 
Que j'aime à faire apprendre un nombre utile aux sages.
Immortel Archimède, artiste, ingénieur,
Qui de ton jugement peut priser la valeur ?
Pour moi, ton problème eut de pareils avantages.

La précision des calculs sur ordinateur est intrinsèquement limitée. Ainsi pour les entiers en représentation 16 bits la valeur ne peut dépasser 215-1, soit 32 767, et en représentation 32 bits 231-1, soit 2 147 483 647. Alors, pour contourner ces limitations, l'on peut calculer sur des nombres réels, représentés suivant les cas sur 32 bits, 40 bits, 64 (fréquent), ou même 80 (standard IEEE). Cependant le nombre de chiffres significatifs, reste faible : de 6 à 15 !

Pour de nombreux calculs la précision des ordinateurs ne suffit pas, par exemple pour tester des conjectures mathématiques. Il en est ainsi de la recherche de très grands nombres premiers, utilisés pour crypter les courriers électoniques, où le calcul doit se faire avec une précision absolue, tels que 2132 049-1 qui comporte 39 751 chiffres. Il en est ainsi du calcul de pi qui requiert une très grande précision.

Le Français moyen d'aujourd'hui croit connaître pi comme étant 22/7. La Bible affirme que pi = 3. A Babylone pi valait 3. Les Égyptiens connaissaient 3,16 (soit (16/9)2), les Grecs 3,1416 (Ptolémée : 3+8/60+30/3600), et au XVI° siècle on avait 11 décimales.

En 1706 John Machin avait trouvé une formule astucieuse convergeant assez rapidement et calculé 100 décimales. En 1844 Johann Dahse calcula 205 décimales. En 1853 William Shanks en trouva 707 en les calculant durant vingt ans à la main, dont les 527 premières exactes, ce qui fut montré par l'emploi d'un des premiers ordinateurs en 1945.

Ces calculs à la main prenaient des années. Aujourd'hui en quelques heures machine on obtient jusqu'à plusieurs millions de décimales :


Fig. 1 : Evolution dans le temps du nombre de décimales de connues

Fig. 2 : Quelques records dans l'évolution du calcul de pi

1949

ENIAC

2 037

70 heures

1954

NORC

3 092

13 minutes

1957

Pegasus

7 480

 

1958

IBM 704

10 000

1 h 40 mn

1959

IBM 704

16 167

 

1961

IBM 7090

100 265

8 h 43 mn

1966

IBM 7030

250 000

 

1967

CDC 6600

500 000

 

1973

CDC 7600

1 001 250

23 h 18 mn

1981

Facom M200

2 000 036

 

1982

HITACHI M280H

4 194 288

 

1982

HITACHI M280H

8 388 576

 

1983

HITACHI M280H

16 777 206

 

1/1986

CRAY 2

29 360 111

28 h

10/1986

HITACHI S810/20

67 108 839

 

1/1987

NEC SX2

134 214 700

 

5/1989

CRAY 2

480 000 000

 

8/1989

IBM 3090

1 011 196 691

 

8/1991

//

2 260 000 000

 

5/1994

//

4 044 000 000

 

9/1995

HITACHI S3800/480

6 442 450 000

 

8/6/1997

HITACHI SR2201
1024 processeurs

51 539 600 000

en 29 heures, avec 212Go, par Yasumasa KANADA

6/12/2002

HITACHI

1 240 000 000 000

Yasumasa KANADA, en 400 heures de calcul (1)

(1) source http://www.jcanu.hpg.ig.com.br/history/h4dec/h4dec06.html

Le quatrain cité en exergue permet de mémoriser les 31 premiers chiffres de :

3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9

Or pour calculer ne seraient ce que ces 31 premières décimales de pi, connues par cœur par tout taupin normalement constitué, les représentations des nombres en machine ne conviennent pas.

Il faut implémenter un type "nombre à N chiffres" avec une bibliothèque de procédures simulant les opérations sur ces nombres en multi précision. Les algorithmes utilisés sont classiques ( ils simulent les opérations chiffre à chiffre, comme à la main ) et relativement faciles à programmer.

Pour calculer les décimales de pi, on peut partir de tan(pi/4) = 1 ; c'est la formule de Leibniz :

en utilisant le développement en série d'arc tangente


pour établir cette formule, considérer que Atan(x) est la primitive de 1/(1+x2) = 1 - x2 + x4 - x6 + ...

L'erreur commise en ne sommant que les n premiers termes est sensiblement égale au (n+1)ième terme. La convergence est lente ; on l'améliore en décomposant pi en combinaison linéaire à coefficients simples d'arcs ayant une tangente simple et on calcule chaque arc tangente par son développement en série. Ces formules convergent d'autant plus vite que la plus grande des tangentes mises en jeu est petite. Citons quelques formules classiques :

Suites :
Pour en savoir plus sur le calcul de pi.
TD calcul de pi en équipe

Ecole des Mines de Nancy

Document : http://www.mines.u-nancy.fr/~tisseran/cours/pi/
juin 1998 - Dernière mise à jour : mars 2006

Remarques, suggestions, questions, ... : e-mail tisseran@mines.u-nancy.fr