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 2¹⁵-1, soit 32 767, et en représentation 32 bits 2³¹-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 2^{132 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)²), 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+x²) = 1 - x² + x⁴ - x⁶ + ...

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