Zufälliges Gleitkomma-Double im inklusiven Bereich

Wir können leicht zufällige Gleitkommazahlen innerhalb eines gewünschten Bereichs erhalten [X,Y) (note that X is inclusive and Y is exclusive) with the function listed below since Math.random() (and most pseudorandom number generators, AFAIK) produce numbers in [0,1):

function randomInRange(min, max) {
  return Math.random() * (max-min) + min;
}
// Notice that we can get "min" exactly but never "max".

How can we get a random number in a desired range inclusive to both bounds, i.e. [X,Y]?

Ich nehme an, wir könnten unseren Wert von “erhöhen”. Math.random() (oder Äquivalent) durch “Rollen” der Bits von an IEEE-754 Gleitkommazahl mit doppelter Genauigkeit den maximal möglichen Wert genau auf 1,0 zu setzen, aber das scheint mühsam zu sein, besonders in Sprachen, die für Bit-Manipulation schlecht geeignet sind. Gibt es einen einfacheren Weg?

(Nebenbei, warum erzeugen Zufallszahlengeneratoren Zahlen in [0,1) instead of [0,1]?)

[Edit] Bitte beachten Sie, dass ich keine habe brauchen dafür, und ich bin mir voll bewusst, dass die Unterscheidung pedantisch ist. Einfach mal neugierig sein und auf interessante Antworten hoffen. Fühlen Sie sich frei, für das Schließen zu stimmen, wenn diese Frage unangemessen ist.

Ich glaube, es gibt eine viel bessere Entscheidung, aber diese sollte funktionieren 🙂

function randomInRange(min, max) {
  return Math.random() < 0.5 ? ((1-Math.random()) * (max-min) + min) : (Math.random() * (max-min) + min);
}

Zunächst einmal gibt es ein Problem in Ihrem Code: Versuchen Sie es randomInRange(0,5e-324) oder einfach eintreten Math.random()*5e-324 in der JavaScript-Konsole Ihres Browsers.

Selbst ohne Überlauf/Unterlauf/Denormierung ist es schwierig, zuverlässig über Gleitkommaoperationen zu argumentieren. Nach ein bisschen Graben kann ich ein Gegenbeispiel finden:

>>> a=1.0
>>> b=2**-54
>>> rand=a-2*b
>>> a
1.0
>>> b
5.551115123125783e-17
>>> rand
0.9999999999999999
>>> (a-b)*rand+b
1.0

Es ist einfacher zu erklären, warum dies mit a = 2 geschieht⁵³ und b = 0,5: 2⁵³-1 ist die nächste darstellbare Zahl nach unten. Der Standard-Rundungsmodus (“auf die nächste gerade Zahl runden”) rundet 2⁵³-0,5 aufwärts (weil 2⁵³ ist “gerade” [LSB = 0] und 2⁵³-1 ist “ungerade” [LSB = 1]), also subtrahierst du b und bekomme 2⁵³multiplizieren, um 2 zu erhalten⁵³-1 und addieren b 2 bekommen⁵³ wieder.

Um Ihre zweite Frage zu beantworten: Weil das zugrunde liegende PRNG fast immer eine Zufallszahl im Intervall generiert [0,2ⁿ-1], dh es erzeugt zufällige Bits. Es ist sehr einfach, ein geeignetes n (die Bits der Genauigkeit in Ihrer Gleitkommadarstellung) auszuwählen und durch 2 zu teilenⁿ und eine vorhersagbare Verteilung erhalten. Beachten Sie, dass einige Zahlen darin enthalten sind [0,1) that you will will never generate using this method (anything in (0,2^-53) with IEEE doubles).

It also means that you can do a[Math.floor(Math.random()*a.length)] und sorgen Sie sich nicht um Überlauf (Hausaufgabe: Beweisen Sie das in IEEE Binary Floating Point b < 1 impliziert a*b < a für positive ganze Zahl a).

Die andere schöne Sache ist, dass Sie sich jede zufällige Ausgabe x als ein Intervall vorstellen können [x,x+2^-53) (the not-so-nice thing is that the average value returned is slightly less than 0.5). If you return in [0,1]geben Sie die Endpunkte mit der gleichen Wahrscheinlichkeit wie alles andere zurück, oder sollten sie nur die halbe Wahrscheinlichkeit haben, weil sie wie alles andere nur das halbe Intervall darstellen?

Um die einfachere Frage zu beantworten, eine Zahl zurückzugeben [0,1]generiert die folgende Methode effektiv eine Ganzzahl [0,2ⁿ] (durch Generieren einer ganzen Zahl in [0,2ⁿ⁺¹-1] und wegwerfen, wenn es zu groß ist) und durch 2 teilenⁿ:

function randominclusive() {
  // Generate a random "top bit". Is it set?
  while (Math.random() >= 0.5) {
    // Generate the rest of the random bits. Are they zero?
    // If so, then we've generated 2^n, and dividing by 2^n gives us 1.
    if (Math.random() == 0) { return 1.0; }
    // If not, generate a new random number.
  }
  // If the top bits are not set, just divide by 2^n.
  return Math.random();
}

Die Kommentare implizieren Basis 2, aber ich denken die Annahmen lauten also:

• 0 und 1 sollten mit gleicher Wahrscheinlichkeit zurückgegeben werden (dh Math.random() nutzt nicht den engeren Abstand von Gleitkommazahlen in der Nähe von 0).
• Math.random() >= 0,5 mit Wahrscheinlichkeit 1/2 (sollte für gerade Basen gelten)
• Das zugrunde liegende PRNG ist gut genug, um dies zu tun.

Beachten Sie, dass Zufallszahlen immer paarweise generiert werden: die eine in der while Auf (a) folgt immer entweder die in der if oder die am Ende (b). Es ist ziemlich einfach zu überprüfen, ob es sinnvoll ist, indem man einen PRNG betrachtet, der entweder 0 oder 0,5 zurückgibt:

• a=0   b=0  : 0 zurückgeben
• a=0   b=0.5: Rückgabe 0,5
• a=0.5 b=0  : Rückkehr 1
• a=0.5 b=0.5: Schleife

Probleme:

• Die Annahmen könnten nicht wahr sein. Insbesondere besteht ein üblicher PRNG darin, die obersten 32 Bit eines 48-Bit-LCG zu nehmen (Firefox und Java tun dies). Um ein Double zu erzeugen, nehmen Sie 53 Bits von zwei aufeinanderfolgenden Ausgängen und dividieren durch 2⁵³aber einige Ausgaben sind nicht möglich (Sie können 2 nicht generieren⁵³ Ausgänge mit 48 Zustandsbits!). Ich vermute, dass einige von ihnen niemals 0 zurückgeben (unter der Annahme eines Single-Thread-Zugriffs), aber ich habe jetzt keine Lust, die Implementierung von Java zu überprüfen.
• Math.random() ist zweimal für jeden Potenzial Ausgabe als Folge der Notwendigkeit, das zusätzliche Bit zu erhalten, aber dies erlegt dem PRNG mehr Einschränkungen auf (was uns dazu zwingt, über vier aufeinanderfolgende Ausgaben des obigen LCG nachzudenken).
• Math.random() wird im Durchschnitt etwa aufgerufen vier mal pro Ausgang. Ein bisschen langsam.
• Es wirft Ergebnisse deterministisch weg (unter der Annahme eines Single-Thread-Zugriffs), sodass der Ausgaberaum ziemlich garantiert reduziert wird.

Meine Lösung für dieses Problem bestand immer darin, anstelle Ihrer Obergrenze Folgendes zu verwenden.

Math.nextAfter(upperBound,upperBound+1)

oder

upperBound + Double.MIN_VALUE

Ihr Code würde also so aussehen:

double myRandomNum = Math.random() * Math.nextAfter(upperBound,upperBound+1) + lowerBound;

oder

double myRandomNum = Math.random() * (upperBound + Double.MIN_VALUE) + lowerBound;

Dies erhöht einfach Ihre Obergrenze um das kleinste Doppelte (Double.MIN_VALUE), damit Ihre Obergrenze als Möglichkeit in die Zufallsberechnung einbezogen wird.

Dies ist eine gute Methode, da die Wahrscheinlichkeiten nicht zugunsten einer Zahl verzerrt werden.

Der einzige Fall, in dem dies nicht funktionieren würde, ist, wenn Ihre Obergrenze gleich ist Double.MAX_VALUE

Wählen Sie einfach Ihr halboffenes Intervall etwas größer, sodass Ihr ausgewähltes geschlossenes Intervall eine Teilmenge ist. Erzeuge dann die Zufallsvariable weiter, bis sie in dem geschlossenen Intervall landet.

Beispiel: Wenn Sie etwas Einheitliches wollen [3,8]dann regenerieren Sie wiederholt eine einheitliche Zufallsvariable in [3,9) until it happens to land in [3,8].

function randomInRangeInclusive(min,max) {
 var ret;
 for (;;) {
  ret = min + ( Math.random() * (max-min) * 1.1 );
  if ( ret <= max ) { break; }
 }
 return ret;
}

Hinweis: Die Häufigkeit, mit der Sie das halb geöffnete RV generieren, ist zufällig und möglicherweise unendlich, aber Sie können die erwartete Anzahl von Anrufen ansonsten so nahe wie möglich an 1 tätigen, und ich glaube nicht, dass es eine Lösung gibt, die dies nicht tut t möglicherweise unendlich oft anrufen.

Spielt das angesichts der “extrem großen” Anzahl von Werten zwischen 0 und 1 wirklich eine Rolle? Die Chancen auf eigentlich 1 zu treffen sind winzig, daher ist es sehr unwahrscheinlich, dass es einen signifikanten Unterschied zu irgendetwas macht, was Sie tun.

Was wäre eine Situation, in der Sie einen Gleitkommawert benötigen würden, um die Obergrenze einzuschließen? Für ganze Zahlen verstehe ich, aber für einen Float ist der Unterschied zwischen inklusive und exklusiv etwa 1.0e-32.

Denk darüber so. Wenn Sie sich vorstellen, dass Gleitkommazahlen eine beliebige Genauigkeit haben, sind die Chancen genau zu bekommen min sind null. So sind die Chancen zu bekommen max. Ich lasse Sie Ihre eigenen Schlüsse daraus ziehen.

Dieses ‘Problem’ ist gleichbedeutend damit, einen zufälligen Punkt auf der reellen Linie zwischen 0 und 1 zu bekommen. Es gibt kein ‘inklusiv’ und ‘exklusiv’.