Matt Harden writes:
> Tom Pledger wrote:
> > [...]
> >
> > A similar approach can be taken, for getting uniform deviates (of
> > types in Enum) from a generator in Haskell, without the bias. Just
> > keep applying next, until you get an Int whose 30 trusted bits don't
> > introduce the bias.
> > (You may be dealing with a range size greater than 2^30, but that's
> > another story. It means consuming more than one Int at a time, from
> > your generator's sequence.)
> >
> > The 30 bit requirement is a good practical guideline.
>
> This sounds similar to Fergus Henderson's suggestion, for which he
> supplied code. Please see my reply to him, and respond to my comments
> if you like.
Why certainly! I'm having a talkative week/month/...
> To me, these solutions seem very inefficient and statistically
> dangerous, compared to just knowing the RNG's range (which is
> almost always fixed) ahead of time. It seems to me that you have
> to throw out at least two numbers from next for every "good" number
> you get.
This is the sort of thing I meant:
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')
test n =
let os = take n . randoms $ mkStdGen 0
in (length $ filter (LT==) os,
length $ filter (EQ==) os,
length $ filter (GT==) os)
To see that it solves the bias problem, change `guaranteed' to 4 and
try `test 1000'. You don't get as many LT as everything else put
together.
It doesn't waste much of the period of the generator. The worst case
is when modulus == 2^29 + 1, which wastes just under half of the
period. The alternatives don't appeal:
- Back the generator up by 49% of a next. Very indiscrete.
- Use non-guaranteed bits, and risk meeting an evil generator whose
31st bit is always equal to its 30th bit.
Regards,
Tom
