Y a-t-il des nombres qui ne sont pas représentables en base 10 mais qui peuvent être représentés en base 2?

42

C#a le decimaltype utilisé pour les nombres nécessitant une représentation exacte en base 10. Par exemple, 0.1ne peut pas être représenté en base 2 (par exemple, floatet double) et sera toujours une approximation lorsqu'il est stocké dans des variables de ces types.

Je me demandais si le fait inverse était également possible. Existe-t-il des nombres qui ne sont pas représentables en base 10 mais qui peuvent être représentés en base 2 (dans ce cas, je souhaiterais utiliser un à la floatplace d'un decimalpour les traiter)?

Max
la source
14
+1 à la question, mais la balise c # est-elle vraiment applicable ici? D'autres langues ont aussi le type décimal.
Patrick M
1
@ Max: À titre d'exercice, je vous suggère d'imaginer convertir manuellement un nombre de base 2 en base 10. Par exemple, pour calculer la valeur de 0.11_b2, écrivez-le sous forme de 0.5 + 0.5 * 0.5. Existe-t-il une étape qui pourrait échouer ou donner lieu à une répétition du nombre décimal? Personnellement, je trouve que cet exercice fait un excellent travail pour comprendre une intuition sur les nombres de base 2. Je suppose que l’on pourrait aller plus loin et transformer cet exercice en une preuve par construction.
Brian
Ah, mais tu as tort. 1/1010
Xavier J
3
@Ramhound Etant donné les limites de mémoire, le binaire peut représenter 0.0999999....998..exactement, mais pas le nombre entier 0.1. Des approximations telles que l'arrondi au centième le plus proche 0.100sont un problème d'implémentation qui implique de ne pas vous montrer tous les chiffres et de les arrondir.
Izkata
1
Eh bien, il est possible de créer un mécanisme d’encodage FP permettant à «0.1» d’être représenté exactement. Un tel codage ne fait que déplacer les ensembles de tranches de numéros FP qui peuvent et ne peuvent pas être représentés.
Martin James

Réponses:

104

Voici la clé de votre dilemme: 10le produit de 2et 5. Vous pouvez représenter n’importe quel nombre exactement en décimales base 10, c’est k * 1/2 n * 1/5 mk, net msont des entiers.

Autrement dit - si le nombre ndans 1 / n contient un facteur qui ne fait pas partie des facteurs de la base, le nombre ne pourra pas être représenté exactement par un nombre fixe de chiffres dans le développement binaire / décimal / quel que soit nombre - il aura une partie répétitive. Par exemple, 1/15 = 0,0666666666 .... car 3 (15 = 3 * 5) n'est pas un facteur de 10.

Ainsi, tout ce qui peut être représenté en base 2 exactement (k * 1/2 n ) peut être représenté en base 10 exactement.

Au-delà de cela, il y a la question du nombre de chiffres / bits que vous utilisez pour représenter le nombre. Il y a des nombres qui peuvent être représentés exactement dans une base, mais cela prend plus qu'un certain nombre de chiffres / bits à faire.


En binaire, le nombre 1/10, qui est commodément 0,1 en décimal, ne peut pas être représenté par un nombre pouvant être représenté par un nombre fixe de bits en binaire. Au lieu de cela, le nombre est 0.00011001100110011 ... 2 (avec la partie 0011 répétée pour toujours).

Regardons le numéro 1 2 /1010 2 un peu plus près.

          ____                  
       0.00011                  
     + ---------                 
1010 | 1,00000                  
       0                        
       -                       
       dix                      
         0                      
       ----                     
       1 00 --------- +          
          0 |          
       ----- |          
       1 000 |          
           0 |          
       ------ | en répétant
       1 0000 | bloc    
         1010 |          
       ------ |          
          1100 |          
          1010 |          
          ---- |          
            100 ---- +          

C'est exactement le même type de chose que vous obtenez lorsque vous essayez de faire la division longue pour 1/3.

1/10, lorsque factorisé vaut 1 / (2 1 * 5 1 ). Pour la base 10 (ou tout multiple de 10), ce numéro se termine et est appelé un nombre normal . Une expansion décimale qui se répète est appelée décimale répétitive et les nombres qui durent indéfiniment sans se répéter sont des nombres irrationnels.

Le calcul derrière ce Delves dans le petit théorème de Fermat ... et une fois que vous commencez à dire Fermat ou théorème, il devient une question Math.SE .

Y a-t-il des nombres qui ne sont pas représentables en base 10 mais qui peuvent être représentés en base 2?

La réponse est non'.

Donc, à ce stade, nous devrions tous être clairement conscients que tout développement binaire de longueur fixe d’un nombre rationnel peut être représenté par un développement décimal de longueur fixe.


Permet de regarder de plus près à la décimale en C # qui nous amène à virgule flottante décimal dans .NET et étant donné l'auteur, j'accepte que thats comment ça marche.

Le type décimal a les mêmes composants que tout autre nombre à virgule flottante: une mantisse, un exposant et un signe. Comme d'habitude, le signe n'est qu'un bit, mais il y a 96 bits de mantisse et 5 bits d'exposant. Cependant, toutes les combinaisons d’exposants ne sont pas valides. Seules les valeurs de 0 à 28 fonctionnent et elles sont toutes négatives: la valeur numérique est . Cela signifie que les valeurs maximales et minimales du type sont +/- (2 96 -1) et que le plus petit nombre non nul en termes de magnitude absolue est 10 -28 .sign * mantissa / 10exponent

Je ferai remarquer tout de suite que, du fait de cette mise en œuvre, il y a des nombres dans le doubletype qui ne peuvent pas être représentés decimal- ceux qui sont hors de portée. Double.Epsilonest 4.94065645841247e-324ce qui ne peut pas être représenté dans un decimal, mais peut dans un double.

Toutefois, dans la plage que peut représenter le nombre décimal, il a plus de bits de précision que les autres types natifs et peut les représenter sans erreur.

Il y a d'autres types qui circulent. Il existe un BigInteger dans C # qui peut représenter un entier arbitrairement grand. Il n'y a pas d' équivalent à Java BigDecimal (qui peut représenter des nombres avec décimales jusqu'à 2 32 chiffres longs - ce qui est une gamme importante) exactement . Cependant, si vous fouillez un peu, vous pouvez trouver des implémentations roulées à la main.

Certaines langues ont aussi un type de données rationnel qui vous permet de représenter exactement les rationnels (donc 1/3 est égal à 1/3).


Spécifiquement pour C # et le choix de float ou rationnel, je laisserai la parole à Jon Skeet de la pinte flottante Decimal dans .NET :

La plupart des applications métier devraient probablement utiliser des valeurs décimales plutôt que des valeurs flottantes ou doubles. Ma règle empirique est que les valeurs artificielles telles que la monnaie sont généralement mieux représentées avec une virgule flottante décimale: le concept d’exactement 1,25 dollar est tout à fait raisonnable, par exemple. Pour les valeurs du monde naturel, telles que les longueurs et les poids, les types à virgule flottante binaire ont plus de sens. Même s'il existe un "exactement 1,25 mètre" théorique, cela ne se produira jamais: vous ne pourrez certainement jamais mesurer les longueurs exactes, et il est peu probable qu'elles existent même au niveau atomique. Nous sommes habitués à une certaine tolérance.

Communauté
la source
+1 pour une explication mathématique claire et concise. Et pour répondre à la version plus générale de la question posée dans le titre, un exemple de nombre non représentable en base 10 est 1/3.
Doval
@Doval Je soupçonne qu'il y a un problème dans mon raisonnement ou dans l'explication qu'une personne davantage orientée vers les mathématiques pourrait signaler ... mais je pense que je suis sur la bonne voie si tel est le cas.
"Relativement premier" dans ce cas signifie simplement "pas un facteur de", non? Y a-t-il une relation mathématique plus profonde qui me manque?
Patrick M
1
Ah, donc, si je comprends bien, n = 15et b = 10ne sont pas relativement premiers ("ne partage aucun facteur positif commun (diviseurs) sauf 1") car ils partagent le facteur 5. La clé est que tous les facteurs de 15 (5 et 3) ne sont pas aussi des facteurs de 10. (Existe-t-il un mot pour indiquer des nombres qui partagent ou non tous les facteurs communs?) Je pense que cela est parfaitement enveloppé dans votre k, n, méquation, mais pour bien comprendre, j’aurais besoin de voir un complot en 3D. Quoi qu'il en soit, vous avez bien mérité une +1.
Patrick M
1
@PatrickM: "De plus: y a-t-il un mot pour indiquer les nombres qui partagent ou non tous les facteurs communs?": Tout entier est un facteur en lui-même, donc si tous les facteurs de m sont des facteurs de n , alors il suit trivialement que m est un facteur de n . Comme vous le savez bien, un terme est facteur . Un autre est diviseur .
Ruakh
6

Une fois que vous sortez de la plage de valeurs acceptables, la réponse est oui. Cela dit, presque tout dans la fourchette aura une représentation. Référence décimale C # Bien que cela ne soit pas indiqué dans la spécification, les nombres irrationnels ne peuvent pas être représentés exactement (par exemple, e 1 , pi, la racine carrée de 2, etc.).

Le mot clé décimal désigne un type de données 128 bits. Comparé aux types à virgule flottante, le type décimal a une précision plus grande et une plage plus petite, ce qui le rend approprié pour les calculs financiers et monétaires. La plage approximative et la précision pour le type décimal sont indiquées dans le tableau suivant.

Précision: 28-29 chiffres significatifs

1 Merci à MichaelT de m'avoir rappelé un autre nombre irrationnel.

Adam Zuckerman
la source
2
@Magus considère le nombre irrationnel e(2,71 ...). Le log naturel - ln (x) est log base e. Ainsi, les bases irrationnelles existent et sont utiles. Je ne suis pas sûr de l'utilité particulière de la base pi, mais cela ne veut pas dire qu'elle n'est pas utilisée quelque part.
6
@ Max, tu t'intéresses de plus en plus aux questions de mathématiques. Vous pouvez trouver Si un nombre est irrationnel en base 10, est-il irrationnel dans d'autres bases? être une lecture utile et un point de départ pour plus de questions de théorie des nombres.
2
1/3 n'est pas irrationnel.
Adam Zuckerman
2
Le PO a posé des questions sur la base 10 (dix). Créer un système de numération à partir de n'importe quoi vous permettra d'exprimer n'importe quoi en 10. Selon l'article de Wikipedia , utiliser un nombre irrationnel comme base ne le rend pas rationnel. Les nombres rationnels peuvent être exprimés sous forme d'entiers pour le numérateur et le dénominateur, en répétant des nombres dans une décimale ou une terminaison finie de nombres dans une décimale.
Adam Zuckerman
5
@FrustratedWithFormsDesigner L'irrationalité n'a rien à voir avec les bases. Eh bien, c'est une exagération, mais c'est l'irrationalité qui a des implications sur la représentation du nombre dans différentes bases (par exemple, si elle a des chiffres infinis non répétitifs), et non l'inverse. Lisez la question de math.se lien ci - dessus: math.stackexchange.com/questions/625473/...
1

Un type à virgule flottante de base deux serait capable de représenter avec précision de nombreuses valeurs qu'un type de base dix de même taille ne pourrait pas. Toute valeur qui serait exactement représentable par un type de base 2 d'une certaine taille serait exactement représentable dans un type de base dix d'une taille suffisante. La taille requise pour un type purement en base dix pour représenter toutes les valeurs d'un nombre à virgule flottante binaire dépend de la plage de l'exposant du type binaire; des centaines de bits pour un float, ou des milliers pour un double.

Cela étant dit, le Decimaltype est suffisamment grand pour pouvoir être utilisé comme type "universel", capable de contenir la valeur de toute autre primitive numérique et de fournir quelques autres fonctionnalités supplémentaires (si rien d'autre, utilisez un bit pour indiquer si la valeur stockée est le résultat de la conversion de double, et si ce bit est défini, utilisez 64 bits pour conserver la valeur en question). Microsoft a toutefois choisi de ne pas le faire. En conséquence, la conversion d'un doubleà Decimaléchouera complètement pour les grandes valeurs, entraînera les petites valeurs doivent être arrondies à 1E-28 le plus proche. En outre, même dans la plage dynamique dedecimal, la méthode de conversion ne sera pas "aller-retour". Par exemple, évaluer 1,0 / 3,0 en tant que double donnera 0,3333333333333333148, mais le convertir en nombre décimal donnera 0,333333333333333m et le convertir en double produirait 0,3333333333333329818.

supercat
la source