Combien y a-t-il de nombres doubles entre 0.0 et 1.0?

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

De nombreux générateurs de nombres aléatoires (pseudo) 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 le double est un nombre à virgule flottante et a donc une précision finie.

Donc, les questions sont les suivantes:

  1. Combien y a-t-il de nombres double 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?

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

Les double Java sont au format IEEE-754 , ils ont donc une fraction de 52 bits; entre deux puissances adjacentes de deux (y compris une et exclusive de la suivante), il y aura donc 2 à la 52ème puissance différente des double (4503599627370496 d’entre elles). Par exemple, il s’agit du nombre de double distincts compris entre 0,5 inclus et 1,0 exclu, et exactement ce nombre se situe également entre 1,0 inclus et 2,0 exclu, et ainsi de suite.

Compter les doubles entre 0.0 et 1.0 est plus difficile que de le faire entre deux puissances, car il y a beaucoup de puissances de deux incluses dans cette plage, et on entre aussi dans les problèmes épineux des nombres dénormalisés. 10 des 11 bits des exposants couvrent la plage en question, donc, en incluant les nombres dénormalisés (et je pense à quelques types de NaN ), vous auriez 1024 fois le double comme entre deux puissances – pas plus de 2**62 au total quand même. Hors dénormalisation & c, je crois que le compte serait 1023 fois 2**52 .

Pour une plage arbitraire telle que “100 à 100.1”, c’est encore plus difficile car la limite supérieure ne peut pas être exactement représentée par un double (ne représentant pas un multiple exact d’une puissance de deux). Comme approximation pratique, puisque la progression entre les puissances de deux est linéaire, on pourrait dire que cette plage est de 0.1 / 64 ème de la plage entre les puissances environnantes de deux (64 et 128), donc vous vous attendez à

 (0.1 / 64) * 2**52 

distinct double s – qui vient à 7036874417766.4004 … donner ou prendre un ou deux ;-).

Chaque valeur double dont la représentation est comprise entre 0x0000000000000000 et 0x3ff0000000000000 se situe dans l’intervalle [0.0, 1.0]. C’est (2 ^ 62 – 2 ^ 52) des valeurs distinctes (plus ou moins un couple selon que vous comptez les points limites).

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

L’intervalle [100.0, 101.0] correspond aux représentations entre 0x4059000000000000 et 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 ne peut être représenté en double précision, et il n’ya pas de doublons entre eux. Les deux nombres à double précision les plus proches sont:

 99999999999999982163600188718701095... 

et

 10000000000000000159028911097599180... 

D’autres ont déjà expliqué qu’il y avait environ 2 x 62 doubles dans l’intervalle [0,0, 1,0].
(Pas vraiment surprenant: il y a presque 2 ^ 64 doubles finis distincts; la moitié d’entre eux sont positifs, et environ la moitié d’entre eux sont <1,0.)

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

L’article Le nouveau calcul de Java, Partie 2: Les nombres à virgule flottante d’IBM offre l’extrait de code suivant pour résoudre ce problème (dans floats, mais je suppose que cela fonctionne également pour les doubles):

 public class FloatCounter { public static void main(Ssortingng[] 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 inclusivement; grande mais à peine l'infini infini des nombres réels qui existent dans cette gamme. Les nombres successifs sont séparés par environ 0,0000001. Cette distance est appelée ULP pour l’unité de moindre précision ou unité à la dernière place.

  1. 2 ^ 53 – la taille du significande / mantisse d’un nombre à virgule flottante de 64 bits incluant le bit caché.
  2. En gros, le sifnificand est fixe mais l’exposant change.

Voir l’ article de Wikipedia pour plus d’informations.

Le double Java est un numéro binary64 IEEE 754.

Cela signifie que nous devons prendre en compte:

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

Cela signifie essentiellement qu’il ya un total de 2 ^ 62-2 ^ 52 + 1 de doubles représentations possibles qui, selon la norme, se situent entre 0 et 1. Notez que 2 ^ 52 + 1 consiste à éliminer les cas des valeurs non normalisées. 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 parce que les nombres entiers de bord peuvent ne pas être représentables de manière précise dans la représentation IEEE 754, et parce que d’autres bits utilisés dans l’exposant peuvent représenter les nombres. les différentes valeurs.