From: "F. Senault" <fred@...>
Date: 2009-01-24T05:03:11+09:00
Subject: Re: Separate random number generators?

Le 23 janvier 2009 � 16:55, Bart Braem a �crit :

> On Jan 23, 4:33�pm, "F. Senault" <f...@lacave.net> wrote:

>> Can you estimate the number of random numbers you'll need ? �Maybe you
>> could pre-generate sequences of numbers in a few arrays, then patch the
>> rand method to actually read the array instead of generating the
>> number ?
>>
>> The start time and memory consumption will be a lot higher, but maybe it
>> makes a good compromise ?
> 
> That is an idea, but quick calculations show the need of up to 100.000
> random numbers. Which is quite a lot to calculate and most importantly
> store and retrieve again.

On a box of mine (a 2.6GHz dual core AMD 64 CPU), it takes 10 seconds to
make 10 arrays of 1.000.000 random numbers, and memory consumption was
about 500M.  As for the access times :

ruby 1.9.1p0 (2009-01-20 revision 21700) [amd64-freebsd7]
Seeding in 8.921912
                          user     system      total        real
Pseudo seqs          93.429688   0.218750  93.648438 ( 93.614218)
Real rand           108.500000   0.000000 108.500000 (108.456800)

The first is accessing the 10 arrays of numbers to pick 1.000.000
numbers between 1 and 26, the second uses the old rand method with no
reseeding whatsoever.
 
On the other hand, I don't know the exact kind of use you have, but...
you could also generate sequences of a few thousands in arrays and
simply cycle through them (i.e. reuse the numbers a few times).  If
you're concerned about random distribution, this wouldn't be a problem ?

(Uglyish) code :

#! /usr/local/bin/ruby

require "benchmark"

t = Time.new

NUM_SEQ = 10
SEEDS = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
NUM_NUMS = 1_000_000

$numbers = []

NUM_SEQ.times do |i|
  srand(SEEDS[i])
  a = Array.new(NUM_NUMS) { rand }
  $numbers << a
end

$curr_seq = 0
$curr_index = 0
$curr_nums = $numbers[0]
$indexes = Array.new(NUM_SEQ, 0)

puts "Seeding in #{"%2.6f" % (Time.new - t)}"

module Kernel
  alias old_rand rand
  def swap_seq(seq)
    $indexes[$curr_seq] = $curr_index
    $curr_seq = seq
    $curr_index = $indexes[seq]
    $curr_nums = $numbers[seq]
  end
  def reset_seq(seq)
    $indexes[seq] = 0
    $curr_index = 0 if seq == $curr_seq
  end
  def rand(x = nil)
    r = $curr_nums[$curr_index]
    $curr_index += 1
    r = (r * x).to_i if x
    r
  end
end

acc = 1_000_000
n = 100

Benchmark.bm 20 do |x|
  x.report "Pseudo seqs" do
    n.times do
      ns = 0
      s = ""
      nq = 0
      acc.times do |z|
        s = (rand(26) + 65).chr
        nq += 1
        if nq == 1000
          ns = (ns + 1) % NUM_SEQ
          swap_seq(ns)
          nq = 0
        end
      end
      NUM_SEQ.times { |q| reset_seq(q) }
    end
  end
  x.report "Real rand" do
    n.times do
      s = ""
      acc.times do |z|
        s = (old_rand(26) + 65).chr
      end
      GC.start
    end
  end
end

Fred
-- 
Christian Fundamentalism: The doctrine that there is an absolutely
powerful, infinitely knowledgeable, universe spanning entity that is
deeply and personally concerned about my sex life.         (Andrew Lias)