[clean-list] distribution of 1 random number sequence throughout program

[Pieter Koopman]

Dear Chide,

Clean has a library for generating pseudo random numbers: 
MersenneTwister. As explained in the dcl file this produces pretty good 
random numbers based on an algorithm described in "Mersenne Twister: A 
623-dimensionally equidistributed uniform pseudorandom number  
generator" by M. Matsumoto and T. Nishimura in ACM Transactions on 
Modeling and Computer Simulation, vol. 8, no. 1, January 1998, pp. 3-30.

A simple way to distribute random numbers is the 'plumbing' approach of 
Burton and Page. If there is some state (like world or for IO) passed 
around you insert the list of numbers in the state and take as many 
values as you need. From your description I have the impression that 
this does not solve your problem.  It is possible to introduce such a 
state, but that can have a huge (and unwanted) impact on the structure 
of your program. It depends on your program if the plumbing approach 
will work well.

Spliting random stream in oven and odd values has a severe space leak 
penalty as Burton and Page point out. I used a scheme were random 
streams are split by starting a new stream with the current random 
number as seed:

split :: [Int] -> ([Int],[Int])
split [a:x] = (genRandInt a, x)

This is somewhat similar to the random splitting of sequences as 
proposed by Burton and Page. For the Mersenne Twister the next random 
number is generally not related to a new sequence using the current 
number as seed.
For a program that uses a huge number of splits this can have a space 
penalty: each generator uses an array and all those arrays together can 
consume a significant amount of memory (depending on the number of 
splits and if they can be removed by the garbage collector or not).

If you do not want to have a state in your program for plumbing random 
numbers and need a huge number of splits, you can consider to use a 
simpler algorithm to generate pseudo random numbers. More specific: an 
algorithm that does not use much memory. For instance the algorithm used 
in Haskell as outlined in the Burton and Page paper.

So, unfortunately the final answer is 'it depends'. I am not aware of a 
library solving the problem for you.

Hope this helps,

Pieter

On 09/11/2011 11:22 PM, Groenouwe, C. wrote:
> Dear Pieter (and others Clean specialists),
>
> I tried to use random numbers in my clean program, however, I ran into 
> the problem of distributing the pseudo random sequence to the 
> different parts of my program. What is an elegant solution which 
> doesn't restrict your program so much that it breaks possibilities for 
> parallel computing etc. etc.? Doing some research I found this article:
>
> http://www.cs.ou.edu/~rlpage/*Burton*PageRngJFP.pdf 
> <http://mailman.science.ru.nl/pipermail/clean-list/>
>
> and an old thread on the clean-list mailing list about this topic:
>
> http://mailman.science.ru.nl/pipermail/clean-list/1995/000022.html
>
> which also turned out to refer to the mentioned article. My question 
> is: which of the proposed methods in the thread and article do you 
> recommend? Are there also libraries available to support the 
> distribution?
>
> Additional info: my program doesn't do much I/O, so I don't know 
> whether "piggy backing" on the World parameter is an elegant solution 
> (a suggestion I read in the old thread). Is the method of choice of 
> Burton and Page also the best according to you (random splitting of a 
> random sequence)?
>
> TIA!
>
> Chide
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.science.ru.nl/pipermail/clean-list/attachments/20111111/69202ca8/attachment.html>