Re: Random number generation

[Peter Horan]

brucemount wrote:
> I recently wrote a genetic algorithm program and had great difficulty
> with the pseudo-random number generators supplied with various Eiffel
> libraries (they were not very random at all which was causing problems).

As with all pseudorandom generators, their effectiveness depends on  
what you want to do.

The pseudorandom number generator provided in the class RANDOM is the  
Minimal Standard Number Generator discussed in Park and Miller,  
"Random number generators: good ones are hard to find", CACM, Vol 31,  
pp 1192-1201, 1988.

The generating function is f(z) = 7^5*z mod (2^31 -1)

This is full period, passes a number of tests for randomness and can  
be implemented efficiently. As the paper suggests, this generating  
function is often a good choice.

The function rand() referred to on www.random.org and used in Windows  
libraries, may be the same generator with bad choices of modulus and  
multiplier.

I don't know about 64 (or 63) bit cases. But I would be cautious. Note  
that 2^63 - 1 is not a prime number as 2^31 - 1 is. So, using this  
modulus may exhibit periodicities in the sequence.

See also http://members.cox.net/srice1/random/additive.html for a  
64-bit Additive Random Number Generator.

> So, I wrote a class that produces random numbers from the (far more
> random) files created by Random.org.  It is not as fast or convenient
> as the pseudo-random number generators (e.g., you need to download
> random.org files), but it does produce a perfectly even distribution
> (over enough trials).
>
> Would anyone else find this class helpful?  (If so, I'd have to clear
> it up a bit before submitting it.)  Do other people do simulations or
> genetic algorithm optimization using Eiffel?

If people need a True Random Number Generator, this would be a useful  
resource. I have not been using Random number generators in my current  
work, but it is useful to know about your material.

If you have not already done so, and if it is possible, I suggest  
using the interface of RANDOM for your class, so that it could be a  
"drop in" replacement for RANDOM.
--
Peter Horan             Faculty of Science and Technology
peter@...     Deakin University
[phone] (Voice) Geelong, Victoria 3217, AUSTRALIA
[phone] (FAX)   http://www.eit.deakin.edu.au/~peter

-- The Eiffel guarantee: From specification to implementation
-- (http://www.cetus-links.org/oo_eiffel.html)



------------------------------------

Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/eiffel_software/

<*> Your email settings:
    Individual Email | Traditional

<*> To change settings online go to:
    http://groups.yahoo.com/group/eiffel_software/join
    (Yahoo! ID required)

<*> To change settings via email:
    mailto:eiffel_software-digest@...
    mailto:eiffel_software-fullfeatured@...

<*> To unsubscribe from this group, send an email to:
    eiffel_software-unsubscribe@...

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/

[BruceMount]

Peter:

Peter Horan <peter@...> wrote:
> If you have not already done so, and if it is possible, I suggest  
> using the interface of RANDOM for your class, so that it could be a  
> "drop in" replacement for RANDOM.

Sorry for the slow response.  I had to do some "real" work first.  :-)
 I have (just now) looked at this and that would be difficult and
probably not very efficient.  Are there specific features of RANDOM
that you use?

Random.org provides text files that have a string of 8,388,608 ones
and zeros in random order.  My current implementation is that you give
a number X and it returns a random number between 1 and X.  My class
only grabs the number of bits needed to get a number at least as large
as X (e.g., if you only need a number from 1-4, it only grabs 2 "bits"
from the text string).

Hence random numbers are not presented as a list where you can access
the i_th element of the list and it does not currently give numbers
between 0 and 1.

Just to repeat, my class it is slower than RANDOM and expects you to
have downloaded files from Random.org, but it's really really random.

Does this still interest people?

--Bruce



------------------------------------

Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/eiffel_software/

<*> Your email settings:
    Individual Email | Traditional

<*> To change settings online go to:
    http://groups.yahoo.com/group/eiffel_software/join
    (Yahoo! ID required)

<*> To change settings via email:
    mailto:eiffel_software-digest@...
    mailto:eiffel_software-fullfeatured@...

<*> To unsubscribe from this group, send an email to:
    eiffel_software-unsubscribe@...

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/

[Peter Horan]

brucemount wrote:
> Peter:
>
> Peter Horan <peter@...> wrote:
>> If you have not already done so, and if it is possible, I suggest  
>> using the interface of RANDOM for your class, so that it could be a  
>>  "drop in" replacement for RANDOM.
>
> Sorry for the slow response.  I had to do some "real" work first.  :-)

Don't we all?

> Random.org provides text files that have a string of 8,388,608 ones
> and zeros in random order.  My current implementation is that you give
> a number X and it returns a random number between 1 and X.  My class
> only grabs the number of bits needed to get a number at least as large
> as X (e.g., if you only need a number from 1-4, it only grabs 2 "bits"
> from the text string).
>
> Hence random numbers are not presented as a list where you can access
> the i_th element of the list and it does not currently give numbers
> between 0 and 1.

RANDOM does not hold items as a stored list. The i-th item is  
recalculated from the seed if it is "before" the current item.  
Otherwise, it starts from the current item and count.

There are probably unnecessary features if files from random.org are  
used (e.g. seed, multiplier). The feature "modulus" could be used to  
control how many bits you take each time from the bit-stream. The  
feature "count" could be used to index into the bit-stream.

> Just to repeat, my class it is slower than RANDOM and expects you to
> have downloaded files from Random.org, but it's really really random.

I am surprised your scheme is slower because RANDOM does a multiply  
for each item.

> Does this still interest people?

I am sure it does interest people, although I have not used a RNG for  
some time. random.org is something I'll store away for future use.
--
Peter Horan             Faculty of Science and Technology
peter@...     Deakin University
[phone] (Voice) Geelong, Victoria 3217, AUSTRALIA
[phone] (FAX)   http://www.eit.deakin.edu.au/~peter

-- The Eiffel guarantee: From specification to implementation
-- (http://www.cetus-links.org/oo_eiffel.html)



------------------------------------

Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/eiffel_software/

<*> Your email settings:
    Individual Email | Traditional

<*> To change settings online go to:
    http://groups.yahoo.com/group/eiffel_software/join
    (Yahoo! ID required)

<*> To change settings via email:
    mailto:eiffel_software-digest@...
    mailto:eiffel_software-fullfeatured@...

<*> To unsubscribe from this group, send an email to:
    eiffel_software-unsubscribe@...

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/