Случайное число в диапазоне от 1 до sys.maxsize всегда 1 mod 2 ^ 10

Я пытаюсь найти статистические свойства PRNG, доступные в Python (2.7.10), с использованием теста частоты, теста пробега и теста квадратов.

Для проведения теста частоты мне нужно преобразовать сгенерированное случайное число в его двоичное представление, а затем подсчитать распределение 1 и 0. Я экспериментировал с двоичным представлением случайных чисел на консоли python и наблюдал это странное поведение:

Как вы можете видеть, все числа заканчиваются на 0000000001, т.е. все числа 1 mod 2^10. Почему это так?

Кроме того, это поведение наблюдается, когда диапазон 1 to sys.maxsize. Если диапазон указан как 1 to 2^40, это не наблюдается. Я хочу знать причину такого поведения и есть ли что-то не так в моем коде.

Документация для случайной библиотеки, которая реализует PRNG, которые я использую, здесь.

Сообщите мне, если я должен предоставить дополнительную информацию.

Ответы

Ответ 1

@roeland намекнул на причину: в Python 2, sample() многократно использует int(random.random() * n). Посмотрите исходный код (в Python Lib/random.py) для получения полной информации. Короче говоря, random.random() возвращает не более 53 значительных (отличных от нуля) старших бит; то int() заполняет остальную часть младших бит нулями (вы, очевидно, на машине, где sys.maxsize == 2**63 - 1); то индексирование вашей базы (xrange(1, sys.maxsize)) четным целым числом с "большим числом" младших разрядов 0 всегда возвращает нечетное целое число с тем же числом младших разрядов 0 (за исключением последнего).

В Python 3 ничего из этого не происходит - random в Python 3 использует более сильные алгоритмы и при необходимости возвращается к random.random(). Например, здесь под Python 3.4.3:

>>> hex(random.randrange(10**70))
'0x91fc11ed768be3a454bd66f593c218d8bbfa3b99f6285291e1d9f964a9'
>>> hex(random.randrange(10**70))
'0x7b07ff02b6676801e33094fca2fcca7f6e235481c479c521643b1acaf4'

ИЗМЕНИТЬ

Здесь приведен более подходящий пример, в разделе 3.4.3 в 64-битном поле:

>>> import random, sys
>>> sys.maxsize == 2**63 - 1
True
>>> for i in random.sample(range(1, sys.maxsize), 6):
...    print(bin(i))
0b10001100101001001111110110011111000100110100111001100000010110
0b100111100110110100111101001100001100110001110010000101101000101
0b1100000001110000110100111101101010110001100110101111011100111
0b111110100001111100101001001001101101100100011001001010100001110
0b1100110100000011100010000011010010100100110111001111100110100
0b10011010000110101010101110001000101110111100100001111101110111

В этом случае Python 3 вообще не вызывает random.random(), но вместо этого итеративно захватывает куски из 32 бит из лежащего в основе Mersenne Twister (32-разрядные беззнаковые ints являются "естественными" выходами из этой реализации MT), склеивая их вместе, чтобы создать подходящий индекс. Таким образом, в Python 3 платформы float не имеют к этому никакого отношения; в Python 2, причуды поведения float имеют все, что с ним связано.

Ответ 2

Это зависит от многих вещей, например от того, как именно реализуется RNG, сколько бит состояния он использует и как именно реализована функция sample.

Вот что говорится в документации:

Почти все функции модуля зависят от базовой функции random(), которая равномерно генерирует случайный float в полуоткрытом диапазоне [0.0, 1.0]. Python использует Mersenne Twister в качестве основного генератора. Он производит 53-битные прецизионные поплавки и имеет период 2 ** 19937-1.

Итак, если sample действительно использует random() под капотом, тогда вы должны ожидать только 53 бит значимых бит в вашем результате.

Ответ 3

Это, безусловно, похоже на округление ошибки в random.sample.

Нижние 4 или около того бита всегда равны нулю после умножения на разброс диапазона (maxsize -1), а затем, когда добавляется начало диапазона (1), они всегда 1

если умножение работало корректно, учитывая, что спрэд не является степенью двух, и учитывая, что случайное число имеет только 53 разных бита, я ожидаю увидеть и различные значения в самых правых битах.