Dlaczego ta losowa wartość ma rozkład 25/75 zamiast 50/50?

Edycja: Więc w zasadzie to, co próbuję napisać, to 1-bitowy hash double.

Chcę zmapować doubledo truelub falsez szansą 50/50. W tym celu napisałem kod, który wybiera losowe liczby (tak jak na przykład, chcę tego użyć na danych z regularnościami i nadal otrzymuję wynik 50/50) , sprawdza ich ostatni bit i przyrosty, yjeśli wynosi 1, lub njeśli jest 0.

Jednak ten kod stale daje 25% yi 75% n. Dlaczego nie jest to 50/50? A skąd taka dziwna, ale prosta (1/3) dystrybucja?

public class DoubleToBoolean {
    @Test
    public void test() {

        int y = 0;
        int n = 0;
        Random r = new Random();
        for (int i = 0; i < 1000000; i++) {
            double randomValue = r.nextDouble();
            long lastBit = Double.doubleToLongBits(randomValue) & 1;
            if (lastBit == 1) {
                y++;
            } else {
                n++;
            }
        }
        System.out.println(y + " " + n);
    }
}

Przykładowe dane wyjściowe:

250167 749833

Ponieważ nextDouble działa tak: ( źródło )

public double nextDouble()
{
    return (((long) next(26) << 27) + next(27)) / (double) (1L << 53);
}

next(x)tworzy xlosowe bity.

Dlaczego to ma znaczenie? Ponieważ około połowa liczb generowanych przez pierwszą część (przed podziałem) jest mniejsza niż 1L << 52, a zatem ich znaczenie nie wypełnia całkowicie 53 bitów, które mogłaby wypełnić, co oznacza, że ​​najmniej znaczący bit znaczenia jest zawsze równy zeru.

Ze względu na ilość uwagi, którą to poświęca, oto dodatkowe wyjaśnienie, jak doublenaprawdę wygląda a w Javie (i wielu innych językach) i dlaczego ma to znaczenie w tym pytaniu.

Zasadniczo doublewygląda to tak: ( źródło )

Bardzo ważnym szczegółem niewidocznym na tym rysunku jest to, że liczby są „znormalizowane” ¹ tak, że 53-bitowy ułamek zaczyna się od 1 (wybierając taki wykładnik, że tak jest), a następnie 1 jest pomijany. Dlatego na rysunku ułamek (znacznik) przedstawia 52 bity, ale faktycznie zawiera on 53 bity.

Normalizacja oznacza, że ​​jeśli w kodzie dla nextDouble53. bitu jest ustawiony, ten bit jest niejawną wiodącą 1 i odchodzi, a pozostałe 52 bity są kopiowane dosłownie do znacznika wyniku double. Jeśli jednak ten bit nie zostanie ustawiony, pozostałe bity należy przesunąć w lewo, aż zostanie ustawiony.

Średnio połowa wygenerowanych liczb przypada na przypadek, w którym istotność nie została w ogóle przesunięta w lewo (a około połowa z nich ma 0 jako najmniej znaczący bit), a druga połowa jest przesunięta o co najmniej 1 (lub po prostu całkowicie zero), więc ich najmniej znaczący bit jest zawsze równy 0.

1: nie zawsze, oczywiście nie można tego zrobić dla zera, które nie ma najwyższego 1. Liczby te nazywane są liczbami denormalnymi lub subnormalnymi, patrz wikipedia: liczba denormalna .

Z dokumentów :

Metoda nextDouble jest implementowana przez klasę Random tak, jakby przez:

public double nextDouble() {
  return (((long)next(26) << 27) + next(27))
      / (double)(1L << 53);
}

Ale stwierdza również, co następuje (podkreślenie moje):

[We wczesnych wersjach Java wynik był nieprawidłowo obliczany jako:

 return (((long)next(27) << 27) + next(27))
     / (double)(1L << 54);

Może się to wydawać równoważne, jeśli nie lepsze, ale w rzeczywistości wprowadziło dużą niejednorodność ze względu na odchylenie w zaokrąglaniu liczb zmiennoprzecinkowych: było trzy razy bardziej prawdopodobne, że najniższy bit znaczenia będzie wynosił 0 niż to, że będzie 1 ! Ta niejednorodność prawdopodobnie nie ma większego znaczenia w praktyce, ale dążymy do doskonałości.]

Ta notatka pojawiła się przynajmniej od Javy 5 (dokumenty dla Javy <= 1.4 są za zaporą logowania, zbyt leniwe, by je sprawdzić). To ciekawe, bo problem najwyraźniej nadal istnieje nawet w Javie 8. Być może „poprawiona” wersja nigdy nie była testowana?

Ten wynik nie dziwi mnie, biorąc pod uwagę sposób reprezentacji liczb zmiennoprzecinkowych. Załóżmy, że mamy bardzo krótki typ zmiennoprzecinkowy z tylko 4 bitami dokładności. Gdybyśmy mieli wygenerować liczbę losową z przedziału od 0 do 1, rozłożoną równomiernie, byłoby 16 możliwych wartości:

0.0000
0.0001
0.0010
0.0011
0.0100
...
0.1110
0.1111

Jeśli tak wyglądali w maszynie, możesz przetestować mniej zamówiony bit, aby uzyskać dystrybucję 50/50. Jednak pływaki IEEE są reprezentowane jako potęga 2 razy mantysy; jedno pole w liczbie zmiennoprzecinkowej to potęga 2 (plus stałe przesunięcie). Potęga 2 jest tak dobrana, aby część „mantysy” była zawsze liczbą> = 1,0 i <2,0. Oznacza to, że w efekcie liczby inne niż 0.0000byłyby przedstawione w następujący sposób:

0.0001 = 2^(-4) x 1.000
0.0010 = 2^(-3) x 1.000
0.0011 = 2^(-3) x 1.100
0.0100 = 2^(-2) x 1.000
... 
0.0111 = 2^(-2) x 1.110
0.1000 = 2^(-1) x 1.000
0.1001 = 2^(-1) x 1.001
...
0.1110 = 2^(-1) x 1.110
0.1111 = 2^(-1) x 1.111

( 1Przed punktem binarnym jest domniemana wartość; dla 32- i 64-bitowych liczb zmiennoprzecinkowych żaden bit nie jest faktycznie przydzielany do przechowywania tego 1).

Ale patrząc na powyższe powinno pokazać, dlaczego, jeśli przekonwertujesz reprezentację na bity i spojrzysz na niski bit, otrzymasz zero w 75% przypadków. Wynika to z faktu, że wszystkie wartości mniejsze niż 0,5 (binarne 0.1000), co stanowi połowę możliwych wartości, mają przesunięte mantysy, powodując pojawienie się 0 w niskim bicie. Sytuacja jest zasadniczo taka sama, gdy mantysa ma 52 bity (nie licząc domniemanej 1) jak a double.

(Właściwie, jak zasugerował @sneftel w komentarzu, moglibyśmy uwzględnić więcej niż 16 możliwych wartości w dystrybucji, generując:

0.0001000 with probability 1/128
0.0001001 with probability 1/128
...
0.0001111 with probability 1/128
0.001000  with probability 1/64
0.001001  with probability 1/64
...
0.01111   with probability 1/32 
0.1000    with probability 1/16
0.1001    with probability 1/16
...
0.1110    with probability 1/16
0.1111    with probability 1/16

Ale nie jestem pewien, czy jest to rodzaj dystrybucji, którego spodziewałaby się większość programistów, więc prawdopodobnie nie jest to opłacalne. Poza tym niewiele zyskujesz, gdy wartości są używane do generowania liczb całkowitych, ponieważ często są to losowe wartości zmiennoprzecinkowe).