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/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)
>

A crude solution: we remember the seed and how many times we've been  
called. When called for the n+1 time, we reset the seed, call rand n  
times and then return the result of the n+1th call.
As far as the selection of the original seed goes, srand can already  
cook one up for us so we lean on that.

class Random
   def initialize(*rand_args)
     @rand_args = rand_args
     ignored, @start_seed = srand, srand
     @sequence = 0
   end

   def next
     srand(@start_seed)
     @sequence.times { rand *@rand_args}
     @sequence += 1
     rand *@rand_args
   end

   def reset
     @sequence = 0
   end
end

Performance wise this isn't great - generating n random numbers  
require n(n+1)/2 calls to rand. Things can be improved by generating  
(say) 100 numbers in one go, since what is expensive is recovering our  
previous state.

This sample achieves that

class Random
   def initialize(*rand_args)
     @rand_args = rand_args
     ignored, @start_seed = srand, srand
     @sequence = 0
     @cache = []
   end

   def next
     populate if @cache.empty?
     @cache.shift
   end

   def populate
     srand(@start_seed)
     @sequence.times { rand *@rand_args}
     100.times do
       @cache << rand(*@rand_args)
     end
   @sequence += 100
   end

   def reset
     @cache = []
     @sequence = 0
   end
end

It's a lot faster (0.25s versus 22.3 s to generate 10000 numbers) but  
the complexity isn't any better.

Fred