Wie viele doppelte Zahlen gibt es zwischen 0,0 und 1,0?

93

Das ist etwas, woran ich seit Jahren denke, aber ich habe mir nie die Zeit genommen, danach zu fragen.

Viele (Pseudo-) Zufallszahlengeneratoren erzeugen eine Zufallszahl zwischen 0,0 und 1,0. Mathematisch gesehen gibt es in diesem Bereich unendlich viele Zahlen, die jedoch doubleeine Gleitkommazahl sind und daher eine endliche Genauigkeit haben.

Die Fragen sind also:

  1. Wie viele doubleZahlen gibt es zwischen 0,0 und 1,0?
  2. Gibt es genauso viele Zahlen zwischen 1 und 2? Zwischen 100 und 101? Zwischen 10 ^ 100 und 10 ^ 100 + 1?

Hinweis: Wenn es einen Unterschied macht, interessiert mich doubleinsbesondere die Definition von Java .

Polygenschmierstoffe
quelle

Antworten:

68

Java doubles sind im IEEE-754- Format, daher haben sie einen 52-Bit-Bruch; zwischen zwei benachbarten Zweierpotenzen (einschließlich einer und ausschließlich der nächsten) gibt es daher zwei bis 52 doublePotenzen , die sich unterscheiden (dh 4503599627370496 von ihnen). Das ist zum Beispiel die Anzahl der unterschiedlichen doubles zwischen 0,5 eingeschlossen und 1,0 ausgeschlossen, und genau so viele liegen auch zwischen 1,0 eingeschlossen und 2,0 ausgeschlossen und so weiter.

Das Zählen doubleszwischen 0,0 und 1,0 ist schwieriger als zwischen Zweierpotenzen, da in diesem Bereich viele Zweierpotenzen enthalten sind und man sich auch mit den heiklen Fragen denormalisierter Zahlen befasst. 10 der 11 Bits der Exponenten decken den fraglichen Bereich ab. Wenn Sie also denormalisierte Zahlen (und ich denke ein paar Arten von Zahlen) einschließen, hätten NaNSie das 1024-fache des doubles zwischen Zweierpotenzen - 2**62ohnehin nicht mehr als insgesamt . Ohne denormalisierte & c glaube ich, dass die Zählung 1023 mal sein würde 2**52.

Für einen beliebigen Bereich wie "100 bis 100.1" ist es noch schwieriger, da die Obergrenze nicht genau als a dargestellt werden kann double(kein exaktes Vielfaches einer Zweierpotenz). In praktischer Näherung könnte man sagen, dass der Bereich zwischen den Potenzen von zwei linear ist, da der Verlauf zwischen den Zweierpotenzen linear ist 0.1 / 64(64 und 128)

(0.1 / 64) * 2**52

verschiedene doubles - was dazu kommt 7036874417766.4004... ein oder zwei zu geben oder zu nehmen ;-).

Alex Martelli
quelle
@ Alex: Nur um zu beachten, als ich 100 bis 100,1 schrieb, habe ich falsch geschrieben. Ich meinte 100 bis 101. Grundsätzlich zwischen N und N + 1 für beliebige N.
Polygenschmierstoffe
4
@Alex: Lassen Sie mich das klarstellen: Es kann nicht mehr als 2**64mögliche Doppelwerte geben (da es sich um einen 64-Bit-Typ handelt), und anscheinend liegt ein RIESIGER Anteil dieser Werte dazwischen 0..1?
Polygenschmierstoffe
9
@polygene, ja und ja - speziell liegt etwa ein Viertel der möglichen Werte (für jede "normale" Gleitkommadarstellung einer Basis und eines Exponenten gegenüber Bruchfraktionen) zwischen 0,0 und 1,0 (ein weiteres Viertel zwischen 1,0 und unendlich und die verbleibende Hälfte auf der negativen Hälfte der realen Achse). Im Wesentlichen repräsentiert die Hälfte der Werte des Exponenten (mit einer normalen Vorspannung auf halbem Weg innerhalb seines Bereichs) negative Potenzen der Basis, daher Zahlen <1,0.
Alex Martelli
8
@polygenelubricants: Für viele Anwendungen ist der Bereich zwischen 0 und 1 viel, viel wichtiger und interessanter als der Bereich zwischen 100 und 101, deshalb erhält er einen größeren Anteil der Werte. In der Physik müssen Sie beispielsweise häufig mit lächerlich kleinen Werten wie der Newtonschen Gravitationskonstante bei 6,67e-11 umgehen. Eine gute Präzision ist nützlicher als zwischen 100 und 101. Weitere Informationen finden Sie unter float-point-gui.de .
Michael Borgwardt
1
Sie können auch eine beliebige Zahl auf 0,0 bis 1,0 skalieren, wobei Sie die Skalierung separat verfolgen und so weniger Rechenfehler erzielen. Es ist schön, wenn die gesamte Zahlenreihe zwischen zwei Zahlen abgebildet werden kann!
Codekaizen
42

Jeder doubleWert, dessen Darstellung zwischen 0x0000000000000000und 0x3ff0000000000000im Intervall [0.0, 1.0] liegt. Das sind (2 ^ 62 - 2 ^ 52) unterschiedliche Werte (plus oder minus ein Paar, je nachdem, ob Sie die Endpunkte zählen).

Das Intervall [1.0, 2.0] entspricht Darstellungen zwischen 0x3ff0000000000000und 0x400000000000000; das sind 2 ^ 52 verschiedene Werte.

Das Intervall [100.0, 101.0] entspricht Darstellungen zwischen 0x4059000000000000und 0x4059400000000000; das sind 2 ^ 46 verschiedene Werte.

Es gibt keine Doppel zwischen 10 ^ 100 und 10 ^ 100 + 1 . Keine dieser Zahlen ist mit doppelter Genauigkeit darstellbar, und es gibt keine Doppelzahlen, die zwischen ihnen liegen. Die nächsten zwei Zahlen mit doppelter Genauigkeit sind:

99999999999999982163600188718701095...

und

10000000000000000159028911097599180...
Stephen Canon
quelle
+1, für eine gut unterstützte genaue Antwort. (Wenn Sie beim Zählen der Endpunkte wählerisch sind, denken Sie daran, dass +0.0 und -0.0 unterschiedliche Darstellungen haben.)
Jim Lewis
1
+1, so ein Twist-Ende! Ich fühlte mich, als würde ich ein M. Night Shyamalan-Drehbuch lesen!
Polygenelubricants
7

Andere haben bereits erklärt, dass es im Bereich [0.0, 1.0] etwa 2 ^ 62 Doppel gibt.
(Nicht wirklich überraschend: Es gibt fast 2 ^ 64 verschiedene endliche verdoppelt, von denen, sind die Hälfte positiv, und etwa die Hälfte diejenigen sind <1,0) .

Sie erwähnen jedoch Zufallszahlengeneratoren: Beachten Sie, dass ein Zufallszahlengenerator, der Zahlen zwischen 0,0 und 1,0 generiert, im Allgemeinen nicht alle diese Zahlen erzeugen kann . Normalerweise werden nur Zahlen der Form n / 2 ^ 53 mit n einer Ganzzahl erzeugt (siehe z. B. die Java-Dokumentation für nextDouble ). Daher gibt es normalerweise nur etwa 2 ^ 53 (+/- 1, abhängig davon, welche Endpunkte enthalten sind) mögliche Werte für die random()Ausgabe. Dies bedeutet, dass die meisten Doubles in [0.0, 1.0] niemals generiert werden.

Mark Dickinson
quelle
3

Der Artikel Javas neue Mathematik, Teil 2: Gleitkommazahlen von IBM bietet das folgende Codefragment, um dies zu lösen (in Gleitkommazahlen , aber ich vermute, dass es auch für Doppel funktioniert):

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);
    }
}

Sie haben diesen Kommentar dazu:

Es stellt sich heraus, dass es genau 8.388.609 Floats zwischen 1.0 und 2.0 einschließlich gibt; groß, aber kaum die unzähligen Unendlichkeiten reeller Zahlen, die in diesem Bereich existieren. Aufeinanderfolgende Zahlen liegen etwa 0,0000001 auseinander. Dieser Abstand wird als ULP für Einheit mit der geringsten Genauigkeit oder Einheit an letzter Stelle bezeichnet.

Mark Rushakoff
quelle
Ja, aber das ist für float, nicht double - floats haben einen Bruchteil von 23 Bit, also 2**23 -> 8388608unterschiedliche Werte zwischen benachbarten Zweierpotenzen (der "inklusive" Teil bedeutet natürlich, dass Sie noch eine zählen müssen, die nächste Zweierpotenz). doubles haben 52-Bit-Brüche!
Alex Martelli
1
@ Alex: Ich denke, ich muss das Programm (modifiziert für Doppel) bis zum Ende des Universums laufen lassen, bevor ich die Ergebnisse erhalten kann ... :(
Mark Rushakoff
1
Ich fühle mich dumm; Ich schrieb gerade das doubleÄquivalent und dachte "Hey, ich werde meine eigene Frage in ungefähr 5 Minuten beantworten ..."
Polygenelubricants
1
@polygene: Dies fühlt sich wie ein Project Euler-Problem an, bei dem der offensichtliche Ansatz nicht zu berechnen ist, aber es muss eine genial einfache Formel geben, die für den willkürlichen Fall gelöst werden kann ...
Mark Rushakoff
2
Vielleicht nicht mit einem wirklich aufgeladenen Supercomputer: Auf einer Maschine, die nur eine Nanosekunde benötigt, um die innere Schleife zu betreiben, würde das Zählen doublezwischen benachbarten Zweierpotenzen ungefähr 52 Tage dauern (das printlnwäre natürlich sehr unwahrscheinlich, so schnell zu laufen, egal was passiert) Nehmen wir an, dass eine Aussage weggeht ;-). Ich denke, es ist machbar, ein Jahr oder weniger auf einer leistungsstarken, aber realistischen Maschine zu verbringen ;-).
Alex Martelli
2
  1. 2 ^ 53 - die Größe des Signifikanten / der Mantisse einer 64-Bit-Gleitkommazahl einschließlich des versteckten Bits.
  2. Etwa ja, da der Sifnificand fest ist, sich aber der Exponent ändert.

Weitere Informationen finden Sie im Wikipedia-Artikel .

Yann Ramin
quelle
Ihre Antwort für 2 widerspricht, wie ich die Arbeitsweise von FP verstehe.
Polygenschmierstoffe
Ich denke , 1falsch ist , weil der versteckte Bit ist immer - also 2^52, nicht 2^53 eindeutige Werte (zwischen benachbarten Potenzen von zwei, eines enthält und die nächsten ausgeschlossen - nicht ! Zwischen 0,0 und 1,0).
Alex Martelli
1

Das Java-Double ist eine IEEE 754-Binärzahl64.

Dies bedeutet, dass wir Folgendes berücksichtigen müssen:

  1. Mantisse ist 52 Bit
  2. Exponent ist 11-Bit-Zahl mit 1023 Bias (dh mit 1023 hinzugefügt)
  3. Wenn der Exponent alle 0 ist und die Mantisse nicht Null ist, wird die Zahl als nicht normalisiert bezeichnet

Dies bedeutet im Grunde, dass es insgesamt 2 ^ 62-2 ^ 52 + 1 mögliche Doppeldarstellungen gibt, die gemäß dem Standard zwischen 0 und 1 liegen. Beachten Sie, dass 2 ^ 52 + 1 dazu dient, die Fälle der nicht normalisierten zu entfernen Zahlen.

Denken Sie daran, dass wenn die Mantisse positiv ist, der Exponent jedoch negativ, die Zahl positiv ist, aber weniger als 1 :-)

Für andere Zahlen ist es etwas schwieriger, weil die Kanten-Ganzzahl-Zahlen in der IEEE 754-Darstellung möglicherweise nicht präzise darstellbar sind und weil im Exponenten andere Bits verwendet werden, um die Zahlen darstellen zu können. Je größer die Zahl, desto niedriger die verschiedenen Werte.

njsf
quelle