[issue9816] random.jumpahead and PRNG sequence independence
Craig McQueen added the comment: I notice that the C++11 library has a discard() member function for its random generators, which is effectively a jumpahead operation. It seems that the C++11 library has implemented discard() for the Mersene Twister generator. If jumpahead() is technically possible for MT, can it be added back into the Python library? -- nosy: +cmcqueen1975 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue9816 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue9816] random.jumpahead and PRNG sequence independence
Craig McQueen added the comment: C++11 Mersenne Twister discard() member function: http://www.cplusplus.com/reference/random/mersenne_twister_engine/discard/ -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue9816 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue9816] random.jumpahead and PRNG sequence independence
Craig McQueen added the comment: StackOverflow question about Mersenne Twister jumpahead: http://stackoverflow.com/q/4184478/60075 which refers to this: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/JUMP/index.html -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue9816 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue9816] random.jumpahead and PRNG sequence independence
New submission from Joseph Schaeffer thir...@gmail.com: Reading the Python 2.6 docs, it appeared that using random.jumpahead would allow the initialization of several generators with the same seed but having much different internal states. While the resulting PRNG appear to have different internal states, the produced random numbers [via .random()] are exactly the same after a small initial segment. Attached is some example code which shows the first point at which they all agree - in my testing (Mac OS X, Python versions 2.5, 2.6, 2.7) the generated numbers all agreed on the 12th number generated. For smaller differences in jumpahead it was noticeable a lot earlier - n=1,2 differ only in the first sample from each. The internal state of the PRNGs is indeed different even after the successive sampling, so it may be that this is intended - however if so the docs may cause confusion: my particular case was where I need random numbers for a stochastic markov process and in addition needed many such generators [one for each trajectory] and was hoping to use random.jumpahead to have indepedent PRNG's without having to generate [and prove] my own independent set of seeds. Thus having a long sequence of non-independent random numbers near the initial start condition causes random.jumpahead to be unusable for my situation. It appears that Python 3.1 removed random.jumpahead - if so, it may be useful to note in the 2.6 docs why this was / the issues with random.jumpahead: reading how it changed after 2.3 made it sound like it was exactly what I wanted. Possible cause: I suspect the issue may be related to how a Mersenne Twister algorithm can take a while to recover from poor seeding (excessive 0's), but do not know enough to explore that idea. -- components: Library (Lib) files: random_test.py messages: 115985 nosy: Joseph.Schaeffer priority: normal severity: normal status: open title: random.jumpahead and PRNG sequence independence type: behavior versions: Python 2.5, Python 2.6, Python 2.7 Added file: http://bugs.python.org/file18816/random_test.py ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue9816 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue9816] random.jumpahead and PRNG sequence independence
Changes by Ned Deily n...@acm.org: -- nosy: +rhettinger versions: -Python 2.5, Python 2.6 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue9816 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue9816] random.jumpahead and PRNG sequence independence
Changes by Raymond Hettinger rhettin...@users.sourceforge.net: -- assignee: - rhettinger priority: normal - low ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue9816 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue9816] random.jumpahead and PRNG sequence independence
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: Thanks for the report. Something does appear to be broken. When the states are different, the random numbers should be different. Am looking in to it. In the mean time, I recommend against using jumpahead() with MT. It is better to separately seed three different generators and rely on the huge period of MT to keep the sequences from overlapping. If you do use jumpahead(), it is intended to be supplied with large values of n (not 1, 11, or 21). The function/method was removed in 3.x because it was an API defect. The jumpahead concept as originally intended (move ahead n-steps) was something that could really only work with a generator like Wichmann-Hill. Newer and more advanced generators aren't usually amenable to direct computation of a state that is n-steps forward. -- priority: low - high ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue9816 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue9816] random.jumpahead and PRNG sequence independence
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: I see the problem now. Random.jumpahead(n) does a very poor job of shuffling MT's state when n is small. The first few numbers of the state are different but some of the later ones are not. When random() crawls across parts of the state that are identical, it produces identical output. Later when has wrapped around, the random() calls diverge again. Fixed by salting the jumpahead value. See r84665. -- resolution: - fixed status: open - closed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue9816 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue9816] random.jumpahead and PRNG sequence independence
Joseph Schaeffer thir...@gmail.com added the comment: Thanks for looking into it! I'm glad that issue will be fixed, as at least one website was actually recommending using .jumpahead(i) for i in 1..100 for independent seed. I suspect in my use case I'll want to continue my previous methods; I work with stochastic Markov processes and I need to seed a large number (10k+) of generators - one per trajectory - and also have the requirement of needing a deterministic PRNG. So having a single Mersenne Twister seed plus salting values that worked with .jumpahead would be a simpler representation; my previous code in C did basically that with a LCG to create those seeding values for the Mersenne Twister. So that's roughly equivalent [I think?] to the fixed random.jumpahead. Thanks again! -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue9816 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com