Alex Martelli wrote: > ...claims: > > Note that for even rather small len(x), the total number of > permutations of x is larger than the period of most random number > generators; this implies that "most" permutations of a long > sequence can never be generated. > > Now -- why would the behavior of "most" random number generators be > relevant here? The module's docs claim, for its specific Mersenne > Twister generator, a period of 2**19997-1, which is (e.g.) a > comfortable > 130128673800676351960752618754658780303412233749552410245124492452914636 > 028095467780746435724876612802011164778042889281426609505759158196749438 > 742986040468247017174321241233929215223326801091468184945617565998894057 > 859403269022650639413550466514556014961826309062543 times larger than > the number of permutations of 2000 items, which doesn't really feel > to me like a "rather small len(x)" in this context (what I'm most > often shuffling is just a pack of cards -- len(x)==52 -- for example).
I wouldn't be too comfortable with that margin. The fun thing about factorials is that they add up really quickly. The crossover point is between 2080 and 2081. In [28]: from scipy import * In [29]: def f(x): ....: return special.gammaln(x-1) - 19937*log(2) ....: In [30]: optimize.brentq(f, 2000, 3000) Out[30]: 2082.4031300820125 In [31]: import gmpy In [32]: mtperiod = 2**19937 - 1 In [33]: for i in range(2075, 2085): ....: if gmpy.fac(i) > mtperiod: ....: print i ....: break ....: ....: 2081 I think that documenting this boundary might be worthwhile rather than making vague references to "small len(x)." A note along the lines of Josiah wrote about there being no guarantees despite period size would also be useful. OTOH, isn't the exact PRNG algorithm considered an implementation detail? It certainly was when the module migrated from Wichmann-Hill to the Mersenne Twister. OTGH, I don't foresee the random module ever using an algorithm with worse characteristics than the Mersenne Twister. -- Robert Kern "I have come to believe that the whole world is an enigma, a harmless enigma that is made terrible by our own mad attempt to interpret it as though it had an underlying truth." -- Umberto Eco _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
