Fwd: Re: Random Numbers fasters than the osax
Fwd: Re: Random Numbers fasters than the osax
- Subject: Fwd: Re: Random Numbers fasters than the osax
- From: email@hidden (Michael Sullivan)
- Date: Thu, 4 Apr 2002 17:33:30 -0500
- Organization: Society for the Incurably Pompous
Timothy Bates wrote:
>
I just thought that I would not, for the list, that this random number
>
generator is not what most users (wanting random numbers, rather than
>
conducting special simulations) would want.
>
>
It does not repeat any values before it has emitted all values in the range,
>
i.e., selection without replacement.
>
>
However, nearly all uses of random data from a range of values - tosses of a
>
coin, for instance are WITH replacement. If you use this system to simulate
>
coin tosses (random from 1 to 2), youl get the sequence
>
>
1212121212 repeating ad-infinitum ...
I don't think so. Not the one I posted anyway. This is the output of a
run of that algorithm using my random(1,2) 100 times:
{1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1,
1, 1, 2, 2, 2, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2,
1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 1, 1, 2, 2, 2, 1,
1, 2, 2, 2, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2,
2, 2, 2, 2}
It is true that if the number of possible returns approaches the size of
BigPrime, the generator starts to have the quality you're talking about.
If you set it to return random integers from 0 to 2^31 -1, then you are
correct, you will never see a repeat until you've exhausted all the
possibilities.
If you want integers between 1 and even 10000 or so, you'll start to see
chiSquare results that look suspicious, and at 100000, they'll be
downright poor. Has pointed me to a website (www.random.org) that had
the chiSquare formula and a calculator for the heavy duty diff eq
involved in evaluating the result. As a result I've done a bunch of
testing. It looks like the limit of really good pseudo-random data for
that sequence is around 3 significant digits, with decent non-critical
performance in the 4-5 range. At 6-7 digits (1 to 1 million), it is
essentially non-random.
Similarly if you try to return even a one-bit result (heads or tails),
you'll eventually see repetition after about a billion tries. the more
significant the result, the fewer numbers you can get out of the
generator before the sequence loses it's entropic structure.
In general, I think the number of calls it is safe to make before
reseeding [*] can be determined by this formula:
safeCalls = kBigPrime/(n^2)
where n is the number of significant returns (i.e. returning
results from 1 to n).
This also sheds light on why 5 significant digits is already suspicious.
That puts n^2 at 10 billion, larger than kBigPrime, so the number of
safe calls is zero.
Even though the original isn't even up yet, I've already got a 1.1
version that will be ready soon, which is a bit faster, and whose test
suite includes a calculation of chi-square so the user can verify for
themselves just how close to random the sequence is for any particular
purpose.
Michael
[*] I believe that if one reseeded from a source of real randomness, at
random times determined by the same source but always less than the
number of safe calls, that the data provided by this algorithm would
remain excellent indefinitely.
_______________________________________________
applescript-users mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/applescript-users
Do not post admin requests to the list. They will be ignored.