Распределение конечных цифр случайных чисел в Python

Есть два очевидных способа генерирования случайной цифры от 0 до 9 в Python. Можно сгенерировать случайное число с плавающей запятой между 0 и 1, умножить на 10 и округлить в меньшую сторону. В качестве альтернативы можно использовать random.randintметод.

import random

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

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

Мне было любопытно, что произойдет, если кто-то сгенерирует случайное число от 0 до 1 и сохранит последнюю цифру. Я не обязательно ожидал, что распределение будет равномерным, но я нашел результат довольно удивительным.

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)

Вывод:

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

Гистограмма показана ниже. Обратите внимание, что 0 не появляется, так как конечные нули усекаются. Но кто-нибудь может объяснить, почему цифры 4, 5 и 6 встречаются чаще, чем остальные? Я использовал Python 3.6.10, но результаты были похожи в Python 3.8.0a4.

Это не «последняя цифра» числа. Это последняя цифра строки, которую strвы получили, когда передали число.

Когда вы вызываете число strс плавающей точкой, Python дает вам достаточно цифр, чтобы при вызове floatстроки получал исходное число с плавающей точкой. Для этой цели, трейлинг 1 или 9 менее вероятно потребуется, чем другие цифры, потому что трейлинг 1 или 9 означает, что число очень близко к значению, которое вы получите, округлив эту цифру. Есть хороший шанс, что другие поплавки не будут ближе, и если это так, то эта цифра может быть отброшена без ущерба для float(str(original_float))поведения.

Если strдать вам достаточно цифр для точного представления аргумента, последняя цифра почти всегда будет 5, за исключением случаев, когда random.random()возвращается 0,0, и в этом случае последняя цифра будет 0. (Плавающие могут представлять только двоичные числа , а последняя ненулевая десятичная цифра нецелочисленное двоичное рациональное всегда равно 5.) Выходные данные также будут очень длинными, выглядящими как

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

что является одной из причин, по которой strэтого не происходит.

Если strвам дано ровно 17 значащих цифр (достаточно, чтобы отличить все значения с плавающей точкой друг от друга, но иногда больше цифр, чем необходимо), то эффект, который вы видите, исчезнет. Было бы почти равномерное распределение конечных цифр (включая 0).

(Кроме того, вы забыли, что strиногда возвращает строку в научной нотации, но это незначительный эффект, потому что существует небольшая вероятность получить значение с плавающей точкой, где это могло бы произойти random.random().)

TL; DR Ваш пример на самом деле не смотрит на последнюю цифру. Последняя цифра конечного двоичного представления мантиссы, преобразованного в основание-10, всегда должна быть 0или 5.

Посмотрите на 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);

    // ...
}

А теперь по адресу 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;
    // ...
}

Википедия подтверждает это:

Точность 53-битного значения и точности дает точность от 15 до 17 значащих десятичных разрядов (2 ^-53 ≈ 1,11 × 10 ^-16 ). Если десятичная строка, содержащая не более 15 значащих цифр, преобразуется в представление двойной точности IEEE 754, а затем преобразуется обратно в десятичную строку с тем же количеством цифр, конечный результат должен соответствовать исходной строке. Если число двойной точности IEEE 754 преобразуется в десятичную строку, содержащую не менее 17 значащих цифр, а затем возвращается обратно в представление двойной точности, конечный результат должен соответствовать исходному числу.

Таким образом, когда мы используем str(или repr), мы представляем только 17 значащих цифр в base-10. Это означает, что некоторые числа с плавающей запятой будут усечены. Фактически, чтобы получить точное представление, вам нужна точность 53 значащих цифр! Вы можете проверить это следующим образом:

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

Теперь, используя максимальную точность, вот правильный способ найти «последнюю цифру»:

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

ПРИМЕЧАНИЕ. Как указывает user2357112, правильные реализации, на которые нужно смотреть, - это PyOS_double_to_stringи format_float_short, но я оставлю текущие реализации, потому что они более интересны с педагогической точки зрения.