[PDF] Algorithme de calcul dune racine carrée

View - Download Algorithme de calcul dune racine carrée

Previous PDF

Next PDF

flash informatique323232

3 DÉCEMBRE 2013 - N°

7

Algorithme de calcul d'une

racine carrée

Benjamin.Barras@epfl.ch

, EPFL - Domaine-IT, Responsable Linux The algorithm presented here is used to calculate a square root simply, efficiently and very accurately. L'algorithme présenté ici, permet de calculer une racine carrée de manière simple, efficace et d'une précision redoutable.

Introduction

Après avoir parlé de l'algorithme CORDIC

[1] dans le numéro précédent, je vous propose de découvrir en détail l'algorithme de calcul d'une racine carrée utilisé dans les calculatrices HP. On trouvera l'article original, qui décrit cet algorithme, dans le HP

Journal

[2]

Vocabulaire

Avant de décrire cet algorithme, nous avons besoin de définir un peu de vocabulaire:

0,1,2,3,4,5,6,7,8,9 sont des chiffres (digit);

on forme un nombre avec des chiffres; exemple: 1267 est un nombre formé avec les chiffres 1, 2, 6, 7; on travaillera toujours en base 10; rappel: 1267=110 3 +2 10 2 +6 10 1 +7.

Présentation de l'algorithme

Première approche On cherche la valeur de ,

Prenons a une valeur approchée de

, et calculons le reste: R=x-a 2

Si R>0, on augmente a et on recommence,

Encore faut-il choisir une méthode ?

Premier exemple

Première approche, calcul de 54756aR=54756-a

2

Signe Notes

20014756R > 0a=200 est une valeur approchée

21010656R > 0on augmente a

2206356R > 0on augmente a

2301856R > 0on augmente a

240-2844R < 0stop, nouvelle valeur approchée:

a =230 Simple, pas compliqué, mais on peut faire mieux !Comment faire ?Calculs Cherchons la prochaine valeur du chiffre b qui se trouve à la posi- tion j: a j a b 10 j avec a qui est notre une valeur approchée (nombre). Les restes sont: R a x a 2 et R aj x a j2

Remarque: R

a R aj puisque a j est plus proche de x.

Définissons

R b comme le solde de la différence lorsque l'on ajoute b 10 j a R b R a R aj a j2 a 2

Donc, d'après l'équation ci-dessus:

R a Rb R aj

0 donc

R a R b

Premiers développements

Calculons

R b R b =a j2 -a 2 a+b 10 j 2 -a 2 =a 2 +2 ab 10 j +b 2 10 2j -a 2 =2 ab 10 j +b 2 10 2j Donc b est le plus grand chiffre possible tel que: 2 ab 10 j b 2 10 2 j R a

Une fois que l'on a trouvé

b , a est recalculé en y ajoutant la valeur b 10j , soit a j a b 10 j . On recalcule R a , soit R aj = R a R b . Enfin, on décrémente j de 1.

Deuxième exemple

Deuxième approche, calcul de 54756

a =200, R a x a 2 =54756-40000=14756, j =1bR b =2ab 10 j +b 2 10 2 j R a -R b

0014756

1410010656

284006356

3129001856

417600-2844

Donc a =200+3 10 1 =230, R a =1856, j =0 Simple, pas compliqué, mais on peut faire mieux

Première subtilité

Il faut savoir qu'on écrit

un nombre pair: p=2n avec n un nombre impair: p=2n -1 avec n -0

Théorème

b 2 b n=1 2 n -1 somme des nombres impairs jusqu'à 2 b -1.

Exemple:

b =6 2 b -1=11 b 2 =36=1+3+5+7+9+11 3333

3 DÉCEMBRE 2013 - N°

7

Preuve

Les lignes blanches et noires représentent les nombres impairs. Il suffit de compter le nombre de carré. Reprenons notre calcul, avec: b 2 b n=1 2 n -1 b b n=1 1

Ce qui nous donne:

R b = 2 ab 10 j b 2 10 2 j b n=1 (2 a 10 j 2 n -1 10 2 j

Deuxième subtilité

Reprenons notre inégalité:

R a R b

Multiplions par 5 des deux côtés: 5

R a 5 R b

Calculons 5

R b 5 R b =5 b n=1 (2 a 10 j (2 n -1) 10 2 j b n=1 (10a 10 j (10n-5)10 2 j Rappel: b est le plus grand chiffre possible tel que 5R a 5 R b reste vérifiée: R aj R a R b

0, donc

5 R aj =5 R a -5 R b 0.

Troisième exemple

x=54756,a=200, R a x a 2 =54756-40000=14756, j =1 5 R b b n=1 (10a10 j (10n-5)10 2 j ), 5 R a =73780 n10a10 j (10n-5)10 2 j 5 R b 5 R a -5 R b

1205002050053280

2215004200031780

322500645009280

42350088000-14220

Donc b =3, a =200+3 10 1 =230, 5 R a =9280, j =0 Remarque: 23500 sont les premiers chiffres qui apparaissent pour

54756.

Suite x=54756,a=230, R a x a 2 =54756-52900=1856, j =0 5 R b b n=1 (10a10 j (10n-5)10 2 j ), 5 R a =9280 n10a10 j (10n-5)10 2 j 5 R b 5 R a -5 R b

1230523056975

2231546204660

3232569452335

4233592800

5234511625-2345

Donc b =4, a =230+4=234 qui correspond aux chiffres 234
5.quotesdbs_dbs45.pdfusesText_45

[PDF] pour i allant de 1 ? n ti 83

[PDF] j'ai besoin de en anglais

[PDF] je besoin ou j ai besoin

[PDF] j'ai besoin en arabe

[PDF] ecriture fractionnaire cm2

[PDF] visa pour l'image perpignan plan

[PDF] ecriture fractionnaire addition et soustraction

[PDF] visa pour l'image 2017 programme

[PDF] visa pour l'image 2016 programme

[PDF] j'ai trouvé dans mes cheveux une souris bleue youtube

[PDF] poesie en reve j ai trouvé

[PDF] j'ai trouvé dans mes cheveux une souris bleue mp3

[PDF] trouver bebe chevreuil

[PDF] youtube j ai trouvé dans mes cheveux

[PDF] nourriture d un faon