Un nombre aléatoire dans la plage de 1 à sys.maxsize est toujours 1 mod 2^10

Question

J'essaie de trouver les propriétés statistiques des PRNGs disponibles dans Python (2.7.10) en utilisant le test de fréquence, le test des séries et le test du chi carré.

Pour effectuer le test de fréquence, je dois convertir le nombre aléatoire généré en sa représentation binaire, puis compter la distribution de 1 et 0 's. J'expérimentais avec la représentation binaire des nombres aléatoires sur la console python et j'ai observé ce comportement bizarre :

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

Comme vous pouvez le voir, tous les chiffres se terminent par 0000000001 c'est-à-dire que tous les nombres sont 1 mod 2^10 . Pourquoi en est-il ainsi ?

De même, ce comportement est observé lorsque la gamme est 1 to sys.maxsize . Si la plage est spécifiée comme étant 1 to 2^40 mais cela n'est pas observé. Je veux savoir la raison de ce comportement et s'il y a quelque chose de mal dans mon code.

La documentation de la bibliothèque aléatoire qui implémente les PRNGs que j'utilise est la suivante aquí .

Faites-moi savoir si je dois fournir d'autres informations.

Answer 1

@roeland a fait allusion à la cause : dans Python 2, sample() utilise int(random.random() * n) de manière répétée. Regardez le code source (dans le répertoire de votre Python Lib/random.py ) pour plus de détails. En bref, random.random() ne renvoie pas plus de 53 bits de tête significatifs (non nuls) ; puis int() remplit le reste des bits de poids faible avec des zéros (vous êtes manifestement sur une machine sur laquelle sys.maxsize == 2**63 - 1 ) ; puis l'indexation de votre base ( xrange(1, sys.maxsize) ) par un nombre entier pair avec "beaucoup" de bits de poids faible renvoie toujours un nombre entier impair avec le même nombre de bits de poids faible (sauf le dernier).

Dans Python 3, rien de tout cela n'arrive - random en Python 3 utilise des algorithmes plus puissants, et ne se rabat qu'en faveur de random.random() si nécessaire. Par exemple, ici sous Python 3.4.3 :

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

EDIT

Voici un exemple plus directement pertinent, sous 3.4.3 sur une machine 64 bits :

>>> 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 n'invoque pas random.random() dans ce cas, mais plutôt de saisir itérativement des morceaux de 32 bits du Mersenne Twister sous-jacent (les ints non signés de 32 bits sont les sorties "naturelles" de cette implémentation de MT), en les collant ensemble pour construire un index approprié. Ainsi, dans Python 3, les flottants de la plate-forme n'ont rien à voir avec cela ; dans Python 2, les bizarreries du comportement des flottants ont tout à voir avec cela.

Answer 2

Cela dépend de beaucoup de choses, comme la manière exacte dont le RNG est implémenté, le nombre de bits d'état qu'il utilise, et la manière exacte dont le système de gestion de l'information est utilisé. sample est mise en œuvre.

Voici ce que dit la documentation :

Presque toutes les fonctions des modules dépendent de la fonction de base random(), qui génère un flottant aléatoire uniformément dans l'intervalle semi-ouvert [0,0, 1,0]. Python utilise le tordeur de Mersenne comme générateur de base. Il produit des flottants de 53 bits de précision et a une période de 2**19937-1.

Ainsi, si le sample utilise en effet random() sous le capot, alors vous ne devez vous attendre qu'à 53 bits de bits significatifs dans votre résultat.

Answer 3

Cela ressemble certainement à une erreur d'arrondi dans random.sample.

Les quelque 4 bits du bas sont toujours à zéro après la multiplication par l'écart de la gamme ( maxsize -1 ), alors lorsque le début de la plage ( 1 ) est ajouté, ils sont toujours à 1

si la multiplication fonctionnait correctement, étant donné que l'écart n'est pas une puissance de deux, et étant donné que le nombre aléatoire ne comporte que 53 bits variables, je m'attendrais à voir des valeurs variables dans les bits les plus à droite également.