Recherche algorithme base 2

[mathelot]

bonjour,

je cherche un algorithme pour programmer le calcul
des digits de 1/3 en base 2.


Excellente journée à tous.

[Flodelarab]

:lol:

Pourquoi ne poses tu pas la division ?


Ne passons pas à côté des choses simples

[mathelot]

Euh, comment je fais ?



je divise 1 par

peux-tu m'expliquer ?

[Flodelarab]

Comme une division en décimal sauf que tu la fais en binaire.

D'ailleurs le résultat est juste. Voici la preuve:

Et c'est bien 1/3 ... exprimé en binaire évidemment.

[mathelot]

merçi, j'ai compris.

Et pour développer racine de 2 ?

[Flodelarab]

pfiou! Là, ça se complique. Il faudrait un équivalent de l'extraction de racine en décimal pour le binaire.

As tu déjà extrait une racine en décimal, déjà ?


Nonnnnnnnn je pense à autre chose. Tu cherches un algo ? Utilises la dichotomie autour du nombre qui au carré fait 2.

[mathelot]

je peux peut être faire

x(n+1)=(1/2) (xn+ 1/xn)
x0=2=

puisque c'est possible de diviser.

[Flodelarab]

je peux peut être faire

x(n+1)=(1/2) (xn+ 1/xn)
x0=2=

puisque c'est possible de diviser.

T'auras un gros problème de précision.

Fait par dichotomie comme je t'ai dit. C'est le plus simple.

[alben]

T'auras un gros problème de précision.

Fait par dichotomie comme je t'ai dit. C'est le plus simple.

Bonjour,
Il me semble que la méthode la plus précise et la plus rapide pour extraire une racine en base 2 est celle de Newton (à peu près celle proposée par Mathelot) :
On veut trouver la racine de où M € [1/2;1[
On a avec
et avec a=M ou 2M selon la parité de k.
Appliqué à 2, cela donne xo=1 et a=2. x1 donne déjà 3 bits significatifs et ça double à chaque étape ; avec six itérations, on arrive à 160 bits, soit 50 décimales !
Bien entendu, cela suppose que l'on dispose de l'addition et de la division en binaire avec une précision suffisante.
Dans le cas général pour calculer n'importe quelle racine carrée, c'est très facile à programmer car on peut fixer le nombre d'itérations en fonction de la précision sur les opérations élémentaires :
nb de calculs de