|
#1 - 25-03-2016 08:59:35
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
racine carrée se 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é ?
#2 - 25-03-2016 16:40:23
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Racie carré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 : 307
- Lieu: Montargis
racine caeré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 : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
Rcine 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 : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
Racine caarrée de 2
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 : 3802
Racine carre 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 : 3334
racine xarré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 : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
Racin ecarrée de 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 : 3802
Rcine carrée 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 : 307
- Lieu: Montargis
Racine carrée dee 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)
une biennale, c'est pluôt un événement qui dure ou a lieu tous les 2 ans
#11 - 27-03-2016 09:54:37
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Racine carrée e 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 : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
racine carréz 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 : 3802
Racine carrée d 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 : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
racine carté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 : 3802
Racine carrée de 22
Je me suis mal exprimé, un entier -1 est un entier auquel on ôte 1.
#16 - 27-03-2016 22:39:46
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
ravine 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 : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
racine carté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 : 3802
racine carréz 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 carréee 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 : 3802
Racine carreé 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
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
racine caeré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 : 3802
Racne 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
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
racine careé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 : 3802
Racine carrré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 : 3802
racine carrée se 2
Pourrais tu me dire comment tu écris "but" au départ pour le nombre 2 par exemple ?
Mots clés des moteurs de recherche
|
|