http://f4hla.free.fr/
Méthode Chinoise de résolution des racines carrées
Introduction
Je cherchais une méthode permettant d'extraire la racine carrée d'un nombre quelconque, éventuellement de tête et je suis tombé sur cette méthode attribuée aux Chinois, ce que je n'affirmerais pas.
Par contre, il semble qu'elle ait été enseignée dans les classes françaises à une certaine époque ou une époque certaine, et j'aimerais beaucoup le vérifier. Si vous avez des informations la dessus, n'hésitez pas à m'écrire.
Si mes recherches m'ont donné une méthode je n'avais pas de preuve, donc je vous livre ci-aprés la méthode telle que je l'ai comprise ainsi qu'une démonstration. Si vous déceliez une erreur dans cette dernière, n'hésitez pas à m'en faire part cela fera toujours avancer la science (un petit pas pour moi...)
Enoncé
Soit un nombre N, réel quelconque. On cherche r sa racine carrée positive.
Étape 1 : Décomposer N en nombres à deux chiffres en partant du point (ou de la virgule!!).
On numérotera les nombres obtenus [n1..nk] en partant de la gauche vers la droite.
Étape 2 : Considérer
-x : un chiffre (donc entre 0 et 9)
-c et y : deux entiers, initialisés à 0
Étape 3 : Effectuer récursivement les opérations suivantes:
a - c=c*100+ni
b - chercher x maximum tel que y=x(20*r+x) soit encore inférieur à c
c - r=r*10+x et c=c-y
d - recommencer jusqu'à avoir c=0 et nj=0 pour tout j ou bien jusqu'à avoir assez de décimale.
Note : La virgule (ou le point) de r se trouve à la même place que dans N.
Exemple
N=3333.00
r 5 7 .7 3
__ __ __ __ ...
N 33 33 .00 00
y=x*x 25
______
08 33
y=x*10x 7 49
__________
84 00
y=x*114x 80 29
__________
3 71 00
y=x*1154x 3 46 29
...
A la calculatrice, on trouve : r=57.7321...
Preuve
***Hypothèses***
Soit N un réel positif quelconque
Notons :
- N=Sum(ni.100^(m-i), i=1...inf) avec ni entier entre 0 et 99.
- R un entier positif avec R=Sum(xi.10^(m-i), i=1..inf) et xi dans 0..9
- Rk les sous parties de R tel que Rk=Sum(xi.10^(m-i), i=1..k)
On se donne les relations suivantes pour construire R :
- (a) Rk=Rk-1 + xk.10^(m-k) avec xk dans 0..9 et R0=0
et rk=Rk.10^(k-m)
- (b) xk tel que yk(xk)=xk(20.rk-1 + xk)<=ck
(ce qui correspond bien à ce que l'on fait dans le calcul expliqué ci-dessus)
Il faut montrer que :
- (1) Rk->Sqrt(N), k->inf
- (2) Rk est constitué par les k premières décimale de Sqrt(N)
***Démonstration***
Preuve de (2) :
Supposons (1). Supposons que de plus Rk²<=N (3).
Alors (a) montre que (2) est vrai puisque par construction xk est un chiffre.
Preuve de (3) :
(a) indique que Rk est croissante.
Donc si on montre (1) on aura (3)
Preuve de (1) :
(a) => Rk>=0 (d)
(d) => (1)<=>mq Rk²->N : nous allons donc montrer cette dernière relation.
On a rk=Rk.10^(k-m). Alors rk=10.rk-1 + xk selon (a).
Ainsi rk²= xk² + 100.rk-1² + 20.rk-1.xk
= 100.rk-1² + yk(xk)
Par retour à Rk, on a : Rk²=Rk-1² + yk(xk).100(m-k).
Par récurrence, on obtient Rk²=Sum(yi(xi).100(m-i),i=1..k)
Or (c) donne yi(xi) = ci - [ci+1 - ni+1]/100 et l'on tire
Rk² = 100^m.Sum(ci.100^-i - ci+1.100^(-i-1) + ni+1.100^(-i-1), i=1..k)
= 100^m.[c1.100^-1 - ck+1.100^(-k-1) + Sum(ni+1.100^(-i-1), i=1..k)]
Or c1=n1 par construction selon (c) d'où l'on tire :
Rk² = Sum(ni.100^(m-i), i=1..k+1) - ck+1.100^(m-k-1)
(c) et (b) montrent que ck>=0 donc Rk²<=Sum(ni.100^(m-i), i=1..k+1)->N, k->inf
Selon (c), on a yi(xi) = ci - [ci+1 - ni+1]/100 et la condition de (b) donne
ck < yk(xk + 1) = (xk + 1)(20.rk-1 + xk + 1)
= yk(xk) + (2.xk + 20 rk-1 + 1)
Alors on a : [ck+1 - nk+1]/100 = ck - yk(xk) selon (c)
< 2.xk + 20.rk-1 + 1
< 20.(1 + 10^k-1)
< 3.10^k
Alors Rk² = Sum(ni.100^(m-i), i=1..k) + [nk+1 - ck+1].100^(m-k-1)
> Sum(ni.100^(m-i), i=1..k) - 3.10^(2m-k-2)->N, k->inf
ce qui démontre notre propos!