-
- Obsession de
Pi
- par Jean-Paul
Delahaye
- in Pour La Science de janvier 1997
-
- Grâce à une
nouvelle formule pour Pi, on sait calculer (en base 2) le 400
milliardième chiffre de Pi sans connaître les
autres.
-
- En 1995, nombreux
étaient ceux qui pensaient qu'il n'y avait
- plus grand-chose de spectaculaire à attendre concernant
Pi: sans
- doute allait-on continuer à progresser dans le calcul
des
- décimales, mais cela se ferait au rythme
régulier du
- perfectionnement des machines, et non pas grâce à
des avancées
- mathématiques nouvelles. La découverte d'une
nouvelle formule
- pour Pi par une équipe canadienne de
l'Université Simon
- Fraser, à Burnaby, en
Colombie-Britannique, et les
- conséquences de cette découverte prouvent que Pi
reste à la fois
- riche et énigmatique. On sait calculer aujourd'hui
presque aussi
- loin que l'on veut les chiffres du nombre Pi (hélas, en
binaire
- ou en base 16, pas encore dans le système
décimal).
-
- LES MACHINES NE FONT PAS
TOUT
-
-
- Un livre d'histoire sur le calcul de Pi
énonçait, en 1970,
- qu'il n'y aurait plus rien de nouveau concernant le
quadrimillé-
- naire
nombre Pi. Or, dès 1975, la
découverte
de nouveaux
- algorithmes
de calcul de Pi et l'application des méthodes de
- multiplication rapide donnaient un coup
d'accélérateur au calcul
- des décimales de Pi, ce qui permettait, en quelques
années, de
- passer du million de décimales connues
- (record atteint, en 1973, par les Français
Jean
- Guilloud
et Martine Bouyer) aux six milliards quatre cents
- millions de décimales en 1995
(record
actuel du Japonais
- Yasumasa Kanada). Les progrès des microprocesseurs
seuls
- auraient permis de passer de 1 à 500 millions, au
mieux, entre
- 1973 et 1995. L'histoire de Pi I'avait déjà
montré: le progrès
- mathématique est essentiel pour aller plus loin dans le
calcul
- de ses chiffres, et c'est ce qui donne du sens à cette
course
- (outre l'utilité parfois évoquée de ces
calculs pour tester les
- ordinateurs et leurs logiciels). La méthode que nous
allons
- examiner est d'une nature bien différente, et plus
- révolutionnaire encore que les méthodes de
multiplication
- rapide: elle est fondée sur la découverte d'une
formule qui
- permet le calcul des chiffres de Pi très loin sans
avoir à
- calculer ceux qui précèdent. Selon
Stan
Wagon, ce nouveau pro-
- grès constitue un changement de direction radical dans
le
- cours d'une histoire pourtant aussi ancienne que celle des
- mathématiques. Il y a quelques mois, si vous aviez
demandé à un
- mathématicien s'il jugeait possible de sauter au
- dix-milliardième chiffre de Pi sans avoir à en
calculer les
- précédents, il vous aurait ri au nez: pour tout
le monde,
-
- c'était impossible. Les mathématiciens sont
parfois persuadés,
- sans véritable preuve, mais en s'appuyant sur leur
fameuse et
- trop commode intuition, de certaines impossibilités
qu'un
- illuminé ou simplement un mathématicien
génial sans complexe
- vient balayer d'un revers de main. En 1989, les frères
Borwein,
- grands spécialistes des méthodes de calcul de Pi
(voir
Les
- mathématiciens,
Pour la Science, 1996), écrivaient: «ll est
- raisonnable de spéculer que calculer le
n-ième chiffre de pi n'est
- pas vraiment plus facile que calculer tous les chiffres
- jusqu'au n-ième.» Il est amusant de
remarquer que l'un des
- frères Borwein appartient à l'équipe qui
a démenti ce jugement!
-
- UNE FORMULE NOUVELLE
-
- La découverte de la nouvelle formule est datée
avec une grande
- précision (sans doute grâce aux sauvegardes des
fichiers
- informatiques contenant les traces des calculs qui ont conduit
à
- sa découverte): le 19 septembre 1995, à Oh29,
Simon Plouffe,
- après un mois de recherche à tâtons, dans
le cadre de travaux
- menés avec
David
Bailey et Peter
Borwein, en s'aidant du
- programme de calcul formel
PSLQ,
mais pleinement conscient de ce
- qu'il cherche (I'utilisation de moyens informatiques pour
- faire des mathématiques ne signifie pas que le
mathématicien
- devient idiot!), trouve que:
-
- Cette fantastique formule permet de calculer n'importe quel
- chiffre de Pi en base 2: vous pouvez calculer directement le
40
- milliardième
chiffre de sans calculer les précédents.
- D'ailleurs, I'équipe canadienne l'a calculé:
c'est un '1 ' suivi
- de 0010010. Aujourd'hui, personne n'a calculé les 40
milliards
- de chiffres binaires de Pi qui précèdent (on y
arrivera sans
- doute dans quelques années, mais, pour l'instant, c'est
impos-
- sible ou d'un coût tellement énorme que personne
ne peut se
- payer cette folie). Tout récemment, le
7
octobre 1996,
Fabrice
- Bellard, de
IRISA à Rennes, en utilisant les mêmes
- techniques, a réussi à atteindre le 400
milliardième chiffre
- binaire de Pi, qui est aussi un '1 ' suivi cette fois de
- 001110000111000. Pour le calcul de tous les chiffres de Pi, la
- nouvelle formule n'est pas exceptionnelle (comparée
à
- d'autres, par exemple, dues à Ramanujan). Voici ce
qu'on trouve
- en calculant la somme P(n) des n premiers termes de la somme
- infinie:
-
- P(1)=3.141422466422466422466422. .
.
- P(2)=3.141587390346581523052111...
- P(3)=3.141592457567435381837004. .
.
- P(4)=3.141592645460336319557021...
- P(5)=3.141592653228087534734378. .
.
- P(50)=3.141592653589793238462643383279502884197.
-
- LES CHIFFRES, MAIS PAS LES
DÉCIMALES
-
- Indiquons tout de suite qu'aucune formule analogue à
celle-ci
- n'a été trouvée permettant
d'accéder rapidement aux chiffres
- décimaux (c'est-à-dire en base 10) de
indépendamment les uns des
- autres. Si c'est Pi en base 10 qui vous intéresse, rien
ne vous
- permet encore de connaître la quarante
milliardième décimale
- sans avoir calculé celles qui précèdent
et donc, à moins de
- battre très sensiblement le record actuel, cette
quarante
- milliardième décimale vous restera inconnue. En
revanche, le
- passage de la base 2 à la base 4 ou 8 (ou plus
généralement 2^n)
- peut se faire par petits bouts (on regroupe les chiffres), et
- inversement de la base 2^n à la base 2. Les
premières tentatives
- (déjà très sérieuses) pour trouver
une formule analogue à la
- nouvelle, mais adaptée à la base 10, ont pour
l'instant échoué.
- En
décembre
1996, une méthode de calcul individuel des chiffres
- décimaux de Pi n'utilisant que très peu de
mémoire (comme celle
- détaillée ici pour les chiffres binaires) a
été proposée par S.
- Plouffe. Cette astucieuse méthode est fondée sur
une ancienne
- formule de calcul de Pi et sur des propriétés
particulières des
- coefficients du binôme de
Newton.
Avec cette méthode, la
- consommation d'une petite quantité de mémoire
doit malheureuse-
- ment se payer par une durée de calcul bien plus grande
qui en
- empêche l'utilisation pratique pour battre de nouveaux
- records. Des améliorations de la méthode ne sont
toutefois pas
- impossibles: en ce qui concerne la base 10, les espoirs se
- concrétisent. La formule de Bailey-Borwein-Plouffe (que
nous
- appellerons BBP) aurait pu être découverte depuis
des siècles,
- notamment par
Euler,
qui en a trouvé tant de merveilleuses. En
- effet, rien dans sa démonstration n'est délicat
ni extraordi-
- naire: la difficulté était d'imaginer
l'existence d'une telle
- formule, et de l'écrire. ll a fallu attendre 1995. La
formule
- BBP connue, d'autres formules analogues ont été
découvertes en
- quelques mois, pour toutes sortes de constantes
mathématiques:
- comme bien souvent dans le domaine scientifique, quand un coin
- du voile a été soulevé par une
équipe, géniale ou chanceuse, tout un pan de
montagne
- nouveau apparaît. C'est un véritable filon qu'a
déterré l'équipe
- de l'Université Simon
Fraser, et l'on n'a pas fini de faire
- marcher la pelle et la pioche. Peut-être d'ailleurs que
ce filon
- contient des diamants plus gros que celui déjà
extrait:
- I'effervescence règne. Nous allons expliquer pourquoi
la for-
- mule BBP permet le calcul du 400 milliardième chiflre
binaire
- de Pi sans avoir à calculer ceux qui
précèdent. Pour la
- comprendre, il suffit de savoir compter et de maîtriser
le jeu
- des retenues dans une addition. Comme nous sommes plus habi-
- tués à manipuler des nombres écrits en
base 10 qu'en base 2 ou
- 16, nous expliquerons les idées du calcul avec des
exemples en base 10.
- Évidemment ces explications s'adaptent à toutes
les autres
- bases, et c'est en définitive en base 16 (et donc 2)
qu'elles
- sont vraiment utiles.
-
- COMMENT ON UTILISE LA FORMULE
BBP
-
- L'explication s'organise autour de quatre idées.
-
- Idée 1.
Lorsque l'on additionne de très grands nombres (par
exemple, deux
- nombres de 200 chiffres chacun), on peut savoirce qui se passe
- vers le milieu sans avoir à calculer beaucoup: le
calcul d'une
- seule addition des deux chiffres en position 100 ne sera pas
- toujours suffisant,mais il n'y a pas besoin de grand-chose de
plus. Imaginons que
- nous voulions connaître le chiffre en position 100 de
l'entier
- obtenu en additionnant le nombre de 200 chiffres X= abc
qui
- comporte les chiffres décimaux a, b et c en position
100, 101 et
- 102 avec le nombre Y = a'b'c' qui, lui,
possède les
- chiffres décimaux a', b' et c' en position 100,101 et
102.
-
-
- Tout est une question de retenues. Supposons qu'on calcule la
- somme des deux entiers abc et a'b'c' comme on le ferait pour
une
- addition habituelle de deux nombres entiers à trois
chiffres et
- qu'on obtienne a"b"c". Posons-nous la question: quand a"
est-il
- bon? C'est-à-dire: quand a" est-il le chiffre qu'on
obtien-
- drait en position 100 en faisant complètement
l'addition des
- 200 chiffres de X et des 200 chiffres de Y? La réponse
est
- simple: a" sera bon sauf si b+b'=9 et c+c'=9, car alors, tout
dépendra
- de ce qui se passe à droite dans la grande addition.
S'il y a
- une retenue à reporter, celle-ci se propagera jusqu'au
a +
- a' qu'il faudra changer, sinon elle ne se propagera pas. De
- cela, il résulte que, sauf malchance (au plus une fois
sur 100),
- on tombera sur le bon chiffre a" dans l'addition en se
- contentant de calculer avec trois additions de deux chiffres.
De
- plus, si malchance il y a, on le saura et on pourra donc aller
- voir un peu plus à droite et calculer avec quatre ou
cinq
- chiffres pour être certain d'avoir le bon a". Donc,
à condition
- d'aller voir un peu à droite (mais pas bien loin), on
est cer-
- tain de ce qu'on calcule au milieu de la grande addition sans
- avoir à la faire entièrement. Ce principe
s'applique aussi
- quand on additionne successivement plusieurs grands entiers ou
- quand on multiplie un grand entier par un petit entier (on
- appelle ainsi un entier de quelques chiffres, 30 ou 50 au
plus):
- on sait avec certitude ce qui se passe au milieu en se
- contentant de calculer un peu à droite de ce qui nous
intéresse.
- «Un peu», en pratique, signifie quelques dizaines de
chiffres,
- mais qu'est-ce qu'un calcul sur 30 chiffres ou 50 chiffres
- lorsqu'on évite la manipulation de milliards de
chiffres. Nous
- venons de voir qu'on peut additionner localement de grands
- entiers ou multiplier localement un grand entier par un petit.
- En revanche, ce n'est pas vrai pour la multiplication de deux
- grands entiers ou pour la division (sinon, il y a longtemps
qu'on
- saurait calculer les chiffres de Pi par le milieu).
-
- Idée 2.
On peut calculer le n-ième chiffre (pensez à n
- égal à 10 milliards), d'un nombre de la forme
1/(k*16^i) en base
- 16 en ne faisant qu'une série de petits calculs. Pour
faciliter
- la compréhension, comme précédemment,
nous nous pla&cdedil;ons en
- base 10, et nous allons expliquer comment on peut calculer le
- n-ième chiffre décimal de 1 /(k*10^i) en ne
faisant que des
- petits calculs. Prenons n = 1 000 (pour alléger un
peu), i = 35,
- k = 49. Nous voulons calculer le 1000e chiffre décimal de
- 1/(49*10^35). Chacun sait que, pour multiplier un nombre
décimal
- par 10, il suffit de décaler la virgule d'un chiffre
vers la
- droite. Donc, le 1 oo0e chiffre décimal de 1/(49*10^35)
est le
- 999ième chiffre de 1/(49*10^34), qui est ie 998e de
1/(49*10^33), etc.
- Donc, finalement, on a à calculer le 965e chiffre de
1/49. En
- utilisant encore le principe du décalage, on trouve que
ce
- chiffre est le même que le premier chiffre après
la virgule de 10^964/49.
-
- Imaginons que nous réussissions à calculer le
reste de la
- division de 10^964 par 49 sans avoir à manipuler de
grands
- nombres (c'est l'idée 3), alors: 10^964 = 49 q + r,
avec q
- entier et r < 49, et donc :(10^964)/49 = q+ r/49. Puisque q
est un
- entier, le premier chiffre après la virgule de 1
o964/49 est le
- même que le premier chiffre après la virgule de
r/49, ce qui
- est facile à déterminer (car r< 49) en
faisant la division
- (qui est une division entre petits entiers). Donc, au total
- (sous réserve qu'on puisse facilement calculer le reste
de la
- division de 10^964 par 49), nous savons comment calculer le
1000e
- chiffre décimal de 1/(49*10^35) et, plus
généralement,
- n'importe quel chiffre isolé, même très
loin en base p, d'un
- nombre de la forme 1/(n*p^i) si n est un petit entier.
-
- Idée 3.
- Le calcul du reste de la division de 10^964 par 49 est facile
- et peut se faire sans avoir à manipuler de grands
nombres. Pour
- calculer ce reste, on utilise cette «arithmétique
modulo 49», qui
- consiste à soustraire 49 autant de fois que c'est
nécessaire dès
- qu'on l'a dépassé. Par exemple, 35 + 45 = 80 =
31, 3 x 45 = 135
- = 37, etc. Le calcul du reste de la division de 10^964 par 49
- est alors ramené au calcul de 10964 dans cette
«arithmétique
- modulo 49» où le module d'une somme est la somme
des modules,
- etc., et l'on procède comme suit. Calcul de proche en
proche de
- 10^2, 10^4, 10^8, etc., modulo 49: 10^2 = 100 = 2; 10^4= 2^2 =
4;
- 10^8 = 4^2= 16; 10^16 = 16^2 = 256 = 11 ; 10^32 = 11^2 = 121 =
23;
- 10^64= 23^2= 529 = 39; 10^128 = 39^2= 1521 = 2; 10^256= 2^2=
4; 10^512= 4^22= 16.
- Décomposition de 964 en somme de puissance de 2:
- 964=512+256+128+64+4
- 10^964 =10^(512 + 256 +128 + 64 +4) =16 x 4 x 2 x 39 x 4 = 25.
- On n'utilise que des petits nombres, et aucune
- manipulation n'est vraiment longue (même si, à la
place de 1000,
- on avait mené les calculs avec dix milliards).
|