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

[Groenouwe, C.]

Dear Pieter,

Thank you for your valuable reply, I'm going to give your suggestion a try! I already discovered the MersenneTwister library before my first post, however, thanks for pointing out the caveat when using it with a huge number of splits. I don't think I will run into memory problems anytime soon, because in its current stage my program doesn't need that many splits. But I will keep your suggestion in mind at the moment it would...

Chide
________________________________
Van: Pieter Koopman [pieter at cs.ru.nl]
Verzonden: vrijdag 11 november 2011 12:02
Aan: Groenouwe, C.
CC: clean-list at science.ru.nl
Onderwerp: Re: distribution of 1 random number sequence throughout program

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/BurtonPageRngJFP.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/20111120/273cc1f8/attachment.html>