Discussion :

[annoussa]

salut!!!
je suis en train d'écrire une fonction qui calcule la racine carrée d'un réel positif a par la methode de newton.
la racine carrée d'un reel>0 est egale à la limite de la suite (Xn) n>0
X indice(n+1)= 1/2 *( x indice n + a / x indice n)
X0 est arbitraire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
entrer(a);
entrer (X0);
n <-0
 
tant que ???
x(n+1)<- 1/2 *( x indice n + a / x indice n)
n<-n+1
fin tant que

et apres on fait une boucle mais quelle est la condition d'arrêt!!!!!
et quand on retourne la racine carrée de a!!!!!
merci de me conseiller!!

[Matthieu Brucher]

Tu peux utiliser la précision pour faire ton calcul.

[®om]

Vu que tu sais que ta suite converge (en tout cas en mathématiques, car en représentation flottante ça doit être plus dur à prouver), tu peux comparer l'écart entre Xn et Xn+1 (divisé par Xn pour prendre en compte l'ordre de grandeur). Donc tu t'arrêtes lorsque (|Xn+1 - Xn| / |Xn|) < ε... Il faut maintenant déterminer ton ε

[nletteron]

J'allais le dire. Ta suite est convergente donc

| x(n+1) - x(n) | < epsilon

Epsilon est une valeur très petite. A toi de voir quelle est le meilleur rapport qualité du résultat, temps de l'algorithme.

[Eric Boisvert]

je ce bout de code ici (Delphi)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
// distance de deux points
Function Distance(x1, y1, x2, y2 : integer): integer;
// Calcul de l'hypothénuse a := sqrt(dx*dx+dy*dy)
// en utilisant la formule de Newton pour le calcul de la racine carrée
// 12 itérations suffisent :  sqrt(a) -->  Xo = (1+a)/2  et  Xn+1 = (xn+a/xn)/2
// C'est 3 fois plus rapide que  j := trunc(sqrt(sqr(dx)+sqr(dy)))
var
  i : Integer;
  a, r0, r1 : Integer;
begin
  r0 := x2-x1;      
  r1 := y2-y1;
  a := r0*r0 + r1*r1;
  r1 := (1+a) DIV 2;
  FOR i := 1 TO 12 DO
  begin
    r0 := r1;
    IF r0 > 0 then r1 := (r0+(a div r0)) div 2;
  end;
  Result:= r1;
end;

[random]

à la vitesse ou l'itération converge 12 itérations c'est déja énorme
surtout si on choisit inteligemment l'amorce

[Eric Boisvert]

étant donnée qu'un entier est sur 32 Bits

est-ce qu'il ne serait pas possible de choisir le nombre d'itération
en fonction de la grosseur du chiffre initial?

exemple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
si Chiffre initiale < 16777215 (24bits)
    Nombre d'iteration=8
else si Chiffre initiale < 65535 (16bits)
      Nombre d'iteration=6
  else si Chiffre initiale < 255 (8bits)
      Nombre d'iteration=4
  else
      Nombre d'iteration=12

où quelque chose du genre?