@nodgim #26

On s'arrête si
- (on a atteint le nombre de "décimales" que l'on voulait)
ou
- (N1==but1) et (on n'a plus de "décimales" non traitées)

Non, il n'y a pas de reste, et je compare N1 à but1 dans 4) . Je suppose qu'on peut le faire visuellement sans faire d'opération.

C'est bon j'ai compris Enigmatus.
Je valide.
C'est sensiblement différent de ma méthode, c'est une variante. Tu pourras comparer.
Dans ma méthode, quand je fais l'addition, je suis sûr qu'elle aboutira, c'est à dire qu'elle ne servira pas à rien. Dans ta méthode, statistiquement, une addition sur 2 est à jeter.

@nodgim #28

Sauf erreur,

Nombre initial = 0 11 01 10          |
but1=0 (1ère tranche); n=N=0

On essaye : n1=01; N1= 4*N + 4*n + 1 = 000 + 001 = 1 (on fait cette addition)
            N1 > but1
         => Ce n'est pas bon
Donc :      n1=00; N1 = 4*N = 000

but2=011
On essaye : n2=001; N2= 4*N1 + 4*n1 + 1 = 00000 + 0001 = 1 (on fait cette addition)
            N2 < but2
         => C'est bon
Donc :      n2=001; N2 = 00001

but3=01101
On essaye : n3=011; N3= 4*N2 + 4*n2 + 1 = 0000100 + 00101 = 1001 (on fait cette addition)
            N3 < but3
         => C'est bon
Donc :      n3=011; N3 = 1001

but4=0110110
On essaye : n4=0111; N4= 4*N3 + 4*n3 + 1 = 100100 + 01101 = 110001 (on fait cette addition)
            N4 < but4
         => C'est bon
Donc :      n4=0111; N4 = 110001

et on peut continuer pour calculer les "décimales"

Bon je vais proposer ma solution.

Dans les réponses données, on a eu:

-Unanimement, la méthode dite de la potence. Mais celle-ci suppose un calcul du reste entre le carré de la racine partielle et l'entier, et donc une soustraction, opération non prévue dans l'énoncé.

-Une méthode plus brute avancée par Fix33 et Enigmatus, qui consiste à tester chaque nouveau bit de la racine pour voir si son carré ne dépasse pas l'entier proposé. Et effectivement, une addition suffit à chaque étape. L'inconvénient est tout de même qu'à peu près une addition sur 2 est faite inutilement en cas dépassement de l'entier.

L'algo que je propose est une solution intermédiaire, basée sur le principe de l'invariance, à partir d'un certain rang de bits, entre le nb de bits de la racine carrée approchée et le carré correspondant: double ou double moins une unité. Cette invariance permet alors de fixer au départ une indexation.

Je vous laisse lire la recette, n'hésitez pas à faire vos remarques si ce n'est pas clair.

Bonne lecture et merci pour votre participation.


--------------------------------------------------------------

Recette pour écrire les décimales d'une racine carrée d'un entier en binaire.

1) Au préalable, ôter 1 au nombre entier pour le remplacer par une infinité de 1 après la virgule.

2) Trouver la racine carrée approchée la plus petite R0 telle que R0² donne au moins l'écriture correcte de l'entier moins une unité.

3) Remplacer les chiffres à gauche de la virgule de R0² par un index. Cet index I0 portera le nombre:
-de chiffres à gauche de la virgule de R0² si nb de chiffres de R0² pair.
-de chiffres + 1 à gauche de la virgule de R0² si nb de chiffres de R0² impair.

4) Repérer le rang du 1er zéro à droite de I0. On dira qu'il est à distance "d" de I0 (nb de chiffres de décalage).

5) Vérifier si le 1er chiffre à gauche de R0 doit être placé au regard de I0+d ou bien de I0+d+1. (voir test plus bas)
Si placement en I0+d, alors R0 devient R1 en lui ajoutant 1 au rang I0+d et les 0 intercalaires éventuels (R1 contient alors I0+d chiffres).
Si placement en I0+d+1, alors R0 devient R1 en lui ajoutant 1 au rang I0+d+1 et les 0 intercalaires éventuels.
 
6) Selon placement, ajouter 2*R1-1 aux décimales de R0² (le 1er chiffre de 2*R1-1 en I0+d ou I0+d+1).

7) changer l'index: I1=I0+d. Effacer les chiffres de rang inférieur ou égal à I1.   

8) Reprendre l'algorithme en 4) en incrémentant les variables.


Test
Additionner un nombre X qui commence par 0 avec un nombre R qui commence par 1.
Le but est d' avoir 1 comme 1er chiffre du résultat, mais sans qu'il y ait de retenue à gauche.
On regarde chiffre à chiffre (X,R) à partir de la gauche:
Si un couple (0,0) apparait en 1er, alors le 1er chiffre de R se positionne au droit du 1er zéro de X.
Si c'est un couple (1,1) qui apparait en 1er, alors R est à décaler d'un rang vers la droite.

Déjà, la première étape va prendre un "certain temps", puisqu'elle consiste à ajouter une infinité de 1 après la virgule…

@nodgim
Ta méthode "simple" ressemble à une blague de 1er avril… J'avoue avoir la flemme de tester cet algorithme, mais j'y remarque un certain nombre d'additions et de soustractions.

Je donne ici l'application (améliorée même) pour la racine de 2:

Au départ:
Carré: (2)00...
Racine: 1--->101(3)
Opération: (2)000...+ 1001=(2)1001=(3)001

Carré (3)001
racine: 101--->1011(4)
Opération: (3)001 + 10101=(3)11001=(5)1001

Carré (5)001
racine 1011-->101101(6)
Opération: (5)001  + 1011001= (5)1101001=(7)01001

Carré (7)01001
racine 101101--->10110101(8)
Opération (7)01001+101101001=(7)111111001=(13)001

Carré (13)001
racine 10110101---->10110101000001(14)

etc....

C'est du binaire, donc la racine s'étale vite. Mais si tu compares avec la méthode de la potence en binaire, y pas photo: c'est moins sujet à erreur et plus rapide.