[MLton] Wrong behaviour of MLton.Random.alphaNumString?
Matthew Fluet
fluet@cs.cornell.edu
Sun, 28 Dec 2003 17:46:11 -0500 (EST)
> c) I tried to take a look at the code in question
> (lib/mlton-stubs/random.sml). I find it rather wierd that after the
> first 6 characters have been set no more calls to rand () occurs.
> (Line 19 to 46). It seems that the random function works by wrapping
> around the word, and currently I do not have the time to read the
> algebra needed to get that little bugger sorted out.
I think there are actually a couple of bugs in both:
basis-library/mlton/random.sml
lib/mlton-stubs/random.sml
The high-level view of the code is the following: a 32-bit random word has
enough random bits to index into the string of alpha-num characters more
than once. So, we can speed things up a little by not calling rand() for
each character. Instead, we store a random word in r : Word.word ref,
peel off some low bits with Word.mod (and use them to index into the
string for a random character), and then shift those used bits out of r
with Word.div. But, we need to periodically refresh the random bits.
Therefore, rather than Int.quot, it should be Int.rem.
However, I am (more than) a little suspicious of the hard-coded 6. In
particular, 62^6 = 56,800,235,584; not 965,660,736. I'm not sure where
that number came from. The comment is (supposedly) showing that 62^6 (the
number of outcomes of making 6 random choices from a set of 62 elements)
is less than 2^32 (the number of outcomes of calling rand()), which would
imply that there are enough random bits in a random word to cover indexing
6 times. However, this isn't the case, as 62^6 > 2^32.
Regardless, we should really compute the refresh period, rather than
hard-code it. I believe we should have:
val m = Int.quot(Word.wordSize, IntInf.log2 (IntInf.fromInt n) + 1)
For Word.wordSize = 32 and n = 62, then m = 5. So, for a quick-fix,
change
Int.quot(i,6)
to
Int.rem(i,5).