Technique de l'extraction de racine - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs est disponible ici.

La technique du goutte à goutte est un algorithme permettant d'extraire la racine carrée d'un nombre décimal.

Algorithme

  1. Découper le nombre en tranches de 2 chiffres à partir de la virgule
  2. Prendre la tranche la plus à gauche et lui retrancher les nombres impairs successifs tant que cela est possible
  3. Le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre...) de soustractions effectuées est le chiffre (Un chiffre est un symbole utilisé pour représenter les nombres.) le plus à gauche de la racine
  4. Prendre le dernier nombre impair utilisé, lui ajouter 1, multiplier par 10 et ajouter 1
  5. Au résultat des soustractions effectuées à l'étape 2, coller la tranche suivante
  6. Au nombre ainsi obtenu, retrancher, tant que cela est possible, les nombres impairs à partir du nombre impair obtenu à l'étape 4
  7. Le nombre de soustractions effectuées est le chiffre suivant de la racine
  8. Recommencer à partir de l'étape 4

Remarques :

  • si le résultat des soustractions est 0 et que les tranches restantes ne comportent que des zéros, on arrête les calculs et on écrit des zéros à droite des chiffres déjà obtenus de la racine (autant que de tranches restantes)
  • si le nombre de soustractions effectuées est 0, on enlève 2 au nombre impair obtenu à l'étape 4 ; cela donne le dernier nombre impair utilisé

Exemple avec le nombre 71214,28

7 est la tranche la plus à gauche

7-1-3 = 3 il y a 2 soustractions donc 2 est le chiffre le plus à gauche de la racine de 71214,28

3 est le dernier nombre impair utilisé. (3+1)×10+1 = 41

3 est le résultat des soustractions. Avec la tranche suivante, on obtient 312

312-41-43-45-47-49-51 = 36 il y a 6 soustractions donc 6 est le chiffre suivant de la racine

51 est le dernier nombre impair utilisé. (51 + 1)×10+1 = 521

36 est le résultat des soustractions. Avec la tranche suivante, on obtient 3614

3614-521-523-525-527-529-531 = 458 il y a 6 soustractions donc 6 est le chiffre suivant de la racine (266)

531 est le dernier nombre impair utilisé. (531+1)×10+1 = 5321

458 est le résultat des soustractions. Avec la tranche suivante, on obtient 45828

45828-5321-5323-5325-5327-5329-5331-5333-5335 = 3204 il y a 8 soustractions donc 8 est le chiffre suivant de la racine (266,8)

5335 est le dernier nombre impair utilisé. (5335+1)×10+1 = 53361. 3204 est le résultat des soustractions. Avec la tranche suivante, on obtient 320400

320400-53361-53363-53365-53367-53369-53371 = 204 il y a 6 soustractions, 6 est le chiffre suivant de la racine (266,86)

53371 est le dernier nombre impair utilisé. (53371+1)×10+1 = 533721

204 et la tranche suivante donne 20400

on ne peut effectuer de soustractions donc le chiffre suivant de la racine est 0 (266,860)

533721-2=533719 est le dernier nombre impair " utilisé ". Le prochain nombre impair à utiliser est (533719+1)×10+1 = 5337201

20400 et la tranche suivante donne 2040000

on ne peut effectuer de soustractions donc le chiffre suivant de la racine est encore 0 (266,8600)

5337201-2=5337199 est le dernier nombre impair " utilisé ". Le prochain à utiliser est (5337199+1)×10+1 = 53372001

2040000 et la tranche suivante donne 204000000

204000000-53372001-53372003-53372005 = 43883991 il y a 3 soustractions donc 3 est le chiffre suivant de la racine (266,86003)

et ainsi de suite ...

On peut vérifier que 266,86003² + 0,0043883991 = 71214,28 car la racine ayant 5 chiffres après la virgule, la différence comporte 10 chiffres après la virgule.

Preuve de l'algorithme

L'algorithme est basé d'une part sur la propriété que la somme des n premiers nombres impairs (de 1 à 2n – 1) est n², et d'autre part que lorsqu'on change de tranche (2 chiffres), cela correspond à un changement d'un chiffre pour la racine et donc à considérer que la racine est multipliée par 10 ; le nombre est donc (10n)² qui est la somme des 10n premiers nombres impairs, de 1 à 20n – 1 d'après la propriété précédente.

Et comme 20n + 1 = ((2n – 1) + 1) × 10 + 1, on a les calculs de l'étape 4 de l'algorithme pour obtenir le nombre impair à utiliser dans la suite des soustractions.

Remarquons que lorsqu'on a un nombre à virgule, on peut se ramener à un nombre entier par un décalage de la virgule par tranche de 2 chiffres : cela correspond à un décalage de la virgule d'1 chiffre pour la racine carrée (La racine carrée d’un nombre réel positif x est le nombre positif dont le...). En pratique, le passage de la virgule consiste à mettre une virgule dans la racine (voir l'exemple).

Pour la justification, appelons N un nombre entier dont on cherche la racine carrée .

La première étape consiste à séparer N en tranches de 2 chiffres à partir du chiffre des unités : N = A0A1 ... Ak où les Ai sont les tranches de 2 chiffres sauf éventuellement pour A0. N ayant k tranches de 2 chiffres, sa racine carrée sera composée de k chiffres:= c0c1 ... ck.

La deuxième étape de l'algorithme consiste à soustraire de la première tranche A0 les c0 premiers nombres impairs : A0 = 1 + 3 + ... + (2c0 – 1) + d0 avec d0 < 2c0 + 1 Le nombre de soustractions donne donc le chiffre correspondant de la racine carrée : c'est l'étape 3 de l'algorithme.

Comme 1 + 3 + ... + (2c0 – 1) = c0², on a donc A0 = c0² + d0. Multiplions par 100 : 100 × A0 = 100 × c0² + 100 × d0 ou encore A000 = (10 × c0)² + d000. Et en ajoutant la tranche suivante, on obtient : A0A1 = c00² + d0A1 qui correspond au début de l'étape 5 de l'algorithme. Comme c00² = 1 + 3 + ... + (20 × c0 – 1), le prochain nombre impair à soustraire est 20 × c0 + 1 qui se calcule à partir de 2c0 – 1 : 20 × c0 + 1 = ((2c0 – 1) + 1) × 10 – 1 et on retrouve les calculs de l'étape 4 de l'algorithme pour déterminer ce nombre.

Ensuite, on cherche les nombres impairs suivants contenus dans d0A1 à partir de 20 × c0 + 1 et on obtient c1 nombres impairs : d0A1 = (20 × c0 + 1) + ... + (2c0c1 – 1) + d1 avec d1 < 2c0c1 + 1. Ce qui donne A0A1 = c00² + (20 × c0 + 1) + ... + (2c0c1 – 1) + d1 ou encore A0A1 = 1 + ... + (20 × c0 - 1) + (20 × c0 + 1) + ... + (2c0c1 – 1) + d1 on a bien la somme des 10 ´ c0 premiers nombres impairs avec les c1 suivants et donc A0A1 = (10 × c0 + c1)² + d1. Le nombre de soustractions a bien donné le chiffre suivant de la racine carrée.

Les cas particuliers ont été mentionnés dans l'exemple : cas où un des ci est 0 et cas où il n'y a plus que des tranches 00

Variante

1. Cette variante, plus rapide et pouvant être exécutée de tête, ne marche (La marche (le pléonasme marche à pied est également souvent utilisé) est un...) que si l'on est sûr que la racine que l'on cherche est un nombre entier.

2. Pour commencer, divisez le nombre par 100 et situez le résultat entre deux carrés de nombres entiers consécutifs. Il est donc recommandé de connaître les carrés des nombres entiers jusqu'a un certain point (Graphie) (20-25).

Exemples : 14400/100=144=12² \ 24649/100=246,49 15²(225)<246,49<16²(256)

Le résultat exact (dans le premier exemple 12) ou la borne inférieure de l'encadrement (dans le deuxième exemple 15) donne les premiers chiffres du résultat. Seul le dernier reste à trouver.

3. Regardez le dernier chiffre du nombre initial ; il est facile de vérifier que :

-Si c'est un 0, le dernier chiffre du résultat est 0

-Si c'est un 5, le dernier chiffre du résultat est 5

-Si c'est un 1, le dernier chiffre du résultat est 1 ou 9

-Si c'est un 4, le dernier chiffre du résultat est 2 ou 8

-Si c'est un 9, le dernier chiffre du résultat est 3 ou 7

-Si c'est un 6, le dernier chiffre du résultat est 4 ou 6

-Il ne peut pas être 2,3 ou 7 (un nombre se finissant par 2,3 ou 7 ne peut avoir une racine entière).

Si vous avez le choix entre deux chiffres, regardez, en 2., si le nombre est plus proche de la borne inférieure ou supérieure de l'encadrement, et choisissez en conséquence le plus petit ou le plus grand des deux chiffres.

Exemples : 14400, le dernier chiffre est 0, donc le résultat est 120 (12 puis 0) \ 24649, le dernier chiffre est 9 et 246,49 est plus proche de 256 que de 225, le résultat est donc 157 (15 puis 7)

4. Les résultats donnés sont, bien entendu exacts. Cependant si vous essayez cette technique avec des nombres choisis au hasard (Dans le langage ordinaire, le mot hasard est utilisé pour exprimer un manque efficient, sinon...), ne vous étonnez pas d'obtenir des résultats faux et relisez le 1.

Page générée en 0.035 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
A propos - Informations légales | Partenaire: HD-Numérique
Version anglaise | Version allemande | Version espagnole | Version portugaise