Jump function for the MT19937
Closed this issue · 9 comments
Hello,
I have not been able to find a Python implementation for the jump ahead function for the MT19937 (http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/JUMP/index.html) and I think it would be a really nice addition. Do you think adding it to randomstate would be a possibility in any near future?
It is present for dSFMT. I am hesitant to alter the MT19937 generator since it has been kept to closely match NumPy. It is also an old, slow PRNG :-).
Yes, why I am missing a jump ahead for the MT19937 is only because it's so popular and still much used (e.g. numpy). It is really hard to get independent streams for it. I'm not an expert on the implementation of PRNGs but wouldn't the jump function only translate the internal state forward, so in essence wouldn't interfere with the working of the generator itself?
It isn't really possible to get independent streams from MT19937 -- jump just moves you to a distant point in the cycle. Thanks for the suggestion -- I will think about it could be done without breaking MT19937 (should be possible).
Thanks for the quick reply and if you decide to add it, that would be just great. By independent streams I mean exactly that, we can be assured that they don't overlap (until of course you reach the jump length in the previous stream). Perhaps indenpendent was a bad choice of word here :)
Even with a large jump -- 2^512 -- it is essentially impossible to cycle the generator. This said, most PRNGs have some low frequency dependence and so you don't want to use too much of the cycle (I would say < 5% -- this is the reason to like large cycle PRNGs for large scale simulation work even if one could never exhaust the space).
Yes, so my use case would be in a large parallel setting where I need to be able to repeat the simulation but also overlapping streams will cause trouble. So if I need e.g. 1000 unique streams, given an initial state, the jump function would seem as a robust option and guarantee they won't overlap. Also I can easily reproduce the result. I'm not sure how close states initialized with different seeds may end up to each other.
@lintusj1 I have mostly finished this (not tested) in the branch mentioned in this thread. In implementing this I noticed that maximum jump ahead is 2^31 which seems quite small. Do you think this would be useful for you with such a small jump?
@bashtage Thank you for letting me know. Indeed, the 2^31 maximum jump limit is surprisingly small and unfortunately probably a bit too risky in my use case.
Looks like it can be made to be much bigger -- e.g., 2**128 -- so this is back on he roadmap.