Pourquoi les nombres décimaux ne peuvent-ils pas être représentés exactement en binaire ?

Question

Plusieurs questions ont été postées sur SO au sujet de la représentation en virgule flottante. Par exemple, le nombre décimal 0,1 n'a pas de représentation binaire exacte, il est donc dangereux d'utiliser l'opérateur == pour le comparer à un autre nombre à virgule flottante. Je comprends les principes de la représentation en virgule flottante.

Ce que je ne comprends pas, c'est pourquoi, d'un point de vue mathématique, les chiffres situés à droite de la virgule sont plus "spéciaux" que ceux situés à gauche ?

Par exemple, le nombre 61.0 a une représentation binaire exacte car la partie intégrale de tout nombre est toujours exacte. Mais le nombre 6,10 n'est pas exact. Tout ce que j'ai fait, c'est déplacer la décimale d'une place et soudain, je suis passé d'Exactopia à Inexactville. Mathématiquement, il ne devrait pas y avoir de différence intrinsèque entre les deux nombres - ce ne sont que des nombres.

En revanche, si je déplace la décimale d'une place dans l'autre sens pour obtenir le nombre 610, je suis toujours en Exactopia. Je peux continuer à aller dans cette direction (6100, 610000000, 610000000000000) et ils sont toujours exacts, exacts, exacts. Mais dès que la décimale franchit un certain seuil, les chiffres ne sont plus exacts.

Qu'est-ce qui se passe ?

Edit : pour clarifier, je veux rester à l'écart des discussions sur les représentations standard de l'industrie, comme l'IEEE, et m'en tenir à ce que je crois être la manière mathématiquement "pure". En base 10, les valeurs positionnelles sont :

... 1000  100   10    1   1/10  1/100 ...

En binaire, ils le seraient :

... 8    4    2    1    1/2  1/4  1/8 ...

Ces chiffres ne sont pas non plus soumis à des limites arbitraires. Les positions augmentent indéfiniment vers la gauche et vers la droite.

Answer 1

Les nombres décimaux peut être représenté exactement, si vous avez suffisamment d'espace, mais pas en flottant. binaire des nombres de points. Si vous utilisez un décimal le type de point (par exemple System.Decimal dans .NET), de nombreuses valeurs qui ne peuvent pas être représentées exactement en virgule flottante binaire peuvent être représentées exactement.

Voyons les choses autrement : en base 10, avec laquelle vous êtes probablement à l'aise, vous ne pouvez pas exprimer 1/3 exactement. C'est 0,3333333... (récurrent). La raison pour laquelle vous ne pouvez pas représenter 0,1 comme un nombre binaire à virgule flottante est exactement la même. Vous pouvez représenter 3, et 9, et 27 exactement - mais pas 1/3, 1/9 ou 1/27.

Le problème est que 3 est un nombre premier qui n'est pas un facteur de 10. Ce n'est pas un problème quand on veut multiplier un nombre par 3 : vous pouvez toujours multiplier par un nombre entier sans rencontrer de problèmes. Mais lorsque vous diviser par un nombre premier qui n'est pas un facteur de votre base, vous risquez d'avoir des ennuis (et des problèmes de sécurité). sera le faire si vous essayez de diviser 1 par ce nombre).

Bien que 0,1 soit généralement utilisé comme l'exemple le plus simple d'un nombre décimal exact qui ne peut pas être représenté exactement en virgule flottante binaire, on peut soutenir que 0,2 est un exemple plus simple car il s'agit de 1/5 - et 5 est le nombre premier qui pose des problèmes entre le décimal et le binaire.

---

Note annexe pour traiter le problème des représentations finies :

Certains types de virgule flottante ont une taille fixe, par exemple System.Decimal d'autres comme java.math.BigDecimal sont "arbitrairement grandes" - mais elles atteindront une limite à un moment donné, qu'il s'agisse de la mémoire système ou de la taille maximale théorique d'un tableau. Il s'agit cependant d'un point totalement distinct du point principal de cette réponse. Même si vous disposiez d'un nombre de bits véritablement arbitraire, vous ne pourriez toujours pas représenter exactement le décimal 0,1 dans une représentation binaire flottante. Comparez cela à l'inverse : pour un nombre arbitraire de chiffres décimaux, on peut peut représente exactement tout nombre qui est exactement représentable comme un point binaire flottant.

Answer 2

La raison de cette imprécision est la nature des bases numériques. En base 10, on ne peut pas représenter exactement 1/3. Il devient 0,333... Par contre, en base 3, 1/3 est représenté exactement par 0,1 et 1/2 est une décimale (tresimale ?) qui se répète à l'infini. Les valeurs qui peuvent être représentées de façon finie dépendent du nombre de facteurs premiers uniques de la base, ainsi la base 30 [2 * 3 * 5] peut représenter plus de fractions que la base 2 ou la base 10. Encore plus pour la base 210 [2 * 3 * 5 * 7].

Il s'agit d'un problème distinct de celui de l'"erreur de virgule flottante". L'imprécision est due au fait que quelques milliards de valeurs sont réparties sur une plage beaucoup plus large. Ainsi, si vous disposez de 23 bits pour le significande, vous ne pouvez représenter qu'environ 8,3 millions de valeurs distinctes. Ensuite, un exposant de 8 bits offre 256 options pour distribuer ces valeurs. Ce schéma permet aux décimales les plus précises de se produire près de 0, de sorte que vous pouvez presque représente 0,1.

Answer 3

Par exemple, le nombre 61.0 a une représentation binaire exacte car la partie intégrale de tout nombre est toujours exacte. Mais le nombre 6.10 n'est pas exact. Tout ce que j'ai fait, c'est déplacer la décimale d'une place et soudain, je suis passé d'Exactopia à Inexactville. Mathématiquement, il ne devrait pas y avoir de différence intrinsèque entre les deux nombres - ce ne sont que des nombres. .

Éloignons-nous un instant des particularités des bases 10 et 2. Demandons - en base b quels nombres ont des représentations terminales et quels nombres n'en ont pas ? Un instant de réflexion nous indique qu'un nombre x a une terminaison b -si et seulement s'il existe un nombre entier. n tal que x b^n est un nombre entier.

Donc, par exemple, x = 11/500 a une représentation terminale de 10, parce que nous pouvons choisir n = 3 et ensuite x b^n = 22 , un nombre entier. Toutefois, x = 1/3 ne le fait pas, parce que tout ce que n nous choisissons, nous ne pourrons pas nous débarrasser des 3.

Ce deuxième exemple nous incite à réfléchir aux facteurs, et nous pouvons voir que pour tout rationnel x = p/q (que l'on suppose être en termes inférieurs), nous pouvons répondre à la question en comparant les factorisations premières de b y q . Si q a des facteurs premiers qui ne sont pas dans la factorisation première de b nous ne serons jamais en mesure de trouver une personne convenable n pour se débarrasser de ces facteurs.

Ainsi pour la base 10, cualquier p/q donde q a des facteurs premiers autres que 2 ou 5 n'aura pas de représentation terminale.

Donc, en revenant aux bases 10 et 2, nous voyons que tout rationnel avec une représentation terminale 10 sera de la forme p/q exactement quand q a seulement 2 et 5 dans sa factorisation première ; et ce même nombre aura une représentation 2 terminale exactement lorsque q a seulement 2 dans sa factorisation première.

Mais l'un de ces cas est un sous-ensemble de l'autre ! Chaque fois que

q a seulement 2 dans sa factorisation première

c'est évidemment le cas également vrai que

q a seulement 2 et 5 dans sa factorisation première

ou, dit autrement, chaque fois que p/q a une représentation 2 terminale, p/q a une représentation terminale de 10 . La réciproque n'est cependant pas vraie. pas tenir - à tout moment q a un 5 dans sa factorisation première, il aura une représentation terminale de 10, mais pas une 2-représentation terminale. C'est le 0.1 exemple mentionné par d'autres réponses.

Nous avons donc la réponse à votre question - parce que les facteurs premiers de 2 sont un sous-ensemble des facteurs premiers de 10, tous les nombres à terminaison 2 sont des nombres à terminaison 10, mais pas l'inverse. Il ne s'agit pas de 61 contre 6.1 - il s'agit de 10 contre 2.

Pour conclure, si, par hasard, les gens utilisaient (disons) la base 17 mais que nos ordinateurs utilisaient la base 5, votre intuition n'aurait jamais été trompée par cela - il y aurait pas de (non nulles, non entières) qui se terminaient dans les deux cas !

Answer 4

La raison première (mathématique) est que lorsque vous traitez avec des entiers, ils sont infiniment petit .

Cela signifie que, même s'il en existe une quantité infinie, nous pouvons "compter" tous les éléments de la séquence, sans en sauter aucun. Cela signifie que si nous voulons obtenir l'élément dans la séquence 610000000000000 e position dans la liste, nous pouvons le déterminer à l'aide d'une formule.

Cependant, les nombres réels sont infiniment infini . Vous ne pouvez pas dire "donnez-moi le vrai numéro à la position". 610000000000000 "et obtenir une réponse. La raison en est que, même entre 0 y 1 il existe un nombre infini de valeurs, lorsque l'on considère des valeurs à virgule flottante. Il en va de même pour deux nombres à virgule flottante quelconques.

Plus d'informations :

http://en.wikipedia.org/wiki/Countable_set

http://en.wikipedia.org/wiki/Uncountable_set

Mise à jour : Mes excuses, il semble que j'ai mal interprété la question. Ma réponse concerne la raison pour laquelle nous ne pouvons pas représenter chaque réel je n'avais pas réalisé que la virgule flottante était automatiquement classée comme rationnelle.

Answer 5

Pour répéter ce que j'ai dit dans mon commentaire à M. Skeet : nous peut représenter 1/3, 1/9, 1/27, ou tout autre rationnel en notation décimale. On le fait en ajoutant un symbole supplémentaire. Par exemple, un trait sur les chiffres qui se répètent dans l'expansion décimale du nombre. Pour représenter les nombres décimaux sous la forme d'une séquence de nombres binaires, nous avons besoin des éléments suivants 1) une séquence de nombres binaires, 2) un point de radix, et 3) un autre symbole pour indiquer la partie répétitive de la séquence.

La notation de la citation de Hehner est un moyen d'y parvenir. Il utilise un symbole de citation pour représenter la partie répétitive de la séquence. L'article : http://www.cs.toronto.edu/~hehner/ratno.pdf et l'entrée Wikipedia : http://en.wikipedia.org/wiki/Quote_notation .

Rien n'interdit d'ajouter un symbole à notre système de représentation, de sorte que nous pouvons représenter des rationnels décimaux exactement à l'aide de la notation binaire chiffrée, et vice versa.