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

Edit: więc w zasadzie to co próbuję napisać to 1 bitowy hash dla double.

Chcę odwzorować double na true lub false z szansą 50/50. W tym celu napisałem kod, który wybiera losowe liczby (jako przykład, Chcę użyć tego na danych z regularnością i nadal uzyskać wynik 50/50), sprawdza ich ostatni bit i przyrosty y jeśli jest to 1, lub n jeśli jest to 0.

Jednak ten kod stale daje 25% y I 75% n. Dlaczego nie 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 wyjście: 

250167 749833
Author: numaroth, 2014-12-23
Source

3 answers

Ponieważ nextDouble działa tak: (source ) 

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

next(x) tworzy x losowe bity.

Dlaczego to ma znaczenie? Ponieważ mniej więcej połowa liczb generowanych przez pierwszą część (przed podziałem) jest mniejsza niż 1L << 52, a zatem ich significand nie wypełnia całkowicie 53 bitów, które może wypełnić, co oznacza, że najmniej znaczący bit significand jest zawsze zerowy dla tych.

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

Zasadniczo double wygląda tak: ( źródło )

układ podwójny

Bardzo ważnym szczegółem nie widocznym na tym zdjęciu jest to, że liczby są "znormalizowane"1 taki, że ułamek 53 bitowy zaczyna się od 1 (wybierając wykładnik taki, że tak jest), że 1 jest następnie pominięty. Dlatego zdjęcie pokazuje 52 bity dla ułamek (significand), ale faktycznie są w nim 53 bity.

Normalizacja oznacza, że jeśli w kodzie dla nextDouble ustawiony jest 53 bit, to ten bit jest implicit interlinit 1 i odchodzi, a pozostałe 52 bity są kopiowane dosłownie do significand wynikowego double. Jeśli jednak ten bit nie jest ustawiony, pozostałe bity muszą zostać przesunięte w lewo, dopóki nie zostanie ustawiony.

Średnio połowa wygenerowanych liczb przypada na przypadek, w którym significand był , a nie przesunięte w lewo w ogóle (i mniej więcej połowa tych mA 0 jako najmniej znaczący bit), a druga połowa jest przesunięta o co najmniej 1 (lub jest po prostu całkowicie zero), więc ich najmniej znaczący bit jest zawsze 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.

 164
Author: harold,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-12-25 01:55:30

Z docs :

Metoda nextDouble jest zaimplementowana 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 Javy wynik został błędnie obliczony jako: 

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

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

Ta notatka była tam przynajmniej od Javy 5 (docs for Java

 48
Author: Thomas,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-12-23 18:18:03

Ten wynik mnie nie dziwi, biorąc pod uwagę sposób reprezentacji liczb zmiennoprzecinkowych. Załóżmy, że mieliśmy bardzo krótki Typ zmiennoprzecinkowy z zaledwie 4 bitami precyzji. Gdybyśmy mieli wygenerować liczbę losową z zakresu od 0 do 1, rozproszoną 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ądały w maszynie, możesz przetestować bit niskiego rzędu, aby uzyskać dystrybucję 50/50. Jednak pływaki IEEE są reprezentowane jako moc 2 razy mantissa; jedno pole w pływak jest mocą 2 (plus stałe przesunięcie). Moc 2 jest tak dobrana, że część "mantissa" jest zawsze liczbą > = 1.0 i 0.0000 będą reprezentowane 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

(1 przed punktem binarnym jest wartością domyślną; dla pływaków 32 - i 64-bitowych, żaden bit nie jest faktycznie przypisany do tego 1.)

Ale patrząc na powyższe powinno zademonstrować dlaczego, jeśli przekonwertujesz reprezentację na bity i spojrzysz na niski bit, otrzymasz zero 75% czasu. Jest to spowodowane tym, że wszystkie wartości są mniejsze niż 0,5 (binary 0.1000), co stanowi połowę możliwych wartości, ponieważ ich mantissy są przesunięte, co powoduje, że 0 pojawia się w niskim bitie. Sytuacja jest zasadniczo taka sama, gdy mantissa ma 52 bity (nie wliczając implikowanego 1), Jak robi to double.

(właściwie, jak zasugerował @sneftel w komentarzu, możemy dołączyć więcej niż 16 możliwych wartości w dystrybucji, przez generowanie: 

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 dystrybucja, której spodziewałby się większość programistów, więc prawdopodobnie nie jest to warte zachodu. Dodatkowo nie zyskasz wiele, gdy wartości są używane do generowania liczb całkowitych, jak często są to losowe wartości zmiennoprzecinkowe.)

 33
Author: ajb,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-12-23 18:36:10