Asp Forum - [QUIZ] Not So Random (#173

Matthew Moss

8/15/2008 3:34:00 PM

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

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/rub....

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/Mersen...

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

20 Answers

Frederick Cheung

8/15/2008 5:13:00 PM

On 15 Aug 2008, at 16:33, Matthew Moss wrote:

> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>
> 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/rub....
>
> 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.

Great to have the quiz back! This one looks fun.

Fred

> ## 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/Mersen...
>
>
>
> --
> Matthew Moss <matthew.moss@gmail.com>
>

brabuhr

8/15/2008 5:21:00 PM

On Fri, Aug 15, 2008 at 11:33 AM, Matthew Moss <matthew.moss@gmail.com> wrote:
> ## Not So Random (#173)
>
> 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.
>
> 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.

A couple of unit tests:

#!/usr/bin/env ruby

class Random
def initialize(ceiling, seed = nil)
#...
end

def next
#...
end

def reset
#...
end
end

require 'test/unit'

class RandomTest < Test::Unit::TestCase
def test_001
x = Random.new(100, 2112)
assert_equal( [38, 1, 5, 57, 11], Array.new(5) { x.next })
assert_equal( [ 1, 31, 3, 56, 14], Array.new(5) { x.next })
x.reset
assert_equal( [38, 1, 5, 57, 11], Array.new(5) { x.next })
end

def test_002
x = Random.new(100, 2112)
assert_equal( [38, 1, 5, 57, 11], Array.new(5) { x.next })
y = Random.new(100, 1221)
assert_equal( [ 5, 99, 88, 48, 86], Array.new(5) { y.next })
x.reset
assert_equal( [38, 1, 5, 57, 11], Array.new(5) { x.next })
assert_equal( [34, 28, 72, 77, 87], Array.new(5) { y.next })
assert_equal( [ 1, 31, 3, 56, 14], Array.new(5) { x.next })
end
end

Loaded suite foo
Started
.
Finished in 0.251163 seconds.

2 tests, 8 assertions, 0 failures, 0 errors

Matthew Moss

8/15/2008 11:51:00 PM

> 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:
> .....
> You may do this as a class, as depicted here, or as a function,
> lambda, code block... whatever you like.

Let me add a bit of additional info to this... I indicated that you
should implement methods `next` and `reset` on your wrapper. This is
not a hard requirement.

You _do_ need to provide a way to access a particular generator's
(i.e. wrapper's) next number, and provide a way to reset the sequence.
For a class wrapper, this is somewhat natural to do as methods `next`
and `reset`, hence my suggestion.

However, if you find want to use another technique (function, code
block, closure, etc.) is more suitable for your solution, please do...
and if that means providing alternate means (other than next/reset
methods) to access the next random number and reset the sequence,
that's fine. Just state in your submission how you provided for next/
reset equivalents.

Martin Bryce

8/16/2008 12:16:00 AM

I know that a Mersenne Twister has a large internal state, so it takes
time to "get started" and produce good quality random numbers from a
non-random initial state. If it gets frequently reseeded, either the
seeding procedure refreshes all the state and runs it for a bit (i.e.
takes a lot of time) or the quality will greatly degrade, I guess. Is
this a problem?
--
Posted via http://www.ruby-....

Matthew Moss

8/16/2008 1:16:00 AM

On Aug 15, 7:16=A0pm, Martin Bryce <nx-2...@fastwebnet.it> wrote:
> I know that a Mersenne Twister has a large internal state, so it takes
> time to "get started" and produce good quality random numbers from a
> non-random initial state. If it gets frequently reseeded, either the
> seeding procedure refreshes all the state and runs it for a bit (i.e.
> takes a lot of time) or the quality will greatly degrade, I guess. Is
> this a problem?

For the purposes of this quiz, no.

Thomas Wieczorek

8/16/2008 3:01:00 PM

My solution seems to work:

irb(main):022:0> x = Random.new(100, 1234)
=> #<Random: ...>
irb(main):023:0> Array.new(6) { x.next }
=> [47, 83, 38, 53, 76, 24]
irb(main):024:0> y = Random.new(100, 2345)
=> #<Random: ...>
irb(main):025:0> Array.new(6) { y.next }
=> [80, 7, 96, 16, 2, 96]
irb(main):026:0> x.reset
=> 2345
irb(main):027:0> Array.new(2) { x.next }
=> [47, 83]
irb(main):028:0> Array.new(2) { y.next }
=> [0, 98]
irb(main):029:0> Array.new(2) { x.next }
=> [38, 53]

It's not the most beatiful way, but it works.

Frederick Cheung

8/17/2008 3:36:00 PM

ThoML

8/17/2008 3:55:00 PM

My first solution takes a similar approach as FC first one but with
some caching. The sequence is only regenerated when the context has
changed:

class Random
@@context = nil

def initialize(ceiling, seed = nil)
@seed = seed || srand(srand)
@rand = Hash.new do |h,k|
unless @@context == self
srand(@seed)
1.upto(@index - 1) {rand(ceiling)}
@@context = self
end
h[k] = rand(ceiling)
end
reset
end

def next
@rand[@index += 1]
end

def reset
@index = 0
end
end

I haven't had the time to give it too much thought so I'm not sure if
the following actually makes sense. The idea is to seed the random
generator for the next random number with an initial seed + object-
specific sequence number. The sequence is deterministic and mostly
random but differs from the default sequence.

class Random
def initialize(ceiling, seed = nil)
@seed = seed || (srand; rand(ceiling))
@rand = Hash.new do |h,k|
srand(@seed + k)
h[k] = rand(ceiling)
end
reset
end

def next
@rand[@index += 1]
end

def reset
@index = 0
end
end

brabuhr

8/17/2008 4:03:00 PM

On Fri, Aug 15, 2008 at 11:33 AM, Matthew Moss <matthew.moss@gmail.com> wrote:
> ## Not So Random (#173)
>
> 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.
>
> 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.

Since a single Ruby process only has one PRNG, slave off an extra
process for each Random class:

#!/usr/bin/env ruby

require 'rubygems'
require 'slave'

class Random
def initialize(ceiling, seed = nil)
@ceiling = ceiling
@seed = seed || rand(2112)
@slave = Slave::new{
lambda {|reset|
if reset
srand(@seed)
else
rand(@ceiling)
end
}
}
self.reset
end

def next
@slave.object.call(false)
end

def reset
@slave.object.call(true)
end
end

require 'test/unit'

class RandomTest < Test::Unit::TestCase
def test_001
x = Random.new(100, 2112)
assert_equal( [38, 1, 5, 57, 11], Array.new(5) { x.next })
assert_equal( [ 1, 31, 3, 56, 14], Array.new(5) { x.next })
x.reset
assert_equal( [38, 1, 5, 57, 11], Array.new(5) { x.next })
end

def test_002
x = Random.new(100, 2112)
assert_equal( [38, 1, 5, 57, 11], Array.new(5) { x.next })
y = Random.new(100, 1221)
assert_equal( [ 5, 99, 88, 48, 86], Array.new(5) { y.next })
x.reset
assert_equal( [38, 1, 5, 57, 11], Array.new(5) { x.next })
assert_equal( [34, 28, 72, 77, 87], Array.new(5) { y.next })
assert_equal( [ 1, 31, 3, 56, 14], Array.new(5) { x.next })
end
end

Loaded suite foo
Started
.
Finished in 0.251163 seconds.

2 tests, 8 assertions, 0 failures, 0 errors

Matthew Moss

8/17/2008 6:29:00 PM

Very nice, I like...

comp.lang.ruby

[QUIZ] Not So Random (#173

Matthew Moss

Frederick Cheung

brabuhr

Matthew Moss

Martin Bryce

Matthew Moss

Thomas Wieczorek

Frederick Cheung

ThoML

brabuhr

Matthew Moss

x Login to ForumsZone