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

Plusieurs questions ont été posées à SO sur 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 nombres à droite du séparateur décimal sont-ils plus "spéciaux" que ceux de gauche?

Par exemple, le nombre 61.0 a une représentation binaire exacte car la partie intégrale de n'importe quel 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 produire le nombre 610, je suis toujours dans Exactopia. Je peux continuer 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 nombres ne sont plus exacts.

Que se passe-t-il?

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

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

En binaire, ils seraient:

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

Il n'y a pas non plus de limites arbitraires imposées à ces chiffres. Les positions augmentent indéfiniment à gauche et à droite.

Les nombres décimaux peuvent être représentés exactement, si vous avez suffisamment d'espace - mais pas par des nombres à virgule binaire flottants . Si vous utilisez un type à virgule décimale flottante (par exemple System.Decimaldans .NET), de nombreuses valeurs qui ne peuvent pas être représentées exactement en virgule flottante binaire peuvent être représentées exactement.

Regardons les choses d'une autre manière - dans la base 10 avec laquelle vous êtes probablement à l'aise, vous ne pouvez pas exprimer exactement 1/3. C'est 0.3333333 ... (récurrent). La raison pour laquelle vous ne pouvez pas représenter 0,1 comme un nombre à virgule flottante binaire est exactement pour la même raison. Vous pouvez représenter 3, 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 lorsque vous voulez multiplier un nombre par 3: vous pouvez toujours multiplier par un entier sans rencontrer de problèmes. Mais lorsque vous divisez par un nombre premier qui n'est pas un facteur de votre base, vous pouvez rencontrer des problèmes (et vous le ferez 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, 0,2 est sans doute un exemple plus simple car il est 1/5 - et 5 est le premier qui cause des problèmes entre décimal et binaire .

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

Certains types de virgule décimale flottante ont une taille fixe comme d' System.Decimalautres comme java.math.BigDecimal"arbitrairement grands" - mais ils atteindront une limite à un moment donné, que ce soit la mémoire système ou la taille maximale théorique d'un tableau. Ceci est cependant un point entièrement distinct de la principale de cette réponse. Même si vous aviez un nombre véritablement arbitrairement élevé de bits avec lesquels jouer, vous ne pouviez toujours pas représenter la décimale 0,1 exactement dans une représentation à virgule binaire flottante. Comparez cela avec l'inverse: étant donné un nombre arbitraire de chiffres décimaux, vous pouvez représenter exactement n'importe quel nombre qui est exactement représentable comme un point binaire flottant.

Par exemple, le nombre 61.0 a une représentation binaire exacte car la partie intégrale de n'importe quel 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 je suis soudainement 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 détails des bases 10 et 2. Demandons - dans la base b, quels nombres ont des représentations terminales et quels nombres n'en ont pas? La réflexion d'un instant nous dit qu'un nombre xa une représentation terminale bsi et seulement s'il existe un entier ntel qu'il x b^nest un entier.

Ainsi, par exemple, x = 11/500a une représentation terminale de 10, car nous pouvons choisir n = 3puis x b^n = 22un entier. Mais ce x = 1/3n'est pas le cas, car quoi que nnous choisissions, nous ne pourrons pas nous débarrasser des 3.

Ce deuxième exemple nous invite à réfléchir aux facteurs, et nous pouvons voir que pour tout rationnel x = p/q (supposé être en termes les plus bas), nous pouvons répondre à la question en comparant les factorisations premières de bet q. Si qa des facteurs premiers qui ne sont pas dans la factorisation principale de b, nous ne serons jamais en mesure de trouver un moyen approprié npour se débarrasser de ces facteurs.

Ainsi pour la base 10, tout p/q où qa des facteurs premiers autres que 2 ou 5 n'aura pas de représentation terminale.

Revenons donc maintenant aux bases 10 et 2, nous voyons que tout rationnel avec une représentation terminale à 10 sera de la forme p/qexactement lorsqu'il qn'a que 2s et 5s dans sa factorisation première; et ce même nombre aura une 2-représentation se terminant exactement quand qa seulement 2s dans sa factorisation principale.

Mais l'un de ces cas est un sous-ensemble de l'autre! N'importe quand

qn'a que 2s dans sa factorisation première

il est évidemment aussi vrai que

qn'a que 2s et 5s dans sa factorisation première

ou, autrement dit, chaque fois qu'il p/qa une représentation terminale à 2, il p/qa une représentation terminale à 10 . L'inverse ne tient cependant pas - chaque fois qu'il qa un 5 dans sa factorisation principale, il aura une représentation terminale à 10, mais pas une représentation terminale à 2. C'est l' 0.1exemple mentionné par d'autres réponses.

Nous avons donc là la réponse à votre question - parce que les facteurs premiers de 2 sont un sous-ensemble des facteurs premiers de 10, tous les nombres se terminant par 2 sont des nombres se terminant par 10, mais pas l'inverse. Ce n'est pas environ 61 contre 6,1 - c'est environ 10 contre 2.

En guise de conclusion, si par certaines personnes bizarres utilisaient (disons) la base 17 mais nos ordinateurs utilisaient la base 5, votre intuition n'aurait jamais été égarée par cela - il n'y aurait pas de nombres (non nuls, non entiers) qui se terminent dans les deux cas!

La raison fondamentale (mathématique) est que lorsque vous traitez avec des entiers, ils sont infiniment infinis .

Ce qui signifie que, même s'il y en a une quantité infinie, nous pourrions «compter» tous les éléments de la séquence, sans en ignorer aucun. Cela signifie que si nous voulons obtenir l'élément en 610000000000000e position dans la liste, nous pouvons le comprendre via une formule.

Cependant, les nombres réels sont infiniment infinis . Vous ne pouvez pas dire «donnez-moi le vrai nombre à la position 610000000000000» et obtenez une réponse. La raison en est que, même entre 0et 1, il existe un nombre infini de valeurs, lorsque vous envisagez des valeurs à virgule flottante. Il en va de même pour deux nombres à virgule flottante.

Plus d'informations:

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

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

Mise à jour: Mes excuses, je semble avoir mal interprété la question. Ma réponse est pourquoi nous ne pouvons pas représenter chaque valeur réelle , je n'avais pas réalisé que la virgule flottante était automatiquement classée comme rationnelle.

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

La notation de citation de Hehner est un moyen de le faire. 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 .

Il n'y a rien qui dit que nous ne pouvons pas ajouter de symbole à notre système de représentation, nous pouvons donc représenter les rationnels décimaux exactement en utilisant la notation binaire, et vice versa.

BCD - Décimal codé en binaire - les représentations sont exactes. Ils ne sont pas très peu encombrants, mais c'est un compromis que vous devez faire pour la précision dans ce cas.

C'est la même raison pour laquelle vous ne pouvez pas représenter 1/3 exactement en base 10, vous devez dire 0,33333 (3). En binaire, c'est le même type de problème, mais se produit uniquement pour différents ensembles de nombres.

(Remarque: je vais ajouter «b» pour indiquer les nombres binaires ici. Tous les autres nombres sont donnés en décimal)

Une façon de penser les choses est en termes de quelque chose comme la notation scientifique. Nous sommes habitués à voir des nombres exprimés en notation scientifique comme 6.022141 * 10 ^ 23. Les nombres à virgule flottante sont stockés en interne en utilisant un format similaire - mantisse et exposant, mais en utilisant des puissances de deux au lieu de dix.

Votre 61.0 pourrait être réécrit en 1.90625 * 2 ^ 5, ou 1.11101b * 2 ^ 101b avec la mantisse et les exposants. Pour multiplier cela par dix et (déplacer le séparateur décimal), nous pouvons faire:

(1,90625 * 2 ^ 5) * (1,25 * 2 ^ 3) = (2,3828125 * 2 ^ 8) = (1,19140625 * 2 ^ 9)

ou avec la mantisse et les exposants en binaire:

(1.11101b * 2 ^ 101b) * (1.01b * 2 ^ 11b) = (10.0110001b * 2 ^ 1000b) = (1.00110001b * 2 ^ 1001b)

Notez ce que nous avons fait là pour multiplier les nombres. Nous avons multiplié les mantisses et ajouté les exposants. Puis, comme la mantisse s'est terminée au-delà de deux, nous avons normalisé le résultat en frappant l'exposant. C'est comme lorsque nous ajustons l'exposant après avoir effectué une opération sur des nombres en notation scientifique décimale. Dans chaque cas, les valeurs avec lesquelles nous avons travaillé avaient une représentation finie en binaire, et donc les valeurs produites par les opérations de multiplication et d'addition de base produisaient également des valeurs avec une représentation finie.

Maintenant, considérons comment nous diviserions 61 par 10. Nous commencerions par diviser les mantisses, 1,90625 et 1,25. En décimal, cela donne 1,525, un joli nombre court. Mais qu'est-ce que c'est si nous le convertissons en binaire? Nous le ferons de la manière habituelle - en soustrayant la plus grande puissance de deux dans la mesure du possible, tout comme la conversion de décimales entières en binaires, mais nous utiliserons des puissances négatives de deux:

1,525 - 1 * 2 ^ 0 -> 1
0,525 - 1 * 2 ^ -1 -> 1
0,025 - 0 * 2 ^ -2 -> 0
0,025 - 0 * 2 ^ -3 -> 0
0,025 - 0 * 2 ^ -4 -> 0
0,025 - 0 * 2 ^ -5 -> 0
0,025 - 1 * 2 ^ -6 -> 1
0,009375 - 1 * 2 ^ -7 -> 1
0,0015625 - 0 * 2 ^ -8 -> 0
0,0015625 - 0 * 2 ^ -9 -> 0
0,0015625 - 1 * 2 ^ -10 -> 1
0,0005859375 - 1 * 2 ^ -11 -> 1
0,00009765625 ...

Euh oh. Maintenant, nous avons des ennuis. Il s'avère que 1.90625 / 1.25 = 1.525, est une fraction répétitive lorsqu'elle est exprimée en binaire: 1.11101b / 1.01b = 1.10000110011 ... b Nos machines ont seulement tellement de bits pour contenir cette mantisse et donc elles vont juste arrondir la fraction et assumer des zéros au-delà d'un certain point. L'erreur que vous voyez lorsque vous divisez 61 par 10 est la différence entre:

1.100001100110011001100110011001100110011 ... b * 2 ^ 10b
et, par exemple:
1.100001100110011001100110b * 2 ^ 10b

C'est cet arrondi de la mantisse qui conduit à la perte de précision que nous associons aux valeurs à virgule flottante. Même lorsque la mantisse peut être exprimée exactement (par exemple, en ajoutant simplement deux nombres), nous pouvons toujours obtenir une perte numérique si la mantisse a besoin de trop de chiffres pour tenir après la normalisation de l'exposant.

En fait, nous faisons ce genre de chose tout le temps lorsque nous arrondissons des nombres décimaux à une taille gérable et que nous donnons simplement les premiers chiffres de celui-ci. Parce que nous exprimons le résultat en décimal, cela semble naturel. Mais si nous arrondissions une décimale, puis la convertissons en une base différente, cela semblerait aussi laid que les décimales que nous obtenons en raison de l'arrondi en virgule flottante.

C'est une bonne question.

Toute votre question est basée sur "comment représenter un nombre?"

TOUS les nombres peuvent être représentés avec une représentation décimale ou avec une représentation binaire (complément à 2). Tous !!

MAIS certains (la plupart d'entre eux) nécessitent un nombre infini d'éléments ("0" ou "1" pour la position binaire, ou "0", "1" à "9" pour la représentation décimale).

Comme 1/3 en représentation décimale (1/3 = 0,3333333 ... <- avec un nombre infini de "3")

Comme 0,1 en binaire (0,1 = 0,00011001100110011 .... <- avec un nombre infini de "0011")

Tout est dans ce concept. Puisque votre ordinateur ne peut considérer qu'un ensemble fini de chiffres (décimal ou binaire), seuls certains nombres peuvent être représentés exactement dans votre ordinateur ...

Et comme l'a dit Jon, 3 est un nombre premier qui n'est pas un facteur de 10, donc 1/3 ne peut pas être représenté avec un nombre fini d'éléments dans la base 10.

Même avec une arithmétique avec une précision arbitraire, le système de position de numérotation dans la base 2 n'est pas en mesure de décrire complètement 6.1, bien qu'il puisse représenter 61.

Pour 6.1, nous devons utiliser une autre représentation (comme la représentation décimale, ou IEEE 854 qui autorise la base 2 ou la base 10 pour la représentation des valeurs à virgule flottante)

Si vous faites un nombre suffisamment grand avec une virgule flottante (comme cela peut le faire avec des exposants), vous vous retrouverez également avec une inexactitude devant la virgule décimale. Je ne pense donc pas que votre question soit entièrement valable parce que la prémisse est fausse; ce n'est pas le cas que le décalage de 10 créera toujours plus de précision, car à un moment donné, le nombre à virgule flottante devra utiliser des exposants pour représenter la grandeur du nombre et perdra ainsi une certaine précision.

Je suis surpris que personne ne l'ait encore déclaré: utilisez des fractions continues . Tout nombre rationnel peut être représenté de manière finie en binaire de cette façon.

Quelques exemples:

1/3 (0,3333 ...)

0; 3

5/9 (0,5555 ...)

0; 1, 1, 4

10/43 (0,232558139534883720930 ...)

0; 4, 3, 3

9093/18478 (0,49209871198181621387596060179673 ...)

0; 2, 31, 7, 8, 5

À partir d'ici, il existe une variété de façons connues de stocker une séquence d'entiers en mémoire.

En plus de stocker votre numéro avec une précision parfaite, les fractions continues ont également d'autres avantages, comme la meilleure approximation rationnelle. Si vous décidez de terminer la séquence de nombres dans une fraction continue au début, les chiffres restants (lorsqu'ils sont recombinés en une fraction) vous donneront la meilleure fraction possible. Voici comment les approximations de pi sont trouvées:

La fraction continue de Pi:

3; 7, 15, 1, 292 ...

En terminant la séquence à 1, cela donne la fraction:

355/113

ce qui est une excellente approximation rationnelle.

Dans l'équation

2^x = y ;  
x = log(y) / log(2)

Par conséquent, je me demandais simplement si nous pouvions avoir un système de base logarithmique pour le binaire comme,

 2^1, 2^0, 2^(log(1/2) / log(2)), 2^(log(1/4) / log(2)), 2^(log(1/8) / log(2)),2^(log(1/16) / log(2)) ........

Cela pourrait résoudre le problème, donc si vous vouliez écrire quelque chose comme 32.41 en binaire, ce serait

2^5 + 2^(log(0.4) / log(2)) + 2^(log(0.01) / log(2))

Ou

2^5 + 2^(log(0.41) / log(2))

Le problème est que vous ne savez pas vraiment si le nombre est exactement 61,0. Considère ceci:

float a = 60;
float b = 0.1;
float c = a + b * 10;

Quelle est la valeur de c? Ce n'est pas exactement 61, car b n'est pas vraiment 0,1 car .1 n'a pas une représentation binaire exacte.

Il y a un seuil parce que la signification du chiffre est passée d'entier à non entier. Pour représenter 61, vous avez 6 * 10 ^ 1 + 1 * 10 ^ 0; 10 ^ 1 et 10 ^ 0 sont tous deux des entiers. 6,1 est 6 * 10 ^ 0 + 1 * 10 ^ -1, mais 10 ^ -1 est 1/10, ce qui n'est certainement pas un entier. Voilà comment vous vous retrouvez à Inexactville.

Un parallèle peut être fait de fractions et de nombres entiers. Certaines fractions, par exemple 1/7, ne peuvent pas être représentées sous forme décimale sans beaucoup et beaucoup de décimales. Parce que la virgule flottante est binaire, les cas spéciaux changent, mais le même genre de problèmes de précision se présente.

Il existe un nombre infini de nombres rationnels et un nombre fini de bits pour les représenter. Voir http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems .

Le nombre 61,0 a en effet une opération à virgule flottante exacte - mais ce n'est pas vrai pour tous les entiers. Si vous écriviez une boucle qui en ajoutait une à la fois à un nombre à virgule flottante double précision et à un entier 64 bits, vous atteindriez finalement un point où l'entier 64 bits représente parfaitement un nombre, mais le point flottant ne ... car il n'y a pas assez de bits significatifs.

Il est juste beaucoup plus facile d'atteindre le point d'approximation sur le côté droit de la virgule décimale. Si vous avez commencé à écrire tous les nombres en virgule flottante binaire, cela aurait plus de sens.

Une autre façon de penser est que lorsque vous notez que 61,0 est parfaitement représentable en base 10, et que le décalage de la virgule ne change pas cela, vous effectuez une multiplication par des puissances de dix (10 ^ 1, 10 ^ -1 ). En virgule flottante, la multiplication par des puissances de deux n'affecte pas la précision du nombre. Essayez de prendre 61,0 et de le diviser par trois à plusieurs reprises pour une illustration de la façon dont un nombre parfaitement précis peut perdre sa représentation précise.

vous connaissez des nombres entiers non? chaque bit représente 2 ^ n

2 ^ 4 = 16
2 ^ 3 = 8
2 ^ 2 = 4
2 ^ 1 = 2
2 ^ 0 = 1

bien c'est la même chose pour la virgule flottante (avec quelques distinctions) mais les bits représentent 2 ^ -n 2 ^ -1 = 1/2 = 0,5
2 ^ -2 = 1 / (2 * 2) = 0,25
2 ^ -3 = 0,125
2 ^ -4 = 0,0625

Représentation binaire à virgule flottante:

signe Fraction exposante (je pense que invisible 1 est ajouté à la fraction)
B11 B10 B9 B8 B7 B6 B5 B4 B3 B2 B1 B0

La réponse au score élevé ci-dessus l'a cloué.

D'abord, vous mélangiez la base 2 et la base 10 dans votre question, puis lorsque vous mettez un nombre sur le côté droit qui n'est pas divisible dans la base, vous rencontrez des problèmes. Comme 1/3 en décimal parce que 3 n'entre pas dans une puissance de 10 ou 1/5 en binaire qui n'entre pas dans une puissance de 2.

Un autre commentaire bien que n'utilisez JAMAIS égal avec des nombres à virgule flottante, point. Même s'il s'agit d'une représentation exacte, il existe certains nombres dans certains systèmes à virgule flottante qui peuvent être représentés avec précision de plusieurs façons (IEEE est mauvais à ce sujet, c'est une horrible spécification à virgule flottante pour commencer, alors attendez-vous à des maux de tête). Pas de différence ici 1/3 n'est pas égal au nombre sur votre calculatrice 0,3333333, quel que soit le nombre de 3 à droite de la virgule décimale. Il est ou peut être suffisamment proche mais n'est pas égal. vous vous attendez donc à ce que quelque chose comme 2 * 1/3 ne soit pas égal à 2/3 selon l'arrondi. N'utilisez jamais égal avec virgule flottante.

Comme nous l'avons vu, en arithmétique à virgule flottante, la décimale 0,1 ne peut pas être parfaitement représentée en binaire.

Les représentations en virgule flottante et en nombre entier fournissent des grilles ou des réseaux pour les nombres représentés. Une fois l'arithmétique effectuée, les résultats tombent de la grille et doivent être replacés sur la grille en arrondissant. L'exemple est 1/10 sur une grille binaire.

Si nous utilisons une représentation décimale codée binaire comme l'a suggéré un gentleman, serions-nous en mesure de conserver les nombres sur la grille?