En utilisant la somme des premiers nombres impairs dans l’ordre, on peut définir un algorithme simple de calcul des racines carrées des nombres entiers avec une précision décimale arbitraire.

Calcul de la somme des \(n\) premiers entiers naturels impairs

Il est, curieusement, assez peu connu que la somme des \(n\) premiers nombres entiers naturels impairs vaut \(n^2\), ce qu’on peut voir de deux manières différentes.

La première consiste tout simplement à démontrer le résultat par récurrence sur \(n\geq 1\) : si \(n=1\), le premier entier naturel impair est \(1\), et on a bien \(1=1^2\). Supposant que le résultat est acquis au rang \(n\), c’est-à-dire (puisque le \(n\)-ième entier naturel impair est \(2n-1\)) que \(1+3+\ldots +(2n-3)+(2n-1)=n^2\), on peut alors écrire \(1+3+\ldots +(2n-1)+(2n+1)=n^2+(2n+1)\) (par hypothèse de récurrence) \(=(n+1)^2\) par l’identité remarquable bien connue \((a+b)^2=a^2+2ab+b^2\). Le résultat s’écrit savemment \(\sum_{i=1}^n (2i-1)=n^2\), le signe \(\sum\) (« sigma ») désignant une somme et l’indice \(i\) indiquant qu’on somme toutes les expressions \(2i-1\) obtenues en faisant prendre à \(i\) les valeurs de \(1\) à \(n\).

La seconde méthode consiste à partir de l’expression bien connue de la somme des \(n\) premiers entiers naturels non nuls, donnée par \(\sum_{i=1}^n i=1+2+\ldots+n=\dfrac{n(n+1)}{2}\), et qu’on démontre aussi facilement par récurrence sur \(n\). On remarque alors que la somme des \(n\) premiers entiers naturels impairs, à savoir \(1+2+\ldots +(2n-3)+(2n-1)\), s’écrit aussi comme la différence de \(1+2+\ldots +(2n-1)+2n\) et de \(2+4+\ldots +(2n-2)+2n\). Le second terme de la différence étant le double de la somme des entiers de \(1\) à \(n\), on obtient \(\dfrac{2n(2n+1)}{2}-2\times \dfrac{n(n+1)}{2}=n.(2n+1)-n.(n+1)=n^2\) également.

Identifier la racine carrée par une suite de soustractions

A partir de ce « développement » de \(n^2\), on peut obtenir la racine carrée d’un entier naturel non nul \(n\) par des soustractions successives de nombres impairs. Commençons par le cas où \(n\) est un « carré parfait », c’est-à-dire le carré d’un autre entier naturel \(m\), situation où l’on a \(n=m^2\). Le développement précédent nous donne \(n\) comme la somme des \(m\) premiers nombres impairs, c’est-à-dire \(n=m^2=\sum_{i=1}^m 2i-1=1+3+\ldots + (2m-3)+(2m-1)\). Effectuons alors les soustractions successives à \(n\) des premiers nombres impairs dans l’ordre croissant : la première donne \(n-1\), la seconde (s’il y a lieu) \((n-1)-3=n-4\), la troisième (s’il y a lieu) \((n-4)-5\), et ainsi de suite, jusqu’à obtenir \(0\). Par le développement de \(n=m^2\) en nombres impairs, on s’aperçoit que le nombre de soustractions à effectuer est en fait exactement \(m\), autrement dit on dispose dans ce cas d’un algorithme de calcul de la racine carrée \(m\) de \(n\), qui consiste précisément à compter le nombre de soustractions des premiers entiers impairs à effectuer pour obtenir \(0\).

Mais en général, un entier naturel \(n\) n’est pas toujours un carré parfait. Dans ce cas, on adapte l’algorithme précédent en effectuant les mêmes soustractions successives des premiers entiers naturels impairs dans l’ordre croissant, jusqu’à obtenir le premier résultat négatif. En effet, dans ce cas \(n\) n’est pas une somme des premiers entiers naturels impairs, et on considère le premier entier naturel \(m\) tel que la soustraction de la somme \(1+3+\ldots +(2m-3)+(2m-1)\) des \(m\) premiers entiers naturels impairs, autrement dit de \(m^2\), à \(n\), donne un résultat négatif. On peut alors écrire \(n-m^2<0\), ou encore \(n<m^2\), ce qui se traduit par \(\sqrt n<m\). Or, par définition de \(m\), avant la dernière étape les soustractions successives aboutissaient à un résultat (strictement) positif, ce qu’on peut aussi écrire \(n-(m-1)^2>0\), ou encore \(n>(m-1)^2\), ce qui se traduit par \(m-1<\sqrt n\). On a ainsi obtenu un encadrement entier de la racine carrée de \(n\) sous la forme \(m-1<\sqrt n< m\), où \(m\) est le nombre minimal de soustractions à réaliser pour obtenir un résultat négatif. Dans le cas où \(n=m^2\) est un carré parfait, \(m\) est le nombre de soustractions à réaliser pour obtenir un résultat nul (donc négatif ou nul), si bien que dans tous les cas on a \(m-1<\sqrt n\leq m\), avec \(\sqrt n=m\) dans le cas d’un carré parfait.

Augmenter la précision de l’algorithme

L’algorithme précédent fournit, en général, une approximation de la racine carré à une unité près. Ce n’est pas très satisfaisant, et on peut l’améliorer de la manière suivante. Pour calculer la racine carrée d’un entier \(n\) avec une précision à \(10^{-k}\) (pour \(k\) un entier naturel), il suffit en effet d’appliquer l’algorithme au nombre \(n\times 10^{2k}\) puis de diviser l’encadrement par \(10^k\). On obtient en effet un encadrement de la forme \(m-1< n\times 10^{2k} \leq m\), et comme la racine carrée de \(10^{2k}=(10^k)^2\) est \(10^k\), l’encadrement \((m-1).10^{-k}<n\leq m.10^{-k}\) ! Par exemple, pour calculer la racine carrée de \(2\) avec une précision à \(10^{-1}=1/10\), on applique l’algorithme à \(n=200\). On obtient \(1+3+5+7+9+11+13+17+19+21+23+25+27\) \(=196<200<225\) \(=1+3+5+7+9+11+13+15+17+19+21+23+25+27+29\) : comme il y a \(14\) additions dans la première somme et \(15\) dans la seconde, on peut écrire \(1,4<\sqrt 2 <1,5\), puisque \(\sqrt 2\) est irrationnel.

Pour augmenter la précision du calcul à \(10^{-2}=1/100\), on applique l’algorithme à \(n=20000\). En utilisant par exemple un tableur, on peut programmer très facilement la somme des \(n\) premiers nombres impairs. En remarquant à partir du cas précédent qu’il faudra faire entre \(140\) et \(150\) opérations, on peut évaluer le nombre d’opérations à programmer et le résultat du calcul donne l’encadrement \(141<\sqrt{20000} < 142\), soit \(1,41<\sqrt 2 < 1,42\). Le calcul de racines carrées de petits nombres entiers à des précisions diverses par cette méthode (qui utilise un seul tableur) est assez amusant (on trouve par exemple \(1,73<\sqrt 3 < 1,74\), \(2,23<\sqrt 5 <2,24\) et \(3,16<\sqrt{10}<3,17\)), mais il faut savoir que cet algorithme a été utilisée dans l’ « Arithmaurel », une des premières calculatrices, conçue par le français Timoléon Maurel en 1842. L’incorporation de cet algorithme dans la construction d’une calculatrice est donc l’une des étapes historiques de l’invention de l’ordinateur moderne.

L’Arithmaurel, une des premières calculatrices, conçue par Timoléon Maurel

Source : « Du boulier à la révolution numérique, algorithmes et informatique », Vicenç Torra, Le monde est mathématique, RBA Coleccionables S.A., 2011.