Extraction de la racine carrée par la méthode de Friden

Cette méthode est extrêmement originale, elle a été développée dans les années 50 pour la machine à calculer Friden SRW, qui fut la première et seule machine à calculer mécanique à pouvoir extraire une racine carré de 10 chiffres en 9 secondes ! Et cela en n'effectuant que des soustractions...

Cette méthode se base sur le fait que la somme des n premiers nombres impairs est égale à n². (voir nombre polygones)

1 = 1²
1 + 3 = 4 = 2²
1 + 3 + 5 = 9 = 3²
1 + 3 + 5 + 7 = 16 = 4²
1 + 3 + 5 + 7 + 9 = 25 = 5²
1 + 3 + 5 + 7 + 9 + 11 = 36 = 6²
etc...,

La formule générale est :

Cette formule se démontre très facilement, on ajoute S_n à lui-même, en prenant pour le premier les termes dans l'ordre croissant et pour le second les termes dans l'ordre décroissant, et on additionne terme à terme, comme suit :

La méthode de Friden fonctionne comme suit:

On soustrait successivement les nombres impairs 1, 3, 5, ... du nombre dont on veut calculer la racine carrée entière.
Il suffit de compter combien de nombres impairs on peut soustraire du nombre donné, ce nombre sera la racine carré.

En effet, soit A le nombre dont on cherche la racine, supposons que l'on sache soustraire n nombres impairs, mais pas n+1.

c'est-à-dire:
                A - 1 - 3 - 5 - ... - (2n-1)  ≥ 0
mais        A - 1 - 3 - 5 - ... - (2n-1) - (2n+1) < 0

or on sait que la somme des n premiers nombres impairs est n².

Donc       A - n² ≥ 0
et             A - (n+1)² < 0

Ou encore   n² ≤ A < (n+1)²

C'est-à-dire que n est la racine carrée entière de A.

Ex. : soit 135. on soustrait les nombres impairs à partir de 1 et on compte combien de fois on peut effectuer l'opération :

1. 135 - 1 = 134
2. 134 - 3 = 131
3. 131 - 5 = 126
4. 126 - 7 = 119
5. 119 - 9 = 110
6. 110 - 11 = 99
7. 99 - 13 = 86
8. 86 - 15 = 71
9. 71 - 17 = 54
10. 54 - 19 = 35
11. 35 - 21 = 14

On a pu effectuer 11 soustractions, donc 11 est la racine carrée entière de 135.

Méthode de Friden pour les grands nombres.

Bien sûr, pour un nombre plus grand tel que 34.154.215, on ne peut pas s'amuser à soustraire tous les nombres impairs à partir de 1, car il faudrait faire 5844 soustractions. Il faut donc légèrement améliorer l'algorithme.

N.B.: La notation [ab] indique a.10+b, [abc] = a.10²+b.10+c,  [abcd] = a.10³+b.10²+c.10+d, etc... [a] est égal à a.

Pour les grands nombres on travaille comme suit:

1. On décompose le nombre en tranches de deux chiffres à partir de la droite. Soit p le nombre de tranches
2. On soustrait successivement 1.10^2p, 3.10^2p, 5.10^2p, 7.10^2p, ... du nombre de départ et on compte le nombre de fois que l'on peut soustraire, soit a_p ce nombre, celui-ci est le premier chiffre  de la racine carrée.
3. On multiplie le chiffre précédant par 20 et on ajoute 1, ce qui donne 20a_p+1.
4. On soustrait successivement (20a_p+1)10^2p-2, (20a_p+3)10^2p-2, (20a_p+5)10^2p-2, (20a_p+7)10^2p-2, ... du nombre restant de l'étape 2 et on compte le nombre de fois que l'on sait soustraire, soit a_p-1 ce nombre, celui-ci est le chiffre suivant de la racine carré. Les deux premiers chiffres de la racine carrée sont [a_pa_p-1].
5. On multiplie [a_pa_p-1] par 20 et on ajoute 1, ce qui donne 20[a_pa_p-1]+1.
6. On soustrait successivement (20[a_pa_p-1]+1)10^2p-4, (20[a_pa_p-1]+3)10^2p-4, (20[a_pa_p-1]+5)10^2p-4, (20[a_pa_p-1]+7)10^2p-4, ... du nombre restant de l'étape 4 et on compte le nombre de fois que l'on sait soustraire, soit a_p-2 ce nombre, celui-ci est le chiffre suivant de la racine carré. Les trois premiers chiffres de la racine carrée sont [a_pa_p-1a_p-2].
7. On multiplie [a_pa_p-1a_p-2] par 20 et on ajoute 1, ce qui donne 20[a_pa_p-1a_p-2]+1.
8. On soustrait successivement (20[a_pa_p-1a_p-2]+1)10^2p-6, (20[a_pa_p-1a_p-2]+3)10^2p-6, (20[a_pa_p-1a_p-2]+5)10^2p-6, (20[a_pa_p-1a_p-2]+7)10^2p-6, ... du nombre restant de l'étape 6 et on compte le nombre de fois que l'on sait soustraire, soit a_p-3 ce nombre, celui-ci est le chiffre suivant de la racine carré. Les quatre premiers chiffres de la racine carrée sont [a_pa_p-1a_p-2a_p-3].
9. Etc... jusqu'à ce que l'on ait le nombre de chiffres voulus, soit [a_pa_p-1a_p-2...a₁a₀].

Ex.: soit 254.142.047.

1. On décompose le nombre en tranche de deux chiffres, soit 4 tranches.

2.54.14.20.47

    2.   On soustrait 1.10⁸ = 1.00.00.00.00, 3.00.00.00.00, 5.00.00.00.00, ... du nombre précédant.

2.54.14.20.47
1.00.00.00.00
-------------------
1.54.14.20.47

           On sait soustraire 1 fois, donc le premier chiffre est 1.

    3.   On calcule 1.20+1 = 21

    4.  On soustrait 21.10⁶ = 21.00.00.00, 23.10⁶ = 23.00.00.00, 25.00.00.00, etc..., du dernier nombre calculé en 2.

1.54.14.20.47
   21.00.00.00
-------------------
1.33.14.20.47
   23.00.00.00
-------------------
1.10.14.20.47
    25.00.00.00
--------------------
    85.14.20.47
    27.00.00.00
--------------------
    58.14.20.47
    29.00.00.00
--------------------
    29.14.20.47

On sait donc soustraire 5 fois, les deux premiers chiffres de la racine carrée sont donc 15.

    5.  On calcule 15.20+1 = 301.

    6.  On soustrait 301.10⁴ = 301.00.00, 303.10⁴ = 303.00.00, 305.10⁴ = 305.00.00, etc... du dernier nombre calculé en 4.

29.14.20.47
  3.01.00.00
----------------
26.13.20.47
  3.03.00.00
----------------
23.10.20.47
  3.05.00.00
----------------
20.05.20.47
  3.07.00.00
-----------------
16.98.20.47
  3.09.00.00
----------------
13.89.20.47
  3.11.00.00
----------------
10.78.20.47
  3.13.00.00
----------------
  7.65.20.47
  3.15.00.00
----------------
  4.50.20.47
  3.17.00.00
----------------
  1.33.20.47

On a fait 9 soustractions, les trois premiers chiffres sont donc 159.

    7.  On calcule 159.20 + 1 = 3181.

    8.  On soustrait 3181.10² = 31.81.00, 31.83.00, 31.85.00, etc... du nombre restant en 6.

1.33.20.47
   31.81.00
--------------
1.01.39.47
   31.83.00
--------------
   69.56.47
   31.85.00
--------------
   37.71.47
   31.87.00
--------------
     5.84.47

On a pu effectuer 4 soustractions, donc les quatre premiers chiffres sont donc 1594.

    9.  On calcule 1594.20+1 = 31881.

   10.  On soustrait 31881, 31883, 31885, etc... du nombre restant en 8.

5.84.47
3.18.81
----------
2.65.66

On a  soustrait 1 fois, donc la racine carrée est 15941.

Démonstration de la méthode.

Soit N le nombre que l'on décompose en tranche de deux chiffres.

N = 10^2p.n_p + 10^2p-2.n_p-1+10^2p-4.n_p-2+...+10².n₁+n₀

On soustrait 1.10^2p, 3.10^2p, etc... et on constate qu'on peut soustraire a_p fois (mais pas a_p+1)

C'est-à-dire que a_p².10^2p ≤ N < (a_p+1)².10^2p, ou a_p.10^p ≤ √N < (a_p+1).10^p. Le nombre restant après soustraction est N - a_p².10^2p

Dans l'itération suivante on essaye de trouver le chiffre suivant a_p-1.

ou a_p.10^p + a_p-1.10^p-1 ≤ √N < a_p.10^p + (a_p-1+1).10^p-1

en élevant au carré

a_p².10^2p + 2.a_p.a_p-1.10^2p-1 + a_p-1².10^2p-2 ≤ N

ou encore

2.a_p.a_p-1.10^2p-1 + a_p-1².10^2p-2 ≤ N - a_p².10^2p

ou (20.a_pa_p-1+a_p-1²).10^2p-2 ≤ N - a_p².10^2p

Or, 20.a_pa_p-1+a_p-1² = (20.a_p + 1) +  (20.a_p + 3) +  (20.a_p + 5) + ... +  (20.a_p + (2.a_p-1 - 1) )       a_p-1 termes.

Donc si on soustrait successivement (20.a_p + 1) .10^2p-2, (20.a_p + 3).10^2p-2, etc... du nombre N - a_p².10^2p, il y aura a_p-1 soustractions possibles.

Le nombre restant après soustraction sera N - a_p².10^2p - (20.a_pa_p-1+a_p-1²).10^2p-2 ou N - (a_p.10^p + a_p-1.10^p-1)² ou encore N - [a_pa_p-1]².10^2p-2

on essaye de trouver le chiffre suivant a_p-2.

tel que [a_pa_p-1].10^p-1 + a_p-2.10^p-2 ≤ √N < [a_pa_p-1].10^p-1 + (a_p-2+1).10^p-2

en élevant au carré

[a_pa_p-1]².10^2p-2 + 2.[a_pa_p-1].a_p-2.10^2p-3 + a_p-2².10^2p-4 ≤ N

ou encore

2.[a_pa_p-1].a_p-2.10^2p-3 + a_p-2².10^2p-4 ≤ N - [a_pa_p-1]².10^2p-2

ou (20.[a_pa_p-1].a_p-2+a_p-2²).10^2p-4 ≤ N - [a_pa_p-1]².10^2p-2

Or, 20.[a_pa_p-1].a_p-2+a_p-2² = (20.[a_pa_p-1]+1) +  (20.[a_pa_p-1] + 3) +  (20.[a_pa_p-1] + 5) + ... +  (20.[a_pa_p-1] + (2.a_p-2 - 1) )       a_p-2 termes

Donc si on soustrait successivement (20.[a_pa_p-1] + 1).10^2p-4 , (20.[a_pa_p-1] + 3).10^2p-4, etc... du nombre N - [a_pa_p-1]².10^2p-2, il y aura a_p-2 soustractions.

Le nombre restant après soustraction sera N - [a_pa_p-1a_p-2]².10^2p-4

Etc... jusqu'à obtenir la racine carrée [a_pa_p-1a_p-2...a₁a₀], le reste sera N - [a_pa_p-1a_p-2...a₁a₀]².

 

 
Dernière mise à jour, le 29 Janvier 2007