Chuck Norris connaît la dernière décimale de π
C'est un "2".
Mais il joue un peu sur les mots, puisqu'il parle de la décimale récurrente du développement décimal de π dans une base à pas variable... Malin, le Chuck Norris !
Histoire de continuer ce triptyque d'articles sur π, découvrons ensemble l'algorithme compte-goutte, qui n'a jamais vraiment révolutionné le calcul de π, mais qui est assez chouette à mettre en place.
La série d'Euler
Tout commence au XVIIIe siècle, avec Leonhard Euler (celui qui a réussi à déposer son nom dans tous les domaines des maths...). Il découvre, entre beaucoup d'autres, l'égalité suivante :
Sur le coup, Euler en profite pour calculer une vingtaines de décimales. Soit.
Revenons aux décimales de π : elles sont [3;1,4,1,5,...], dans la base 10 que l'on utilise tous les jours. La base 10 correspond à la base [1/10, 1/10, 1/10, 1/10, ...], "à pas fixe". En effet, écrire π=3.1415... revient à écrire
La base 10 n'est pas une base commode pour exprimer le nombre π. Par contre, la formule d'Euler nous indique une alternative intéressante : la base b=[1/3, 2/5, 3/7, 4/9, ...] "à pas variable". En effet, quand on réécrit sa formule en factorisant successivement par 1/3, 2/5, 3/7 etc., on trouve :
Autrement dit : dans la base b, on a π = 2,22222... : Le développement b-cimal de π n'est qu'une suite du chiffre 2 !
L'algorithme compte-gouttes
"Oui, mais, c'est trop facile, ce qui m'intéresse, moi, ce sont les décimales décimales, pas les décimales b-cimales !"
J'y arrive ! Maintenant qu'on a l'expression de π dans une base donnée, il n'y a plus qu'à le transformer dans une autre base, comme la base 10 par exemple. Le processus à mettre en place est plutôt simple : il suffit de remplir le tableau suivant (que je vous présente dans sa version déjà remplie). Si vous voulez calculer N décimales de π, il va falloir prendre un tableau de largeur 3.4×N, arrondi à l'entier supérieur.
Avant toute chose, il faut commencer par remplir les 3 premières lignes du tableau. La ligne A et la ligne B correspondent aux numérateurs et dénominateurs des fractions de la base b. Ici, c'est 1/3, 2/5, 3/7, etc. La ligne "Décimales" correspond au développement b-cimal (Pour π, ce ne sont que des 2).
Reste plus qu'à remplir successivement chaque sous-tableau de hauteur 4, de droite à gauche : on commence par remplir la ligne "×10", en multipliant la ligne du dessus par 10, puis on inscrit "0" dans la case la plus à droite de la ligne "Retenue". On procède ensuite par colonne, en partant de la droite :
- Dans la case "Somme", on effectue la somme de la case "×10" et de la case "Retenue"
- Dans la case "Reste", on inscrit le reste de la division de "Somme" par "B".
- Dans la case "Retenue" de la colonne de gauche, on inscrit le quotient de la division, multiplié par "A".
Une fois arrivé à la première colonne, on inscrit dans "Reste" le reste de la division de "Somme" par 10, et on garde de côté le quotient : ça sera une décimale de π.
Si, par hasard, ce chiffre est "10", c'est qu'il faut ajouter 1 à la décimale précédente. Ce phénomène arrivera pour la première fois à la 32e décimale.
On obtient une décimale par sous-tableau rempli, d'où le nom de l'algorithme : les décimales arrivent au goutte à goutte.
En s'appliquant beaucoup, cet algorithme permet de calculer - à la main - une vingtaine de décimales en quelques heures !...
Cet algorithme a été inventé en 1968 pour calculer e, et n'a été adapté à π qu'en 1991. A l'ère de l'informatique, cet algorithme est loin d'être performant, mais s'il avait été découvert plus tôt, il aurait fait un malheur chez tous les calculateurs, puisqu'il ne met en œuvre que de petits entiers, et des opérations simples (pas de multiplications de gros entiers, notamment).
La meilleur preuve que cet algorithme est simple, c'est que j'ai réussi à le programmer en javascript ! Attention tout de même, ne lui demandez pas trop de décimales, ou c'est votre navigateur internet qui va faire la gueule!
π ≈ 3,
Pourquoi ça marche ?
Mais au fait, pourquoi cet algorithme fonctionne ? Grâce à la magie des maths, mais pas que.
Puisque la première ligne "Décimales" correspond à π dans la base b, la première ligne "x10" du sous-tableau correspond à 10π, en base b.
(Par soucis de clarté, les "chiffres" des développement décimaux et b-cimaux seront désormais séparés par des ".")
Mais cette écriture n'est pas normalisée ! Revenons en notation décimale : la multiplication "1,7.4×3" (1.74 × 3) ne donne pas "3,21.12" mais "5,2.2" : on peut tout à fait effectuer la multiplication chiffre par chiffre, mais puisque "21" n'est pas un chiffre en base 10, il faut prendre 1 et garder 2 en retenue.
Dans la base 10, les chiffres acceptables sont entre 0 et 9. Dans la base b, les chiffres acceptés au rang n sont les nombres entre 0 et (2n+1)-1. Ce que l'algorithme se charge de faire, c'est donc d'effectuer le report des retenues, et donc, de normaliser le nombre 20,20.20.20... dans la base b.
On obtient donc, après avoir rempli le premier sous-tableau, l'écriture normalisée en base b de 10π : C'est 30+0,2.2.4.3.10.1.13... (obtenu dans la ligne "Reste"). On trouve donc que 10π commence par 30, et donc que π commence par 3.
L'étape qui suit consiste donc à trouver la première décimale du nombre 10π-30, et ainsi de suite.
Pourquoi initialiser à 3.4×N colonnes ? C'est essentiellement parce que 3.4N b-cimales donneront N décimales...
Et sinon ?
La magie de cet algorithme est surtout de permettre de transformer un nombre écrit dans une base exotique en un nombre écrit dans une base bien plus agréable à manipuler.
Prenons le nombre e, par exemple. La formule qui le définit est :
On peut donc en déduire :
Et finalement, dans la base b = [1/2,1/3,1/4,1/5,...], on a e=1,1111111111.... Le même algorithme compte-gouttes se chargera donc d'en calculer toutes les décimales. Le plus dur est de savoir quelle largeur de tableau il faut prendre pour avoir n décimales exactes :
Tableau moins large pour plus de décimales
On trouve donc e=2.7182...
On pourrait, de la même façon, s'attaquer au nombre d'or, grâce à la formule :
On reconnaît aux numérateurs les (4k+1)-èmes termes de la suite de Fibonacci, et aux dénominateurs aussi, mais décalés.
Ou même à π à nouveau, avec la formule de Bill Gosper :
On reconnait aux numérateurs la suite n(2n-1), aux dénominateurs la suite 3(3n+1)(3n+2), et aux b-cimales la suite 5n+3. L'écriture de π dans la base [1/60,6/168,15/330,...] permet alors à l'algorithme compte-gouttes de donner π à N décimales exactes en initialisant le tableau à seulement N b-cimales. Ce qu'on gagne dans un sens, on le perd dans l'autre : les calculs seront beaucoup moins agréables à effectuer...
Bref, un chouette algorithme qui permet de calculer n décimales de π sans utiliser de gros entiers, avec des temps de calculs proportionnels à n² et des coûts en espaces proportionnels à n...
En fait, le principal intérêt de cet algorithme, c'est qu'il est très facile à coder !
Sources :
Jean-Paul Delahaye, Le fascinant nombre π, Éditions Belin, Pour la Science
L'univers de pi, l'algorithme compte-gouttes