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

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 .

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

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...

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.

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.

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 .

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.