C'est suite à un défi lancé par mon professeur de mathématiques à ma classe que j'écris cet article. Le défi était le suivant : calculer, dans un premier temps, 10 000 décimales de racine carrée de 2, puis, par la suite, un milliard, le tout en faisant appel, bien sûr, à la programmation. Pour dire vrai, je ne suis arrivé qu'à trouver les 10000 premières décimales, le programme mettant trop de temps après (environ 2 ans pour un milliard de décimales). Ce post a alors pour simple but de donner un début de réponse aux personnes qui, comme moi, ont passé du temps à trouver comment calculer les décimales de racine carrée de 2.

La méthode de Newton - Raphson

Pour calculer les décimales de racine carrée de 2, basons nous sur la méthode de Newton-Raphson. Cette méthode permet de manière approchée de calculer les racines d'un polynome et ce grâce à la formule suivante :

$$u_{n+1} = u_{n} - \frac{f(u_{n})}{f'(u_{n})}$$

avec \(u_0\) n'importe quel nombre, de préférence assez proche de la vraie valeur de la racine. Comme nous voulons calculer la racine carrée de 2, \(f(x) = x^{2} - 2\) ce qui nous donne si nous développons :

$$u_{n+1} = u_{n} - \frac{u_{n}^{2} - 2}{2u_{n}} = \frac{2u_{n}^{2} - u_{n}^{2} + 2}{2u_{n}} = \frac{u_{n}^{2} + 2}{2u_{n}}$$

La formule que l'on obtient pourrait très bien faire l'affaire et être utilisée dans notre programme. Toutefois, le problème des divisions est leur imprécision : si, imaginons, nous voulons calculer 10000 décimales de racine carrée de 2, cela veut dire que, à chaque division, il faudrait calculer au moins 10000 décimales pour être sûr d'obtenir un résultat juste à la fin, ce qui ralentirait considérablement le programme.

Par conséquent, il nous faut laisser \(u_{n+1}\) sous forme de fraction pour ne pas avoir besoin de faire de petite division à chaque itération, mais plutôt une grosse à la fin. Ecrivons donc \(u_{n}\) sous forme de division de 2 suites comme suit :

$$u_{n} = \frac{p_{n}}{q_{n}}$$

ce qui nous donne :

$$u_{n+1} = \frac{p_{n+1}}{q_{n+1}} = \frac{\frac{p_{n}}{q_{n}}^{2} + 2}{2 \times \frac{p_{n}}{q_{n}}} = \frac{p_{n}^2 + 2 \times q_{n}^2}{2 \times p_{n} \times q_{n}}$$

c'est à dire :

$$\begin{cases} p_{n+1} = p_{n}^2 + 2 \times q_{n}^2 \\ q_{n+1} = 2 \times p_{n} \times q_{n} \end{cases}$$

Le programme

Avant de passer au programme, il nous faut juste étudier rapidement la vitesse de convergence de la suite, c'est à dire essayer de déterminer jusqu'à quel rang de la suite il nous faut aller pour obtenir un certain nombre de décimales de racine carrée de 2 juste. Voici donc un petit tableau répertoriant le nombre de décimales justes pour les 10 premiers rangs de \(u_{n}\) :

Nous pouvons remarquer que à chaque itération, le nombre de décimales justes double au minimum, la suite est donc à peu près quadratique. Après ces calculs, voici le programme que l'on obtient :

import math
import decimal
p, q = 2, 1
nbDecimale = 100000
nbIt = math.ceil(math.log(nbDecimale, 2))
decimal.getcontext().prec = nbDecimale + 1
for i in range(1, nbIt + 1):
    p, q = p * p + 2 * q * q, 2 * q * p
fichier = open("decimales.txt", "w")
fichier.write(str(decimal.Decimal(p) / decimal.Decimal(q)))
fichier.close()
print("Les décimales ont été écrites dans 'fichier.txt'.")

La bibliothèque ''decimal'' permet de faire une division avec un nombre de décimales voulu, défini à la ligne 9 dans le programme. J'ai aussi préféré écrire les décimales dans un fichier car les afficher à l'écran faisait planter le programme et le ralentissait énormément.

On peut remarquer que le programme calcule rapidement, en moins d'une seconde, les 10 000 premières décimales de racine carrée de 2, mais après, il ralentit notablement : environ 10 secondes pour 100 000 et 10 minutes pour 1 000 000. Ce ralentissement est dû, je pense, au nombre de décimales à calculer, mais aussi à la taille de la fraction finale, car plus on veut de décimales, plus on fait d'itérations et plus le numérateur et dénominateur deviennent grands.

Comme La solution que je viens de vous montrer n'est pas LA solution pour calculer les décimales de racine carrée de 2, je suis à l'écoute de toutes informations ou de tout algorithme. N'hésitez donc pas à faire part de vos remarques en commentaire.