From: Matthew Moss <matthew.moss@...>
Date: 2008-08-16T00:33:33+09:00
Subject: [QUIZ] Not So Random (#173)

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Quiz 2:

1.  Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have passed from the time on this message.

2.  Support Ruby Quiz 2 by submitting ideas as often as you can! (A
permanent, new website is in the works for Ruby Quiz 2. Until then,
please visit the temporary website at

     <http://splatbang.com/rubyquiz/>.

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby Talk follow the discussion.  Please reply to
the original quiz message, if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

## Not So Random (#173)

As part of Ruby's standard library, we have access to a good
pseudorandom number generator (PRNG), the [Mersenne twister][1]. (In
particular, the MT19937 variant.) Ruby provides two kernel functions
to make use of this generator: `srand` and `rand`. This week's quiz
involves generating random numbers in a predictable manner.

The first part is to create a wrapper around the random number
generator `rand`, supporting the appropriate parameter (i.e. the
parameter intrinsic to `rand`). Your wrapper should implement two
additional functions: `next` which returns the next random number, and
`reset` which restarts the sequence. So, for example:

    irb> x = Random.new(100)
    => #<Random:...>

    irb> Array.new(5) { x.next }
    => [51, 92, 14, 71, 60]

    irb> Array.new(5) { x.next }
    => [20, 82, 86, 74, 74]

    irb> x.reset
    => nil

    irb> Array.new(5) { x.next }
    => [51, 92, 14, 71, 60]     # after reset, sequence restarts

You may do this as a class, as depicted here, or as a function,
lambda, code block... whatever you like.

The second part is a little trickier: creating multiple, concurrent,
_reproducible_ sequences of pseudorandom numbers isn't so easy. As
convenient as the built-in generator is, there is only one seed. For
example, assume we have two `Random` objects, created as shown above,
`x` and `y`.

    irb> x = Random.new(100)
    => #<Random:...>

    irb> Array.new(6) { x.next }
    => [51, 92, 14, 71, 60, 20]

    irb> y = Random.new(100)
    => #<random:...>

    irb> Array.new(6) { y.next }
    => [66, 92, 98, 17, 83, 57]

    irb> x.reset
    => nil

    irb> Array.new(2) { x.next }
    => [51, 92]       # ok: sequence restarted as requested

    irb> Array.new(2) { y.next }
    => [14, 71]       # fail: this is part of _x_ sequence

    irb> Array.new(2) { x.next }
    => [60, 20]       # more fail: _x_ is now [51, 92, 60, 20]? wrong...


The reason for the failure should be obvious: my current
implementation of `Random` just blindly uses `srand` and `rand`
without considering that there may be multiple instances of `Random`.

So, for this second part, expand your wrapper to support concurrent
use. Please note that you are required to make use of the built-in
generator: you should not implement your own PRNG.

One final note... It is up to you whether the seed for each wrapper
will be user-settable or hidden (as in my examples above). However, if
hidden, each wrapper should have a different seed. (Generated
randomly, perhaps?)



[1]: http://en.wikipedia.org/wiki/Mersenne_twister



-- 
Matthew Moss <matthew.moss@gmail.com>