Edycja: Więc w zasadzie to, co próbuję napisać, to 1-bitowy hash double
.
Chcę zmapować double
do true
lub false
z 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, y
jeśli wynosi 1, lub n
jeśli jest 0.
Jednak ten kod stale daje 25% y
i 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
java
random
double
bit-manipulation
probability
gvlasov
źródło
źródło
doubleValue % 1 > 0.5
, ale byłoby to zbyt gruboziarniste, ponieważ w niektórych przypadkach może wprowadzić widoczne regularności (wszystkie wartości mieszczą się w zakresie długości 1). Jeśli jest zbyt gruboziarnisty, czy powinniśmy prawdopodobnie spróbować mniejszych zakresów, na przykładdoubleValue % 1e-10 > 0.5e-10
? No tak. Przyjmowanie ostatniego kawałka jako skrótudouble
jest tym, co dzieje się, gdy postępujesz zgodnie z tym podejściem do końca, z najmniejszym możliwym modulo.(lastbit & 3) == 0
zadziała, choć to dziwne.Odpowiedzi:
Ponieważ nextDouble działa tak: ( źródło )
next(x)
tworzyx
losowe 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
double
naprawdę wygląda a w Javie (i wielu innych językach) i dlaczego ma to znaczenie w tym pytaniu.Zasadniczo
double
wygląda to tak: ( źródło )Bardzo ważnym szczegółem niewidocznym na tym rysunku jest to, że liczby są „znormalizowane” 1 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
nextDouble
53. bitu jest ustawiony, ten bit jest niejawną wiodącą 1 i odchodzi, a pozostałe 52 bity są kopiowane dosłownie do znacznika wynikudouble
. 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 .
źródło
random.nextDouble()
jest zazwyczaj „najlepszym” sposobem na to, do czego jest przeznaczony, ale większość ludzi nie próbuje tworzyć 1-bitowego skrótu z losowego podwójnego skrótu. Szukasz jednolitego rozkładu, odporności na kryptoanalizę, czy co?next
musi zwrócić anint
, więc i tak może mieć tylko 32 bityZ dokumentów :
Ale stwierdza również, co następuje (podkreślenie moje):
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?
źródło
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:
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.0000
byłyby przedstawione w następujący sposób:(
1
Przed punktem binarnym jest domniemana wartość; dla 32- i 64-bitowych liczb zmiennoprzecinkowych żaden bit nie jest faktycznie przydzielany do przechowywania tego1
).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 adouble
.(Właściwie, jak zasugerował @sneftel w komentarzu, moglibyśmy uwzględnić więcej niż 16 możliwych wartości w dystrybucji, generując:
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).
źródło