Distributed sequential random number generation in Ruby 1.9.2

Question

The Random class in Ruby 1.9.2 is guaranteed to generate random numbers in the same order, given a particular seed and range. For instance:

r = Random.new(23)
r.rand(100)         # 83
r.rand(100)         # 40

But suppose I want to generate the next number in the sequence on another computer (without re-generating the earlier numbers in the sequence). This should be possible, given the previous output. Is there a way to do this with the Random class? Or do I have to write my own implementation of the Mersenne twister?

[Edit: As pointed out in the comments below, it is not in fact possible to determine the state of a Random instance just from the output, because only part of the state (specifically, the low 32 bits) are used for the output.]

@adamse The next number is generated deterministically given some internal state in `r`. So if you create a new `r` with the same state as the old one, it will generate the next number in the sequence. Makes sense? Based on my understanding of the algorithms underlying `Random`, I believe this state can be represented by the seed and the last generated number. — Trevor Burnham, Aug 27 '10 at 19:33
reading the [backported](http://github.com/marcandre/backports/blob/master/lib/backports/1.9.2/random/MT19937.rb) implementation it seems that indeed you can find the next state using the last and the seed. However as far as I understand you might not be able to find the state given the generated number. — ase, Aug 27 '10 at 20:06
I'm not sure if the state of `r` can be deduced from merely the last generated value as presented in your example. Consider two cases: (1) When the same number appears twice within the same random cycle (Not sure if this can happen with Mersenne), and (2) the data from the last output is loss by constraining the output to an integer from 1-100. Consider what would happen if you were using `rand(10)` instead of `rand(100)`. Surely `rand(100)`, while better, is not perfect as well, by pigeonhole principle. — Justin L., Jan 10 '11 at 20:31

score 2 · Accepted Answer · edited May 23 '17 at 10:32

2

Can't test, but the generator can be marshalled, according to Marc-André Lafortune here. So this might work:

r = Random.new(23)
r.rand(100)         # 83
r.rand(100)         # 40

File.open("/path/to/file","w") do |f|
  Marshal.dump(r,f)
end

# later, may be on another computer

File.open("/path/to/file","r") do |f|
  @v = Marshal.load(f)
end

puts @v.rand(100)

edited May 23 '17 at 10:32

Community

1
1

answered Aug 27 '10 at 19:23

steenslag

79,051
16
138
171

That might work, but that seems awfully inefficient. In principle, you should only need to transmit the most recently generated value from one computer to the other; you shouldn't have to serialize the whole object. – Trevor Burnham Aug 27 '10 at 19:30
1

You're making the assumption that there's no other internal state. You could certainly write a random number generator for which that's true (easiest way: keep re-instantiating Random with the prior number as the seed value, and only use the first call) but it's not really fair to say that the current Random class "should in principle" maintain statelessness for the sake of an uncommon use case. – SFEley Jan 03 '11 at 00:35

Distributed sequential random number generation in Ruby 1.9.2

1 Answers1