mercredi 30 mars 2011

Calculer les décimales de pi

Disclaimer : Attention pour Maths-lovers. Et je pars du principe que comme toute personne fréquentable, vous savez ce qu'est $\pi$ (sinon voir à la fin de cet article).

by Xan2-3


J'ai commencé ce billet il y a deux semaines, et je voulais le publier pour le pi day, le mardi 14 mars (3.14 héhé). Mais bon, j'ai été entrainé dans un tourbillon de tâches qui m'ont aspiré loin de mon blog.


Attention, je ne veux pas faire un énième billet pour rendre hommage à cette constante, ou vous expliquer la beauté, l'histoire, etc.

Non j'ai envie de faire quelque chose de différent. Je me suis rendu compte le 14 mars dernier que je connais beaucoup de gens qui aime réciter les décimales de $\pi$. Oui j'ai un entourage bizarre, à croire que je les attire ! Mais je suis sûr que beaucoup de gens ne savent pas comment on calcule ces décimales.

Attention 2, je ne vais pas lister toutes les formules utilisées pour calculer $\pi$, il y en a vraiment beaucoup trop. Je vais juste exposer les méthodes que j'ai personnellement utilisé à différentes occasions, que je pense représentatives de ce qui se fait, et surtout qui sont à mon avis accessibles à beaucoup de gens. Pour les gens qui veulent avoir une liste assez longue, je renvoie vers l'article wikipédia sur les approximations numériques de $\pi$, et aussi vers l'article correspondant sur MathWorld de Wolfram (la papa de Mathematica)

Le nombre est assez délicat à calculer principalement pour 2 raisons:
  1. Ce n'est pas un nombre rationnel, c'est-à-dire qu'il ne s'écrit pas comme une fraction de deux entiers (comme 4/5 ou 154/21). Il ne suffit donc pas de faire une division.
  2. C'est un nombre transcendant, et donc on ne peut pas trouver une formule sous forme de racine d'un polynôme. Par exemple, quand on essaye de calculer la racine x d'un polynôme d'ordre 2 tel que $a x^2+b x + c =0$, on obtient une jolie formule pour x en fonction de a b c qui permet de le calculer simplement. Avec $\pi$, c'est pas possible, ben non !
Depuis que des gens se sont rendus compte que ce nombre magique existe, plusieurs moyens ont été mis en œuvre pour arriver à en déduire la valeur.

En passant par le périmètre

L'une des premières méthodes a consisté a chercher des approximations géométriques. En temps normal, $\pi$ sert à calculer le périmètre d'un cercle avec la célèbre formules $P=2 \pi R $, avec R le rayon du cercle. C'est d'ailleurs en comparant le périmètre et le diamètre que les anciens se sont rendus compte qu'ils retombaient sur le même nombre.

Une première approche bête et méchante : on dessine un cercle, et on utilise une petite corde pour mesurer le périmètre, et une règle pour mesurer le diamètre, puis on utilise la relation $\pi = P/D$.

Si vous vous amusez à la faire, vous allez vous rendre compte qu'il est difficile de mesurer précisément le périmètre d'un cercle. C'est la raison pour laquelle quelqu'un d'aussi malin qu'Archimède a préféré mesuré le périmètre d'un objet qui ressemble de loin à un cercle, mais qui est facile à manipuler : le polygone régulier avec n côtés.

Gisling sous licence CC-by-sa
Par exemple, pour l'hexagone avec n=6 côtés (en vert), $\pi=3$, puisqu'il est constitué de 6 triangles équilatéraux, ce qui implique que le rayon = un côté, et donc que le périmètre = 6 x rayon = 3 x diamètre !

Plus on rajoute de côté, plus le polygone ressemble au cercle, plus $P/D$ tend vers la bonne valeur de $\pi$. Avec 96-gone, Archimède trouve $\pi=3.1418$

En passant par la surface

On peut raffiner un peu plus, et passer par le calcul de la surface, avec la relation $S=\pi R^2$, soit en utilisant toujours les polygones, soit en passant par une méthode beaucoup plus fun : la méthode Monte-Carlo, un des algorithme de calcul scientifique les plus utilisés (au moins en physique), et inspirée des aiguilles de Buffon (18ème siècle !!!).

L'idée de base, c'est qu'une surface c'est rien d'autre qu'une infinité de points, comme le montre la belle image récupérée sur wikipédia

CailinJo sous licence CC-by
La surface d'un carré de côté $D$ vaut $S_{carre}=D^2$, et la surface du cercle vaut $S_{cercle}=\pi \left( \frac{D}{2} \right)^2$, donc le quotient $S_{cerle}/S_{carre}=\frac{\pi}{4}$ magique !

Donc tout ce que fait l'algorithme, c'est remplir de points le carré, et calculer le nombre de points qui tombe dans le cercle. Très facile à faire, on tire les coordonnées d'un point au hasard, et on vérifie que la distance du point au centre du cercle est inférieur au rayon (je vous laisse visualiser). Si on a $N_{cercle}$ points à l'intérieur du cercle, alors $\pi=N_{cercle}/N_{total}$. Personnellement j'aime beaucoup cet algorithme...


Avec du vrai calcul (trigonométrique)


J'ai commencé par les méthodes géométriques parce qu'elles font moins peur en général aux gens, surtout grâce aux images qui les illustrent. Mais il faut bien comprendre que ces méthodes sont très lentes, et il faut beaucoup de temps et de calculs avant d'arriver à beaucoup de chiffres après la virgule. Les méthodes Monte-Carlo sont connues pour converger lentement (je vous ai trouvé un exemple ici), c'est pour ça qu'elles ne sont en général utilisées que dans des calculs à plusieurs dimensions, où elles sont redoutablement efficaces.

Les pros, les vrais, ceux qui n'ont peur de rien, utilisent plutôt des formules de séries numériques. N'ayez pas peur, une série, c'est juste une addition d'une infinité de termes. Par exemple $1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+...= \sum_{n} \left( \frac{1}{2})^n$ est une série (célèbre) dont la somme infinie qui tend vers 2.

On peut également avoir des séries qui dépendent d'une variable par exemple une autre série célèbre est la fonction exponentielle $e^x=\sum_n \frac{x^n}{n!}=1+x+\frac{x^2}{2}+...$ (on voit tout de suite par exemple que pour $x=0$ $e^0=1$, mais ne vous attardez pas sur les formules si vous ne les comprenez pas, tant que vous comprenez l'idée générale), ou alors la série de la fonction arctangente $\arctan x=x-\frac{x^3}{3}+\frac{x^5}{5}-\frac{x^7}{7}+... $, qui est celle qui va justement nous permettre de calculer $\pi$, grâce à la formule de Machin (on ne rigole pas ! c'est son nom). Dans ma vie de tous les jours, quand je veux utiliser $\pi$ dans un programme, je lui demande simplement de calculer $\pi=4 \arctan 1$, mais John Machin lui n'avait pas de calculatrice ni d'ordinateur, ce qui ne l'a pas empêché de calculer $\pi$ à 100 chiffres après la virgule en utilisant une formule dérivée $\frac{\pi}{4}=4 \arctan \frac{1}{5}-\arctan \frac{1}{239}$, et de calculer les $\arctan$ avec la série ci-dessus.

Si ça vous dit, il y a différents codes pour différents langages qui permettent de calculer pi sur codecodex.com, qui utilisent cette formule de Machin.
Mais si vous ne voulez pas le calculer vous-mêmes, vous pouvez toujours apprendre le petit poème, ou alors carrément mémoriser  les 4 premiers millions de chiffres après la virgule...



Bonus (parce que je suis gentil)


Pour ceux qui ne savent vraiment pas ce qu'est pi :




Et pour ceux qui veulent un algorithme de champions, voir ce délicieux blog de maths que je recommande chaudement !

L'auteur

Ma photo
Blog à caractère expérimental, servant de support de réflexion et d'expression à un robot de l'espace !

Dozosphère