Alexander Farber <[EMAIL PROTECTED]> asks:
...
> If % is not good enough for getting random values in a range, then what is?
...
Actually, % 32 is fine (or any reasonably small power of 2). Modulo
any odd number is guaranteed to have at least a small problem, and
module a large enough number is going to start to get really bad.
To illustrate the problem, suppose you had a "perfect" rand
function that returned numbers in the range 0-255. On average,
about half the time, the numbers will be even or odd. That's %2.
Any power of two up to 128 will work perfectly as well.
Now, suppose instead we take it module 189. For values out of
the rand function less than 189, things work fine. However, there
are only 67 values >= 189, so the output of this will be twice
as likely to pick values 0-66 as it is values 67-188. That's
sort of really bad. Now, the output from arc4random() is really
quite large, so for small values of N, %N will be fine. It's
only for large values of N that this roundoff problem is going
to be significant. The for N=289 and using arcrandom(), the bias
is only 0.000000044, so it would take a lot of values to estimate
this empirically.
Another way to fix this, is if you're using %, make sure the random
value you plug into % is smaller than the largest multiple. For 189,
that would be 22724694*189 or 4294967296U. If the number you get
is larger than this, discard it and obtain another random number.
If you throw out the last 130 values, you've now got a fair generator.
rc4 is a common cheap expansion function for random functions.
A higher quality but slower method is to use sha-1 or some other
function. Another possible alternative is to use a symmetric algorithm
such as aes or blowfish. Typically you would plug your seed plus
a counter into the input of these functions, then supply the output
(perhaps with some truncation) as the result of your function.
Incidently, I think your card shuffling algorith has some of the same
problems as the rc4 key schedule algorithm. You might want to read up
on that.
-Marcus Watts
