Combien de nombres doubles y a-t-il entre 0,0 et 1,0?

94

C'est quelque chose qui me préoccupe depuis des années, mais je n'ai jamais pris le temps de le demander auparavant.

De nombreux (pseudo) générateurs de nombres aléatoires génèrent un nombre aléatoire compris entre 0,0 et 1,0. Mathématiquement, il y a des nombres infinis dans cette plage, mais doublec'est un nombre à virgule flottante, et a donc une précision finie.

Les questions sont donc:

  1. Combien de doublenombres y a-t-il entre 0,0 et 1,0?
  2. Y a-t-il autant de nombres entre 1 et 2? Entre 100 et 101? Entre 10 ^ 100 et 10 ^ 100 + 1?

Remarque: si cela fait une différence, je suis particulièrement intéressé par la définition de Java double.

lubrifiants polygènes
la source

Réponses:

68

Les Java doublesont au format IEEE-754 , ils ont donc une fraction de 52 bits; entre deux puissances adjacentes quelconques de deux (dont une incluse et excluant la suivante), il y aura donc 2 à la 52e puissance doubles différentes (c'est-à-dire 4503599627370496 d'entre elles). Par exemple, c'est le nombre de doubles distincts entre 0,5 inclus et 1,0 exclus, et exactement ce nombre se situe également entre 1,0 inclus et 2,0 exclus, et ainsi de suite.

Compter doublesentre 0,0 et 1,0 est plus difficile que de le faire entre des puissances de deux, car il y a de nombreuses puissances de deux comprises dans cette gamme, et, aussi, on entre dans les questions épineuses des nombres dénormalisés. 10 des 11 bits des exposants couvrent la plage en question, donc, y compris les nombres dénormalisés (et je pense que quelques types de NaN), vous auriez 1024 fois le doubles entre les puissances de deux - pas plus que le 2**62total de toute façon . Hors dénormalisé & c, je crois que le décompte serait de 1023 fois 2**52.

Pour une plage arbitraire comme "100 à 100,1", c'est encore plus difficile car la limite supérieure ne peut pas être représentée exactement comme un double(n'étant pas un multiple exact d'une puissance de deux). En guise d'approximation pratique, puisque la progression entre les puissances de deux est linéaire, vous pourriez dire que ladite plage est 0.1 / 64la plage entre les puissances environnantes de deux (64 et 128), donc vous vous attendez à environ

(0.1 / 64) * 2**52

doubles distincts - ce qui revient à 7036874417766.4004... donner ou prendre un ou deux ;-).

Alex Martelli
la source
@Alex: juste pour noter, quand j'ai écrit 100 à 100,1 j'ai mal écrit. Je voulais dire 100 à 101. Fondamentalement, entre N et N + 1 pour N arbitraire
polygenelubricants
4
@Alex: alors permettez-moi de clarifier les choses: il ne peut y avoir plus de 2**64valeurs doubles possibles (car c'est un type 64 bits), et apparemment une ÉNORME proportion de ces valeurs se situe entre 0..1?
polygenelubricants
9
@polygène, oui et oui - en particulier, environ un quart des valeurs possibles (pour toute représentation en virgule flottante "normale" de toute base et exposant par rapport aux longueurs de fraction) se situent entre 0,0 et 1,0 (un autre quart entre 1,0 et l'infini, et le moitié restante sur la moitié négative de l'axe réel). Essentiellement, la moitié des valeurs de l'exposant (avec un biais normal, à mi-chemin dans sa plage) représentent des puissances négatives de la base, donc des nombres <1,0.
Alex Martelli
8
@polygenelubricants: pour de nombreuses applications, la plage entre 0 et 1 est beaucoup, beaucoup plus importante et intéressante que la plage entre 100 et 101, c'est pourquoi elle obtient une plus grande part des valeurs. Par exemple, en physique, vous devez souvent gérer des valeurs ridiculement petites comme la constante gravitationnelle de Newton à 6,67e-11. Avoir une bonne précision est plus utile qu'entre 100 et 101. Lisez floating-point-gui.de pour plus d'informations.
Michael Borgwardt
1
Vous pouvez également mettre à l'échelle n'importe quel nombre entre 0,0 et 1,0, en gardant une trace de l'échelle séparément, ce qui entraîne moins d'erreur de calcul. C'est bien quand la droite numérique entière peut être mappée entre deux nombres!
codekaizen
42

Toute doublevaleur dont la représentation est comprise entre 0x0000000000000000et 0x3ff0000000000000se situe dans l'intervalle [0.0, 1.0]. C'est (2 ^ 62 - 2 ^ 52) valeurs distinctes (plus ou moins un couple selon que vous comptez les points finaux).

L'intervalle [1.0, 2.0] correspond aux représentations entre 0x3ff0000000000000et 0x400000000000000; c'est 2 ^ 52 valeurs distinctes.

L'intervalle [100,0, 101,0] correspond aux représentations entre 0x4059000000000000et 0x4059400000000000; c'est 2 ^ 46 valeurs distinctes.

Il n'y a pas de doubles entre 10 ^ 100 et 10 ^ 100 + 1 . Aucun de ces nombres n'est représentable en double précision, et il n'y a pas de doubles entre eux. Les deux nombres à double précision les plus proches sont:

99999999999999982163600188718701095...

et

10000000000000000159028911097599180...
Stephen Canon
la source
+1, pour une réponse exacte bien étayée. (Si vous êtes pointilleux sur le comptage des points de terminaison, rappelez-vous que +0,0 et -0,0 ont des représentations distinctes.)
Jim Lewis
1
+1, une telle torsion se terminant! J'avais l'impression de lire un scénario de M. Night Shyamalan!
polygenelubricants
7

D'autres ont déjà expliqué qu'il y a environ 2 ^ 62 doubles dans l'intervalle [0,0, 1,0].
(Pas vraiment surprenant: il y a près de 2 ^ 64 doubles finis distincts, de ceux -ci , la moitié sont positifs, et à peu près la moitié de ceux qui sont <1,0.)

Mais vous évoquez des générateurs de nombres aléatoires: notez qu'un générateur de nombres aléatoires générant des nombres compris entre 0,0 et 1,0 ne peut en général pas produire tous ces nombres; typiquement, il ne produira que des nombres de la forme n / 2 ^ 53 avec n un entier (voir par exemple la documentation Java pour nextDouble ). Il n'y a donc généralement qu'environ 2 ^ 53 (+/- 1, selon les points de terminaison inclus) des valeurs possibles pour la random()sortie. Cela signifie que la plupart des doubles dans [0.0, 1.0] ne seront jamais générés.

Mark Dickinson
la source
3

L'article Les nouvelles mathématiques de Java, Partie 2: Nombres à virgule flottante d'IBM propose l'extrait de code suivant pour résoudre ce problème (en flottants, mais je suppose que cela fonctionne également pour les doubles):

public class FloatCounter {

    public static void main(String[] args) {
        float x = 1.0F;
        int numFloats = 0;
        while (x <= 2.0) {
            numFloats++;
            System.out.println(x);
            x = Math.nextUp(x);
        }
        System.out.println(numFloats);
    }
}

Ils ont ce commentaire à ce sujet:

Il s'avère qu'il y a exactement 8 388 609 flottants entre 1,0 et 2,0 inclus; grande mais à peine l'infini innombrable de nombres réels qui existent dans cette gamme. Les nombres successifs sont distants d'environ 0,0000001. Cette distance est appelée ULP pour l'unité de moindre précision ou unité en dernier lieu.

Mark Rushakoff
la source
Oui, mais c'est pour float, pas double - floats ont 23 bits de fraction, donc 2**23 -> 8388608des valeurs différentes entre les puissances adjacentes de deux (la partie "inclusive" signifie bien sûr que vous devez en compter une de plus, la puissance suivante de deux). doubles ont des fractions de 52 bits!
Alex Martelli
1
@Alex: Je suppose que je vais devoir laisser le programme (modifié pour les doubles) en cours d'exécution jusqu'à la fin de l'univers environ avant que je puisse obtenir les résultats ... :(
Mark Rushakoff
1
Je me sens stupide; Je viens d'écrire l' doubleéquivalent et je me suis dit "Hé, je vais répondre à ma propre question dans environ 5 minutes ..."
polygenelubricants
1
@polygene: Cela ressemble à un problème du projet Euler où l'approche évidente est impossible à calculer, mais il doit y avoir une formule brillamment simple à résoudre pour le cas arbitraire ...
Mark Rushakoff
2
peut-être pas avec un supercalculateur vraiment suralimenté: sur une machine ne prenant qu'une nanoseconde pour exécuter la boucle interne, compter doubleentre des puissances adjacentes de deux prendrait environ 52 jours ( printlnbien sûr, il serait très peu probable qu'il fonctionne aussi vite quoi qu'il arrive, donc Supposons qu'une déclaration disparaisse ;-). Je pense qu'il est possible de prendre un an ou moins sur une machine puissante mais réaliste ;-).
Alex Martelli
2
  1. 2 ^ 53 - la taille de la significande / mantisse d'un nombre à virgule flottante de 64 bits, y compris le bit caché.
  2. À peu près oui, car le sifnificand est fixe mais l'exposant change.

Voir l' article wikipedia pour plus d'informations.

Yann Ramin
la source
Votre réponse pour 2 contredit ma compréhension du fonctionnement de FP.
polygenelubricants
Je pense 1est faux parce que le peu caché est toujours un - donc 2^52, pas 2^53 distinctes des valeurs (entre les puissances adjacentes de deux, celui qui est inclus et exclus le prochain - pas ! Entre 0,0 et 1,0).
Alex Martelli
1

Le double Java est un nombre binaire64 IEEE 754.

Cela signifie que nous devons considérer:

  1. Mantissa est 52 bits
  2. L'exposant est un nombre de 11 bits avec un biais de 1023 (c'est-à-dire avec 1023 ajouté)
  3. Si l'exposant est tout 0 et que la mantisse est non nulle, alors le nombre est dit non normalisé

Cela signifie essentiellement qu'il y a un total de 2 ^ 62-2 ^ 52 + 1 de doubles représentations possibles qui, selon la norme, sont comprises entre 0 et 1. Notez que 2 ^ 52 + 1 consiste à supprimer les cas des non normalisés Nombres.

Rappelez-vous que si la mantisse est positive mais que l'exposant est négatif, le nombre est positif mais inférieur à 1 :-)

Pour les autres nombres, c'est un peu plus difficile car les nombres entiers de bord peuvent ne pas être représentables de manière précise dans la représentation IEEE 754, et parce qu'il y a d'autres bits utilisés dans l'exposant pour pouvoir représenter les nombres, donc plus le nombre est grand, plus le nombre est bas. les différentes valeurs.

njsf
la source