Hi.
<RANT>
Simon Peyton-Jones writes:
> [...]
>
> Suppose next produced output in the range 0..16. (It's specified
> to produce "at least 30 bits", but the argument still holds.)
> Suppose we want random numbers in the range 0..10. We can't just
> take "mod 11" because that would produce too many values in the
> range 0..5. Indeed, if we don't know the range of next's result,
> we simply cannot generate uniformly distributed random numbers.
>
> The fix is [add a member function "genRange :: g -> (Int,Int)" to
> the class RandomGen g, and remove the "next yields at least 30
> bits" requirement]
>
> I regret the need for this change. Does anyone object to it? More
> particularly, can anyone think of a flaw?
I object, because I don't think there's a problem, either with bias or
with the 30 bit requirement.
It's quite common, when transforming one type of deviate into another,
to discard a few unsuitable input values before finding some which can
produce valid output.
For example, there's a transformation [PFTV] which takes two uniform
deviates, and returns either two normal (Gaussian) deviates (with
probability pi/4), or nothing.
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.
Koen Claessen writes:
> [...]
>
> If we're fixing bugs in the part about Random.hs in the Haskell'98
> library report, we might as well fix the following bug (spotted by
> John Hughes, but not present at the bug page).
>
> About "split", it says:
>
> "The split operation allows one to obtain two distinct random
> number generators. This is very useful in functional programs
> (for example, when passing a random number generator down to
> recursive calls), ..."
>
> This is not enough. An early Hugs implementation of "split" [...]
>
> [...]
>
> gen1
> / \
> gen1 gen2 -- once
> / | | \
> gen1 gen2 gen2 gen3 -- twice
>
> In fact, they will produce the *same* generator "gen2" on
> both sides, which will create an undesired dependency
> between the two recursive calls.
There are two respectable basic ways of getting a generator value:
mkStdGen (and its counterparts) and next. For most generators, it
seems perverse to create an entirely new way for split.
So, if there's to be any change to RandomGen, it should become:
class RandomGen g where
mkGen :: Int -> g
next :: g -> (Int, g)
split :: g -> (g, g)
split g = (mkGen seed, g') where (seed, g') = next g
That deals with the Indistinct Split problem, but leaves open the
possibility of unusually fancy split implementations for unusually
fancy generators.
A corresponding report change is from this:
"The split operation allows one to obtain two distinct random
number generators."
to this:
"The split operation allows one to obtain two random number
generators. The second of these is new, and the first is very
probably new, and very probably distinct from the second."
</RANT>
Regards,
Tom
[PFTV]
Press, Flannery, Teukolsky, Vetterling
Numerical Recipes in C - The Art of Scientific Computing
Cambridge University Press
1988
