J'ai implémenté un calcul chiffre par chiffre de la racine carrée de deux. À chaque tour, il dépassera un bit de la partie fractionnaire, par exemple.
1 0 1 1 0 1 0 1 etc.
Je souhaite convertir cette sortie en nombres décimaux:
4 1 4 2 1 3 6 etc.
Le problème auquel je suis confronté est que cela fonctionnerait généralement comme ceci:
1 * 2 ^ -1 + 0 * 2 ^ -2 + 1 * 2 ^ -3 etc.
Je voudrais éviter complètement les fractions, car je voudrais travailler avec des entiers pour convertir du binaire en décimal. J'aimerais aussi imprimer chaque chiffre décimal dès qu'il a été calculé.
La conversion en hexadécimal est triviale, car je n'ai qu'à attendre 4 bits. Existe-t-il une approche intelligente pour convertir en base10 qui permet d'observer seulement une partie de la sortie entière et de supprimer de manière théorique les chiffres de l'équation, une fois que nous sommes certains, que cela ne changera plus, c'est-à-dire
1 0 2 0,25 3 0,375 4 0,375 5 0,40625 6 0,40625 7 0,4140625 8 0,4140625
3 Réponses :
Vous pouvez utiliser l'approche de multiplication et de division pour réduire l'arithmétique en virgule flottante.
1 0 1 1
Ce qui équivaut à 1 * 2 ^ 0 + 0 * 2 ^ 1 + 2 ^ (- 2) +2 ^ (- 3) peut être simplifié en (1 * 2 ^ 3 + 0 * 2 ^ 2 + 1 * 2 ^ 1 + 1 * 2 ^ 0) / (2 ^ 3) seule la division reste en virgule flottante reste arithmétique tout est une opération arithmétique entière. La multiplication par 2 peut être mise en œuvre par décalage à gauche.
Existe-t-il une approche intelligente pour convertir en base10 qui permet d'observer seulement une partie de la sortie entière et idéalement de supprimer les chiffres de l'équation, une fois que nous sommes certains que cela ne changera plus (?)
Oui, éventuellement en pratique, mais en théorie, non dans certains cas.
Cela s'apparente à Le dilemme du fabricant de tables .
Considérez le traitement ci-dessous d'une valeur proche de 0,05. Tant que la séquence binaire est .0001 1001 1001 1001 1001 ..., nous ne pouvons pas savoir que l'équivalent décimal est 0,04999999 ... ou 0,05000000 ... non nul.
int main(void) { double a; a = nextafter(0.05, 0); printf("%20a %.20f\n", a, a); a = 0.05; printf("%20a %.20f\n", a, a); a = nextafter(0.05, 1); printf("%20a %.20f\n", a, a); return 0; } 0x1.9999999999999p-5 0.04999999999999999584 0x1.999999999999ap-5 0.05000000000000000278 0x1.999999999999bp-5 0.05000000000000000971Le code peut analyser la séquence entrante de bits de fraction binaire puis poser deux questions, après chaque bit: "si les bits restants sont tous à 0" qu'est-ce que c'est en décimal? "et" si les bits restants sont tous à 1 "quoi est-ce en décimal? ". Dans de nombreux cas, les réponses partageront des chiffres significatifs communs. Pourtant, comme indiqué ci-dessus, tant que 1001 est reçu, il n'y a pas de chiffres décimaux significatifs communs.
Un "out" habituel est d'avoir une limite supérieure quant au nombre de chiffres décimaux qui jamais être montré. Dans ce cas, le code ne présente qu'un résultat arrondi et qui peut être déduit en temps fini même si la séquence d'entrée binaire reste 1001 ad nauseam .
Le problème auquel je suis confronté est que cela fonctionnerait généralement comme ceci:
1 * 2 ^ -1 + 0 * 2 ^ -2 + 1 * 2 ^ -3 etc.
Eh bien 1/2 = 5/10 et 1/4 = 25/100 et ainsi de suite, ce qui signifie que vous aurez besoin de puissances de 5 et de décaler les valeurs par des puissances de 10
ainsi donné 0 1 1 0 1
[1] 0 * 5 = 0
[2] 0 * 10 + 1 * 25 = 25
[3] 25 * 10 + 1 * 125 = 375
[4] 375 * 10 + 0 * 625 = 3750
[5] 3750 * 10 + 1 * 3125 = 40625
Modifier:
Existe-t-il une approche intelligente pour convertir en base10 qui permet d'observer seulement une partie de la sortie entière et de supprimer idéalement les chiffres de l'équation, une fois que nous sommes certains, que cela ne changera plus
Il pourrait en fait être possible de faire apparaître les chiffres les plus significatifs (MSD) dans ce cas. Ce sera un peu long mais merci de rester avec moi
Considérez les valeurs X et Y:
- Si X a le même nombre de chiffres que Y, alors le MSD changera.
i Out X Y flag ------------------------------------------------------------------- 1 0 5 0 2 25 25 1 3 375 125 1 4 3,750 625 0 5 40,625 3,125 1 6 406,250 15,625 0 7 4 140,625 78,125 1 8 4 1,406,250 390,625 0 9 4 14,062,500 1,953,125 0 10 41 40,625,000 9,765,625 0 11 41 406,250,000 48,828,125 0 12 41 4,062,500,000 244,140,625 0 13 41 41,845,703,125 1,220,703,125 1 14 414 18,457,031,250 6,103,515,625 0 15 414 184,570,312,500 30,517,578,125 0 16 414 1,998,291,015,625 152,587,890,625 1 17 4142 0,745,849,609,375 762,939,453,125 1
- Si Y a un ou plusieurs chiffres inférieurs à X, alors le MSD peut changer.
1. If X = 10000 and Y = 9000 then the MSD of X can change. 2. If X = 10000 and Y = 900 then the MSD of X will not change. 3. If X = 19000 and Y = 900 then the MSD of X can change. 4. If X = 18000 and Y = 999 then the MSD of X can change. 5. If X = 17999 and Y = 999 then the MSD of X will not change. 6. If X = 19990 and Y = 9 then the MSD of X can change.Donc, le premier point est explicite mais le deuxième point est ce qui nous permettra de faire apparaître le MSD. La première chose que nous devons savoir est que les valeurs que nous ajoutons sont continuellement divisées en deux à chaque itération. Ce qui signifie que si nous considérons uniquement le MSD, la plus grande valeur en base10 est 9 qui produira la séquence
9 > 4 > 2 > 1 > 0Si nous additionnons ces valeurs, elle sera égale à 16, mais si nous essayons de considérer les valeurs des chiffres suivants (par exemple 9,9 ou 9,999), la valeur s'approche en fait de 20 mais elle ne dépasse pas 20. Cela signifie que si X a n chiffres et Y a n-1 chiffres, le MSD de X peut encore changer. Mais si X a n chiffres et Y a n-2 chiffres, tant que le chiffre n-1 de X est inférieur à 8, alors le MSD ne changera pas (sinon ce serait 8 + 2 = 10 ou 9 + 2 = 11 ce qui signifie que le MSD va changer). Voici quelques exemples
En supposant que X est la somme courante de sqrt (2) et Y est 5 ^ n:
19000 + 1000 = 20000 19900 + 100 = 20000Dans l'exemple ci-dessus, sur point # 2 et # 5, le 1 peut déjà être sauté. Cependant, pour le point # 6, il est possible d'avoir 19990 + 9 + 4 = 20003, mais cela signifie également que 2 et 0 peuvent être sautés après que cela se soit produit.
Voici une simulation pour sqrt (2)
10000 + 10000 = 20000
Très beau. J'ai souvent trouvé qu'il fallait un génie pour repérer quelque chose qui semble être évident rétrospectivement. Cependant, cela ne répond pas à son désir de ... imprimer chaque chiffre décimal dès qu'il a été calculé. Ce n'est peut-être même pas possible.