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

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

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

>>> for n in random.sample(xrange(1, sys.maxsize), 50):
...     print '{0:b}'.format(n)
... 
101101110011011001110011110110101101101101111111101000000000001
110000101001001011101001110111111110011000101011100010000000001
110111101101110011100010001010000101011111110010001110000000001
100001111010011000101001000001000011001111100000001010000000001
1111000010010011111100111110110100100011110111010000000000001
111000001011101011101110100001001001000011011001110110000000001
1000100111011000111000101010000101010100110111000100000000001
11101001000001101111110101111011001000100011011011010000000001
110011010111101101011000110011011001110001111000001010000000001
110110110110111100011111110111011111101000011001100000000001
100010010000011101011100110101011110111100001100100000000000001
10111100011010011010001000101011001110010010000010010000000001
101011100110110001010110000101100000111111011101011000000000001
1111110010110010000111111000010001101011011010101110000000001
11100010101101110110101000101101011011111101101000010000000001
10011110110110010110011010000110010010111001111001010000000001
110110011100111010100111100100000100011101100001100000000000001
100110011001101011110011010101111101100010000111001010000000001
111000101101100111110010110110100110111001000101000000000000001
111111101000010111001011111100111100011101001011010000000001
11110001111100000111010010011111010101101110111001010000000001
100001100101101100010101111100111101111001101010101010000000001
11101010110011000001101110000000001111010001110111000000000001
100111000110111010001110110101001011100101111101010000000001
100001101100000011101101010101111111011010111110111110000000001
100010010011110110111111111000010001101100111001001100000000001
110011111110010011000110101010101001001010000100011010000000001
1111011010100001001101101000011100001011001110010100000000001
110110011101100101001100111010101111001011111101100000000000001
1010001110100101001001011111000111011100001100000110000000001
1000101110010011011000001011010110001000110100100100000000001
11111110011001011100111110110111000001000100100010000000000001
101111101010000101010111111111000001100101111001011110000000001
10010010111111111100000001010010101100111001100000000000001
111110000001110010001110111101110101010110001110000000000000001
100000101101000110101010010000101101000011111010001110000000001
101001011101100011001000011010010000000111110111100010000000001
10110101010000111010110111001111011000001111001100110000000001
10110111100100100011100101001100000000101110100100010000000001
10010111110001011101001110000111011010110100110111110000000001
111011110010110111011011101011001100001000111001010100000000001
101001010001010100010010010001100111101110101111000110000000001
101011111010000101010101000110001101001001011110000000000001
1010001010111101101010111110110110000001111101101110000000001
10111111111010001000110000101101010101011010101100000000001
101011101010110000001111010100100110000011111100100100000000001
111100001101111010100111010001010010000010110110010110000000001
100111111000100110100001110101000010111111010010010000000000001
100111100001011100011000000000101100111111000111100110000000001
110110100000110111011101110101101000101110111111010110000000001
>>>

Как вы можете видеть, все числа заканчиваются на 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 разных бита, я ожидаю увидеть и различные значения в самых правых битах.