On 03-Feb-2000, Tom Pledger <[EMAIL PROTECTED]> wrote:
> import Random
>
> instance Random Ordering where
>
> random = randomR (minBound, maxBound)
>
> randomR (lo, hi) gen | lo <= hi =
> let guaranteed = 2^30
> loInt = fromEnum lo
> hiInt = fromEnum hi
> modulus = hiInt - loInt + 1
> firstUseless = modulus * (guaranteed `div` modulus)
> rr g =
> let (i, g') = next g
> j = i `mod` guaranteed
> in if j < firstUseless then (j, g') else rr g'
> (raw, gen') = rr gen
> in (toEnum (loInt + raw `mod` modulus), gen')
I don't think that is guaranteed to work. I think you are assuming
that `j' is uniformly distributed in the range 0..(2^30-1).
But this is only true if the range of the numbers returned
by `next' (i.e. the range of `Int') is a power of two.
The Haskell report hints at this, saying that the range you
get is "at least 30 bits", but I this could easily
be interpreted as just requiring the range to be >= 2^30,
without requiring it to be a power of 2.
If it is not a power of 2, then the distribution of
`j' will be skewed.
The code that I posted doesn't make that assumption.
I think your code also has a problem with assuming
that 2^30 will fit into an `Int'. My code uses
`Integer' to avoid that.
--
Fergus Henderson <[EMAIL PROTECTED]> | "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit"
PGP: finger [EMAIL PROTECTED] | -- the last words of T. S. Garp.
