Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 25-03-2016 08:59:35

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Racnie carrée de 2

Me croiriez vous si je vous disais qu'on peut trouver les décimales en binaire de la racine carrée d'un entier ( 2 par exemple) seulement en faisant des additions, et avec le maximum d'efficacité ?



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 25-03-2016 16:40:23

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Racin ecarrée de 2

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 ! ).

 #3 - 25-03-2016 19:48:01

kossi_tg
Professionnel de Prise2Tete
Enigmes résolues : 18
Messages : 301
Lieu: Montargis

Racine carréée de 2

Tu veux parler de l'algorithme de la potence en binaire? J'en connais surtout la version en base 10.

 #4 - 26-03-2016 00:32:58

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2989
Lieu: Fanning Island-?-Lac Tele,Mali

racone carrée de 2

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...


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #5 - 26-03-2016 00:42:36

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2989
Lieu: Fanning Island-?-Lac Tele,Mali

Racine carrée d e2

Pour ne faire techniquement que des vrais additions, on peut imaginer que l'on calcule directement l'inverse de la racine carrée, et qu'a la fin on prend son inverse. Cependant pour decider si on additionne ou pas, il faut faire une comparaison avec la vraie racine carrée, soit l'inverse de l'inverse de la racine carrée. ou encore faire l'addition a chaque fois, mais ne remplacer la valeur que si ca donne une retenue.

PS: quand je dis 'inverse', je veut parler du complement a 2.
par example, si on calcule la racine carrée de 3, on calcule 0.010001001 pour ne faire que des additions, puis on inverse les 0 et les 1 pour obtenir 1.101110110


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #6 - 26-03-2016 08:34:50

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Raine carrée de 2

@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.

 #7 - 26-03-2016 14:33:52

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

racone carrée de 2


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #8 - 26-03-2016 16:37:24

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2989
Lieu: Fanning Island-?-Lac Tele,Mali

racine carrée fe 2

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


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #9 - 26-03-2016 17:09:03

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Racine carréee de 2

@Tous: Dans mon jeune temps (en 6ème je crois, mais je n'en suis plus sûr), on m'a appris à calculer une racine carrée, méthode qui s'appelle aujourd'hui la méthode de la potence. Elle s'apparente à une division en quelque sorte, en un peu plus compliquée.
Or cette méthode implique de calculer un reste à chaque opération, donc à faire une soustraction. J'ai bien dit déja que je ne faisais que des additions. Il ne s'agit donc pas de la méthode de la potence.

 #10 - 26-03-2016 20:59:18

kossi_tg
Professionnel de Prise2Tete
Enigmes résolues : 18
Messages : 301
Lieu: Montargis

Racine arrée de 2

@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) lol

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

 #11 - 27-03-2016 09:54:37

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Racine carére de 2

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

 #12 - 27-03-2016 15:30:24

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2989
Lieu: Fanning Island-?-Lac Tele,Mali

Racine carréée de 2

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?


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #13 - 27-03-2016 17:19:58

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

rzcine carrée de 2

Tu m'ôtes les mots de la bouche, Dhrm77.
J'allais apporter une précision, pour ne pas trop vous égarer: La méthode par additions présuppose qu'on a à disposition la partie de racine carrée dont le carré est l'entier en question (auquel on ôte 1). Ce qui suppose qu'on doit calculer par une méthode plus classique (potence par exemple) les qq décimales nécessaires pour avoir au moins la bonne écriture de l'entier.
La méthode par addition a besoin d'un test très simple qui ne fait appel à aucun calcul.

Bon courage.

Je redonne du temps pour ceux qui veulent s'y pencher à la lumière de cette nouvelle info.

 #14 - 27-03-2016 19:52:32

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2989
Lieu: Fanning Island-?-Lac Tele,Mali

Racien carrée de 2

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.


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #15 - 27-03-2016 19:58:10

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Raciine carrée de 2

Je me suis mal exprimé, un entier -1 est un entier auquel on ôte 1.

 #16 - 27-03-2016 22:39:46

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

Racinne carrée de 2

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) ?

 #17 - 28-03-2016 04:04:10

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2989
Lieu: Fanning Island-?-Lac Tele,Mali

Racine carée de 2

Oh, ca change tout.... hmmmm...
Avec n'importe quel entier de depart? comme 157 par exemple? ou il faut deja connaitre la racine carrée de 156?
ou parle-t-on seulement de 2, ou il suffit de connaitre la racine carrée de 1?

On sait bien de x^2-1 = (x-1)(x+1) mais je ne vois pas ou ca nous mene...


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #18 - 28-03-2016 08:11:21

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

racine catrée de 2

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.

 #19 - 28-03-2016 21:58:15

fix33
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1198
Lieu: Devant un clavier depuis 1748

Racine carreé de 2

Salut !

Je suis resté longtemps dubitatif sur ma capacité à résoudre cette question...

Soit Rn la racine approchée avec n nombres, sans virgule donc multipliée par 2^(n-1).
Soit An le carré approché à l'étape n : An = Rn^2.
Dans la suite, si a et b sont des suites de chiffres, je noterai a_b l'entier formé des suites a et b accolées.

R(n+1) = Rn_1 (si son carré ne dépasse pas 2^(2n+1)) ou Rn_0 (sinon)

Or :
(Rn_1)^2 = (Rn_0)^2 + 2×Rn_0 + 1 = An_00 + Rn_01

A chaque étape notre test se limite donc effectivement à une addition (et des décalages).
Si le test est négatif, A(n+1) = An_00.

Par exemple :
R3 = 101 et A3 = 11001
(R3_1)^2 = 1100100 + 10101 = 1111001 < 10000000 donc R4 = 1011 et A4 = 1111001
(R4_1)^2 = 111100100 + 101101 = 1000010001 > 1000000000 donc R5 = 10110 et A5 = 111100100.

Mon algo de calcul de la (n-1)ème décimale (à mettre dans une fonction récursive) :
Calc = An_00 + Rn_01
Si (Calc < 2^(2n+1)) alors (Rn = Rn_1 ; An = Calc ; retourne 1)
Sinon (Rn = Rn_0 ; An = An_00 ; retourne 0)


Je ne vien sur se site que pour faire croir que je suis treise intélligens.

 #20 - 29-03-2016 08:20:28

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Racine ccarrée de 2

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.

 #21 - 30-03-2016 12:04:56

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

racone carrée de 2

Bonjour,
J'ai une méthode (proche de la "potence") avec une addition de 2 nombres binaires par bit calculé (que celui-ci soit 0 ou 1).
Le nombre binaire du départ peut être entier ou non.

Variables :
but : partie du nombre initial correspondant à la racine partielle
   n : racine partielle
   N : carré de n

1) On découpe le nombre en tranches de 2 chiffres à partir du point "décimal", en complétant par des 0 si nécessaire.

2) On initialise but, n et N
   but = tranche de gauche (0, 10 ou 11)
   Si but==0 : n = N = 0
   Sinon :       n = N = 1

3) On accole la tranche suivante à but : but1 = butxy

4) On teste avec un nouveau bit égal à 1 :
   n1 = n1 = 2*n+1
   N1 = 4*n^2 + 4*n + 1 = N00 + n01 <= C'est l'addition à faire

   Si N1 ≤ but1 : c'est bon
   Sinon : le nouveau bit vaut 0, et
      n1 = n0 = 2*n
      N1 = 4*N = N00

5) On revient à 3) tant que N1 est différent de but, qu'il y a encore des tranches non utilisées différentes de 00, et qu'on n'a pas atteint le nombre de décimales fixées

Remarque : On ne traite que des entiers et on positionne le point à la fin. Le nombre de bits de la racine avant le point "décimal" est le nombre de tranches du nombre initial avant le point.

Voici ce que j'obtiens :
Pour 2 :    racine(10) =   1.01101010000010011110
Pour 3.5 : racine(11.1) = 1.11011110111011101010

 #22 - 30-03-2016 13:18:58

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

raxine carrée de 2

@Enigmatus:

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

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

 #23 - 30-03-2016 14:18:31

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

racine varrée de 2

nodgim #22 a écrit:

"Si but==0 : n = N = 0"
il faut lire si but=0 ou si but=/=0 ?

(Si but==0) <=> (Si but est égal à zéro)
C'est une notation utilisée en informatique
n==0 : C'est un test, retourne vrai ou faux
n=0 : C'est une affectation, n prend la valeur 0

Que veut dire la notation "si but=/=0" ? différent de zéro, peut-être ?

 #24 - 30-03-2016 16:50:15

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Raccine carrée de 2

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 =/=.

 #25 - 30-03-2016 16:52:24

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Racine carrée dde 2

Pourrais tu me dire comment tu écris "but" au départ pour le nombre 2 par exemple ?

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 40 moutons, ils meurent tous sauf 18, combien en reste-t-il ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete