[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).