Ile jest liczb podwójnych między 0,0 a 1,0?

95

To jest coś, o czym myślę od lat, ale nigdy wcześniej nie spytałem.

Wiele (pseudo) generatorów liczb losowych generuje liczbę losową z zakresu od 0,0 do 1,0. Z matematycznego doublepunktu widzenia w tym zakresie są nieskończone liczby, ale jest to liczba zmiennoprzecinkowa, a zatem ma skończoną precyzję.

Oto pytania:

  1. Ile jest doubleliczb między 0,0 a 1,0?
  2. Czy jest tyle samo liczb od 1 do 2? Między 100 a 101? Między 10 ^ 100 a 10 ^ 100 + 1?

Uwaga: jeśli to robi różnicę, interesuje mnie doublew szczególności definicja języka Java .

smary wielogenowe
źródło

Odpowiedzi:

68

Java doublesą w formacie IEEE-754 , dlatego mają ułamek 52-bitowy; między dowolnymi dwoma sąsiednimi potęgami dwóch (włączając jedną i wyłączając następną), będą zatem od 2 do 52 różnych potęg double(tj. 4503599627370496 z nich). Na przykład jest to liczba odrębnych doubles od 0,5 uwzględnionego do 1,0 wykluczonego, a dokładnie tyle znajduje się również między 1,0 włączonym a 2,0 wykluczonym i tak dalej.

Liczenie doublesmiędzy 0,0 a 1,0 jest trudniejsze niż robienie tego między potęgami dwójki, ponieważ w tym zakresie jest wiele potęg dwójki, a ponadto można dostać się do drażliwych kwestii zdenormalizowanych liczb. 10 z 11 bitów wykładników obejmuje omawiany zakres, więc włączając zdenormalizowane liczby (i myślę, że kilka ich rodzajów NaN), mielibyście 1024 razy doublewięcej niż s między potęgami dwóch - i tak nie więcej niż 2**62w sumie . Nie licząc zdenormalizowanych & c, uważam, że liczba wyniosłaby 1023 razy 2**52.

W przypadku dowolnego zakresu, takiego jak „100 do 100,1”, jest to jeszcze trudniejsze, ponieważ górnej granicy nie można dokładnie przedstawić jako a double(nie będącej dokładną wielokrotnością żadnej potęgi dwóch). Jako przydatne przybliżenie, ponieważ progresja między potęgami dwójki jest liniowa, można powiedzieć, że wspomniany zakres jest 0.1 / 64tym odstępem między potęgami otaczającymi dwójki (64 i 128), więc można by się spodziewać

(0.1 / 64) * 2**52

odrębne doubles - które sprowadzają się do 7036874417766.4004... dawania lub brania jednego lub dwóch ;-).

Alex Martelli
źródło
@Alex: tylko uwaga, kiedy napisałem 100 do 100,1 źle napisałem. Miałem na myśli 100 do 101. Zasadniczo, między N a N + 1 dla dowolnego N.
poligenelubricants
4
@Alex: pozwólcie, że wyjaśnię: nie może być więcej niż 2**64możliwych wartości podwójnych (ponieważ jest to typ 64-bitowy) i najwyraźniej OGROMNA część tych wartości leży pomiędzy 0..1?
polygenelubricants
9
@polygene, tak i tak - w szczególności około jedna czwarta możliwych wartości (dla dowolnej „normalnej” reprezentacji zmiennoprzecinkowej dowolnej podstawy i wykładnika w funkcji długości ułamka) leży między 0,0 a 1,0 (kolejna ćwiartka między 1,0 a nieskończonością, a pozostała połowa na ujemnej połowie rzeczywistej osi). Zasadniczo połowa wartości wykładnika (z normalnym odchyleniem, w połowie jego zakresu) reprezentuje ujemne potęgi podstawy, a zatem liczby <1,0.
Alex Martelli
8
@polygenelubricants: dla wielu zastosowań zakres od 0 do 1 jest dużo, dużo ważniejszy i bardziej interesujący niż zakres od 100 do 101, dlatego ma większy udział w wartościach. Na przykład w fizyce często masz do czynienia z absurdalnie małymi wartościami, takimi jak stała grawiacyjna Newtona przy 6,67e-11. Dobra precyzja jest bardziej przydatna niż między 100 a 101. Przeczytaj floating-point-gui.de, aby uzyskać więcej informacji.
Michael Borgwardt
1
Możesz również skalować dowolną liczbę w zakresie od 0,0 do 1,0, śledząc skalę oddzielnie, co daje mniej błędów w obliczeniach. Fajnie, gdy całą oś liczbową można odwzorować między dwiema liczbami!
codekaizen
44

Każda doublewartość, której reprezentacja znajduje się pomiędzy 0x0000000000000000i 0x3ff0000000000000leży w przedziale [0,0, 1,0]. To (2 ^ 62 - 2 ^ 52) różne wartości (plus lub minus kilka, w zależności od tego, czy liczysz punkty końcowe).

Przedział [1,0, 2,0] odpowiada reprezentacjom między 0x3ff0000000000000a 0x400000000000000; to jest 2 ^ 52 różne wartości.

Przedział [100,0, 101,0] odpowiada reprezentacjom między 0x4059000000000000a 0x4059400000000000; to jest 2 ^ 46 różnych wartości.

Nie ma podwójnych między 10 ^ 100 a 10 ^ 100 + 1 . Żadnej z tych liczb nie można przedstawić z podwójną precyzją i nie ma między nimi podwójnych. Najbliższe dwie liczby podwójnej precyzji to:

99999999999999982163600188718701095...

i

10000000000000000159028911097599180...
Stephen Canon
źródło
+1, za dobrze popartą dokładną odpowiedź. (Jeśli jesteś wybredny w liczeniu punktów końcowych, pamiętaj, że +0,0 i -0,0 mają różne reprezentacje.)
Jim Lewis,
1
+1, takie zakończenie! Czułem się, jakbym czytał scenariusz M. Night Shyamalana!
polygenelubricants
7

Inni już wyjaśnili, że w zakresie [0,0, 1,0] jest około 2 ^ 62 dubli.
(Nie bardzo zaskakujące jest prawie 2 ^ 64 odrębne skończonych podwójna, z tych pół są pozytywne, a w przybliżeniu połowę tych wynoszą <1,0).

Ale wspomniałeś o generatorach liczb losowych: zwróć uwagę, że generator liczb losowych generujący liczby od 0,0 do 1,0 nie może generalnie wytworzyć wszystkich tych liczb; zazwyczaj tworzy tylko liczby w postaci n / 2 ^ 53, gdzie n jest liczbą całkowitą (zobacz np. dokumentację języka Java dla nextDouble ). Zatem zwykle jest tylko około 2 ^ 53 (+/- 1, w zależności od uwzględnionych punktów końcowych) możliwych wartości danych random()wyjściowych. Oznacza to, że większość dubletów w [0.0, 1.0] nigdy nie zostanie wygenerowana.

Mark Dickinson
źródło
3

Artykuł Nowa matematyka Java, Część 2: Liczby zmiennoprzecinkowe od IBM oferuje następujący fragment kodu, aby rozwiązać ten problem (w liczbach zmiennoprzecinkowych , ale podejrzewam, że działa również w przypadku podwójnych):

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

Mają na ten temat następujący komentarz:

Okazuje się, że istnieje dokładnie 8 388 609 wartości zmiennoprzecinkowych między 1,0 a 2,0 włącznie; duża, ale prawie niezliczona nieskończoność liczb rzeczywistych, które istnieją w tym zakresie. Kolejne numery są oddalone od siebie o około 0,0000001. Odległość ta jest nazywana ULP dla jednostki o najmniejszej precyzji lub jednostki na ostatnim miejscu.

Mark Rushakoff
źródło
Tak, ale to jest dla float, nie double - floats ma wartość 23 bitów frakcji, więc 2**23 -> 8388608różne wartości między sąsiednimi uprawnień obydwoma ( «włącznie» część oczywiście znaczy, trzeba liczyć jeden więcej, następnego moc dwóch). doublemają ułamki 52-bitowe!
Alex Martelli
1
@Alex: Myślę, że będę musiał zostawić program (zmodyfikowany do gry podwójnej) działający do końca wszechświata, zanim będę mógł uzyskać wyniki ... :(
Mark Rushakoff,
1
Czuję się głupio; Właśnie napisałem doubleodpowiednik i pomyślałem: „Hej, odpowiem na swoje pytanie za około 5 minut ...”
polygenelubricants
1
@polygene: To wydaje się być problemem Projektu Euler, w którym oczywiste podejście nie jest możliwe do obliczenia, ale musi istnieć jakaś genialnie prosta formuła, aby rozwiązać ten przypadek ...
Mark Rushakoff
2
może nie z prawdziwie doładowanym superkomputerem: na maszynie doublepotrzebującej zaledwie nanosekundy, aby uruchomić wewnętrzną pętlę, liczenie między sąsiednimi potęgami dwóch zajęłoby około 52 dni ( printlnoczywiście byłoby bardzo mało prawdopodobne, aby działał tak szybko bez względu na wszystko, więc załóżmy, że jedno stwierdzenie odchodzi ;-). Myślę, że można spędzić rok lub mniej na potężnej, ale realistycznej maszynie ;-).
Alex Martelli
2
  1. 2 ^ 53 - rozmiar istotności / mantysy 64-bitowej liczby zmiennoprzecinkowej, w tym ukrytego bitu.
  2. Z grubsza tak, ponieważ sifnificand jest stałe, ale wykładnik się zmienia.

Więcej informacji znajdziesz w artykule na Wikipedii .

Yann Ramin
źródło
Twoja odpowiedź na 2 zaprzecza temu, jak rozumiem działanie FP.
polygenelubricants
Myślę, że 1jest źle, bo ukryty jest zawsze jeden bit - Dlatego 2^52, nie 2^53 odrębne wartości (między sąsiednimi uprawnień dwa, jeden wliczone w cenę i następnego wyłączone - nie ! Między 0,0 a 1,0).
Alex Martelli
1

Podwójna Java to liczba binarna64 IEEE 754.

Oznacza to, że musimy wziąć pod uwagę:

  1. Mantysa jest 52-bitowa
  2. Wykładnik to 11-bitowa liczba z odchyleniem 1023 (tj. Z dodanym 1023)
  3. Jeśli wykładnik ma wartość 0, a mantysa jest różna od zera, wówczas mówi się, że liczba jest nienormalizowana

Zasadniczo oznacza to, że istnieje łącznie 2 ^ 62-2 ^ 52 + 1 możliwych podwójnych reprezentacji, które zgodnie ze standardem mieszczą się w przedziale od 0 do 1. Należy zauważyć, że 2 ^ 52 + 1 ma na celu usunięcie przypadków nienormalizowanych liczby.

Pamiętaj, że jeśli mantysa jest dodatnia, ale wykładnik jest liczbą ujemną, liczba jest dodatnia, ale mniejsza niż 1 :-)

W przypadku innych liczb jest to nieco trudniejsze, ponieważ skrajne liczby całkowite mogą nie być reprezentowane w dokładny sposób w reprezentacji IEEE 754, a ponieważ istnieją inne bity używane w wykładniku, aby móc przedstawić liczby, więc im większa liczba, tym niższa różne wartości.

njsf
źródło