Rozkład ostatnich cyfr liczb losowych w Pythonie

Istnieją dwa oczywiste sposoby generowania losowej cyfry od 0 do 9 w Pythonie. Można wygenerować losową liczbę zmiennoprzecinkową między 0 a 1, pomnożyć przez 10 i zaokrąglić w dół. Alternatywnie można użyć tej random.randintmetody.

import random

def random_digit_1():
    return int(10 * random.random())

def random_digit_2():
    return random.randint(0, 9)

Byłem ciekawy, co by się stało, gdyby ktoś wygenerował losową liczbę od 0 do 1 i zachował ostatnią cyfrę. Niekoniecznie spodziewałem się, że rozkład będzie jednolity, ale wynik był dość zaskakujący.

from random import random, seed
from collections import Counter

seed(0)
counts = Counter(int(str(random())[-1]) for _ in range(1_000_000))
print(counts)

Wynik:

Counter({1: 84206,
         5: 130245,
         3: 119433,
         6: 129835,
         8: 101488,
         2: 100861,
         9: 84796,
         4: 129088,
         7: 120048})

Histogram pokazano poniżej. Zauważ, że 0 nie pojawia się, ponieważ końcowe zera są obcinane. Ale czy ktoś może wyjaśnić, dlaczego cyfry 4, 5 i 6 są bardziej powszechne niż reszta? Użyłem Python 3.6.10, ale wyniki były podobne w Python 3.8.0a4.

To nie jest „ostatnia cyfra” numeru. To ostatnia cyfra ciągu strpodana po przekazaniu numeru.

Kiedy wywołujesz strliczbę zmiennoprzecinkową, Python podaje wystarczająco dużo cyfr, aby wywołanie floatciągu dało ci oryginalną wartość zmiennoprzecinkową. W tym celu końcowe 1 lub 9 jest mniej prawdopodobne niż inne cyfry, ponieważ końcowe 1 lub 9 oznacza, że ​​liczba jest bardzo zbliżona do wartości, którą uzyskasz zaokrąglając tę ​​cyfrę. Istnieje duża szansa, że ​​żadne inne zmiennoprzecinkowe nie są bliżej, a jeśli tak, to cyfrę można odrzucić bez poświęcania float(str(original_float))zachowania.

Jeśli strdostarczyłbyś wystarczającą liczbę cyfr do dokładnego przedstawienia argumentu, ostatnia cyfra prawie zawsze wynosiłaby 5, z wyjątkiem gdy random.random()zwraca 0,0, w którym to przypadku ostatnia cyfra wynosiłaby 0. (Liczba zmiennoprzecinkowa może reprezentować tylko racjonalne różnice , a ostatnia niezerowa cyfra dziesiętna niecałkowite uzasadnienie dyadyczne to zawsze 5.) Wyjścia również byłyby bardzo długie, wyglądając

>>> import decimal, random
>>> print(decimal.Decimal(random.random()))
0.29711195452007921335990658917580731213092803955078125

który jest jednym z powodów, dla których strtego nie robi.

Jeśli strpodałeś dokładnie 17 cyfr znaczących (wystarczających do odróżnienia wszystkich wartości zmiennoprzecinkowych, ale czasami więcej cyfr niż to konieczne), wówczas efekt, który widzisz, zniknąłby. Byłby prawie równomierny rozkład cyfr końcowych (w tym 0).

(Poza tym zapomniałeś, że strczasami zwraca ciąg znaków w notacji naukowej, ale to niewielki efekt, ponieważ istnieje małe prawdopodobieństwo uzyskania liczby zmiennoprzecinkowej tam, gdzie to by się wydarzyło random.random().)

TL; DR Twój przykład tak naprawdę nie patrzy na ostatnią cyfrę. Ostatnia cyfra skończonej reprezentowanej binarnie mantysy przekonwertowanej na base-10 powinna zawsze być 0lub 5.

Spójrz na cpython/floatobject.c:

static PyObject *
float_repr(PyFloatObject *v)
{
    PyObject *result;
    char *buf;

    buf = PyOS_double_to_string(PyFloat_AS_DOUBLE(v),
                                'r', 0,
                                Py_DTSF_ADD_DOT_0,
                                NULL);

    // ...
}

A teraz o cpython/pystrtod.c:

char * PyOS_double_to_string(double val,
                                         char format_code,
                                         int precision,
                                         int flags,
                                         int *type)
{
    char format[32];
    Py_ssize_t bufsize;
    char *buf;
    int t, exp;
    int upper = 0;

    /* Validate format_code, and map upper and lower case */
    switch (format_code) {
    // ...
    case 'r':          /* repr format */
        /* Supplied precision is unused, must be 0. */
        if (precision != 0) {
            PyErr_BadInternalCall();
            return NULL;
        }
        /* The repr() precision (17 significant decimal digits) is the
           minimal number that is guaranteed to have enough precision
           so that if the number is read back in the exact same binary
           value is recreated.  This is true for IEEE floating point
           by design, and also happens to work for all other modern
           hardware. */
        precision = 17;
        format_code = 'g';
        break;
    // ...
}

Wikipedia potwierdza to:

53-bitowa precyzja znaczenia i precyzja daje od 15 do 17 znaczących dokładności cyfr dziesiętnych (2 ^-53 ≈ 1,11 × 10 ^-16 ). Jeśli ciąg dziesiętny zawierający co najwyżej 15 cyfr znaczących jest konwertowany na reprezentację podwójnej precyzji IEEE 754, a następnie konwertowany z powrotem na ciąg dziesiętny z taką samą liczbą cyfr, wynik końcowy powinien być zgodny z ciągiem oryginalnym. Jeśli liczba podwójnej precyzji IEEE 754 jest konwertowana na ciąg dziesiętny z co najmniej 17 cyframi znaczącymi, a następnie z powrotem na reprezentację podwójnej precyzji, wynik końcowy musi być zgodny z liczbą oryginalną.

Tak więc, kiedy używamy str(lub repr), reprezentujemy tylko 17 cyfr znaczących w bazie-10. Oznacza to, że część liczb zmiennoprzecinkowych zostanie obcięta. W rzeczywistości, aby uzyskać dokładną reprezentację, potrzebujesz dokładności 53 cyfr znaczących! Możesz to sprawdzić w następujący sposób:

>>> counts = Counter(
...     len(f"{random():.99f}".lstrip("0.").rstrip("0"))
...     for _ in range(1000000)
... )
>>> counts
Counter({53: 449833,
         52: 270000,
         51: 139796,
         50: 70341,
         49: 35030,
         48: 17507,
         47: 8610,
         46: 4405,
         45: 2231,
         44: 1120,
         43: 583,
         42: 272,
         41: 155,
         40: 60,
         39: 25,
         38: 13,
         37: 6,
         36: 5,
         35: 4,
         34: 3,
         32: 1})
>>> max(counts)
53

Teraz, używając maksymalnej precyzji, oto właściwy sposób na znalezienie „ostatniej cyfry”:

>>> counts = Counter(
...     int(f"{random():.53f}".lstrip("0.").rstrip("0")[-1])
...     for _ in range(1000000)
... )
>>> counts
Counter({5: 1000000})

UWAGA: Jak wskazał użytkownik2357112, poprawnymi implementacjami do obejrzenia są PyOS_double_to_stringi format_float_short, ale zostawię obecne, ponieważ są one bardziej interesujące pedagogicznie.