Par "maximum d'efficacité", je précise: 1 seule addition de 2 nombres binaires par nouvelle décimale de valeur 1 (les décimales à 0 sont gratuites ! ).

Quand tu dis "decimale" tu veux dire "chiffre", correct? sinon, en parlant de binaire ca embrouille...

En fait faire des racines carrées en binaire c'est vraiment mon expertise.... regardes mon message de bonne année. C'était qu'un échantilion de ce que je peux faire. Le programme qui permet de calculer ca est modulaire. Il peut extraire plus d'un million de decimales d'une racine carrée d'un nombre quelconque. Et bien sur, ca ce fait d'abord en binaire et ensuite on converti en décimal.

Et donc a chaque etape, pour trouver le chiffre binaire suivant, je fait une comparaison/soustraction et 2 decalages, pas de multiplication.  Est-ce que c'est a quoi tu penses ou as-tu une auitre technique?
Je demande parce que on peut dire qu'une soustraction c'est l'addition de l'inverse... et si on compte pas les decalages...

@kossi_tg: comment appelle t on une décimale en base 2 ? Une biennale ?

@Dhrm77: seulement des additions, pas de soustractions. Je ne calcule pas l'inverse de la racine carrée.
Maintenant, ta méthode qui utilise soustraction et addition, ça m'intéresse aussi.

Voici la méthode classique pour calculer une racine carrée.
1) la theorie est tout simplement basée sur l'équation [latex](a+b)^2 = a^2+2ab+b^2[/latex]:
  pour obtenir le chiffre suivant (b), on suppose que l'on a deja (a), une partie de la racine carrée
  calculée. Le nombre de depart est [latex](a+b)^2[/latex] et on lui a deja oté [latex]a^2[/latex].
  Il reste donc [latex]2ab+b^2[/latex].
  On a 'a', et on cherche 'b' tel que [latex]b*(2a+b)[/latex] rentre au mieux dans ce qui reste.

2) Application a la base 10:
  Prenons l'exemple de 200.
- avant de commencer, il faut decaler le nombre vers la droite jusqu'a ce qui reste soit inferieur au carré de la base ou l'on travaille. Donc on commence avec un numerateur de '2'.
- au depart notre racine pré-calculée est[latex] a=0[/latex].
- quel est le 'b' tel que [latex]b*(2a+b)[/latex] rentre au mieux dans 2?
- si on prend b=2, on obtient 2*(0+2) = 4 > 2 (trop grand)
- si on prend b=1, on obtient 1*(0+1) = 1 <= 2 (ca marche)
- on a donc le debut a=1. On soustrait 1*(0+1) au 2 de depart et notre reste est 1
- on decale ensuite notre reste de 2 chiffres vers la gauche, et notre racine d'un chiffre vers la gauche.
- on a donc le numerateur N=100, et la racine a=10.
- quel est le 'b' tel que [latex]b*(2a+b)[/latex] rentre au mieux dans 100?
- on evalue b en calculant [latex]b=N/2a = 5[/latex]
- si on prend b=5, on obtient 5*(20+5) = 125 > 100 (trop grand)
- si on prend b=4, on obtient 4*(20+4) = 96 <= 100 (ca marche)
- on a maintenant a=14,  On soustrait 4*(20+4) a N=100 et N est maintenant 4.
- on fait ensuite les decalages. Mais comme on a épuisé les zeros du nombre original, on se rappelle qu'il faut mettre un point (ou virgule) decimal(e) apres le 14, que l'on ignorera pour les calculs suivants, mais qui sera present dans la solution finale.
- on decale ensuite notre reste de 2 chiffres vers la gauche, et notre racine d'un chiffre vers la gauche. N=400, a=140.
- quel est le 'b' tel que [latex]b*(2a+b)[/latex] rentre au mieux dans 400?
- on evalue b en calculant la partie entiere de [latex]b=N/2a = 400/280 = 1[/latex]
- si on prend b=1, on obtient 1*(280+1) = 281 < 400 (ca marche)
- on a maintenant a=141,  On soustrait 1*(280+1) a N=400 et N est maintenant 119.
Et on continue comme ca pour chaque nouveau chiffre.

2) Application au binaire (base 2):
En binaire, tout se simplifie, puisque les choix possibles de chiffres ne sont que 0 et 1.
Quand on calcule [latex]b*(2a+b)[/latex], au pire on a [latex]0*(2a+0) = 0[/latex], au mieux on a [latex]1*(2a+1) = 2a+1[/latex]
On a donc pas de multiplication par b a faire.
Prenons l'exemple du calcul de racine de 3 =11 en base 2.
- a=0
- N=11, 2a+1 = 1, 1<11, donc notre premier chiffre est 1, nouveau N=11-1=10
- ici on va simplifier et au lieu de garder a=1, on va garder a' = 2a = 10
- on decale.
- N=1000, a'=100
- a'+1 = 101, 101<1000, donc notre chiffre suivant est 1, nouveau N=1000-101=11
- on incremente 101 pour obtenir a'=110, puis on decale:
- N=1100, a'=1100
- a'+1 = 1101, 1101>1100, donc notre chiffre suivant est 0, N ne change pas.
- on decrement 1101 pour obtenir a'=1100, puis on decale:
- N=110000, a'=11000
- a'+1 = 11001, 11001<110000, donc notre chiffre suivant est 1, nouveau N=110000-11001=10111
- on incremente 11001 pour obtenir a'=11010, puis on decale:
- N=1011100, a'=110100
- a'+1 = 110101, 110101<1011100, donc notre chiffre suivant est 1, nouveau N=1011100-110101=100111
- on incremente 110101 pour obtenir a'=110110, et ainsi de suite...
...et ainsi de suite...
A la fin, si on calcule une racine entiere, le decalage est dans l'autre sens, sinon on se souvient juste ou se trouve la virgule.
Une etape de plus (que je vous epargne), et...
Notre debut de racine de 3 est 1.10111 en binaire, soit 1.71875 en decimal
3 étapes de plus... 1.10111011 en binaire, soit 1.73046875 en decimal

@nodgim: On parle de décimale en système décimal (base 10) donc je pencherais logiquement pour binaire en système binaire (base 2)

une biennale, c'est pluôt un événement qui dure ou a lieu tous les 2 ans

J'ai du mal a croire que l'on ne puisse faire QUE des additions. Il faut bien faire au moins des tests pour savoir si on va ou non faire ces additions, et ces tests reviennent a faire des comparaisons (donc probablement des soustractions).
Je comprends bien que ta methode est differente, mais pour y voir plus clair, prenons l'exemple d'un racine carrée d'un nombre de 32 bits.
Donc combien d'additions ferais-tu?
Combien de tests?

La partie de racine carrée dont le carré est l'entier -1, c'est i ou j (selon qu'on est physicien ou mathematicien), mais la je suis de plus en plus perdu.
Pour faire la racine carrée d'un nombre complexe je calcule son amplitude, puis sa racine carrée, puis son angle, puis la moitié de son angle, puis on combine te tout.... Mais ca ne m'aide pas a faire la racine carrée de 2 plus efficacement.

Si je comprends bien, pour avoir le k-ième chiffre après la virgule de l'écriture binaire de racine(19), tu n'as besoin que d'additions, et des k premiers chiffres après la virgule de racine(18) ?

Si on cherche la racine carrée de 157, alors à un moment donné, on aura une racine dont le carré aura la valeur par défaut 156,...C''est à partir de ce moment là que démarre l'algo proposé. Bien entendu en langage binaire.

Fix33, tu y es presque. J'aimerais tout de même que tu sois plus précis sur le décalage. Il faut creuser un peu de ce coté là. L'idéal serait que tu fournisses une recette, un algo, qui soit applicable directement.

@Enigmatus:

"Si but==0 : n = N = 0"

il faut lire si but=0 ou si but=/=0 ?

Oui. Je vois ça de temps en temps, pour les rétifs de Latex....
Je regarde tranquillement ce que tu as fait, ça marche bien sûr, je voudrais juste comparer avec ma méthode, voir si c'est vraiment =/=.