I happened to look at src/sys/lib/libkern/arch/vax/random.S, and
I noticed an inconsitency that I then also found in all the other
libkern/arch/*/random.S.

random.S contains the following comment:

 * Here is a very good random number generator.  This implementation is
 * based on ``Two Fast Implementations of the "Minimal Standard" Random
 * Number Generator'', David G. Carta, Communications of the ACM, Jan 1990,
 * Vol 33 No 1.  Do NOT modify this code unless you have a very thorough
 * understanding of the algorithm.  It's trickier than you think.  If
 * you do change it, make sure that its 10,000'th invocation returns
 * 1043618065.
 *
 * Here is easier-to-decipher pseudocode:
 *
 * p = (16807*seed)<30:0>       # e.g., the low 31 bits of the product
 * q = (16807*seed)<62:31>      # e.g., the high 31 bits starting at bit 32
 * if (p + q < 2^31)
 *      seed = p + q
 * else
 *      seed = ((p + q) & (2^31 - 1)) + 1
 * return (seed);
 *
 * The result is in (0,2^31), e.g., it's always positive.

The first I noted (the least important) was the mis-use of "e.g.".  This
should be "i.e.". e.g. (exempli gratia) means "for example". i.e. (id
est) basically means "in other words".

Then I noticed that the second explanation was inconsistent with the
preceeding pseudocode:

    if
	<30:0> stands for the 31 bits #0 .. #30 (inclusive)
    then
	<62:31> stands for the 32 (not 31) bits #31 (not #32) ... #62.

So here are *two* inconsistencies: the starting bit and the number of
bits. Given the dire warning above, including "It's trickier than you
think." I think this is pretty serious. How is one to implement this, or
verify an implementation is correct?

I looked at all */random.S but I could not understand all of them, of
course. I don't know for sure if they all implement the same algorithm.
Judging by the m68k version, which I understood best, what is meant is

 * q = (16807*seed)<62:31>      # i.e., the high 32 bits starting at bit 31

I wanted to verify this with the machine-independent C version, which I
expected to be in src/sys/lib/libkern/random.c, but this seems to be a
verty different algorithm. I don't know if that is supposed to be a
problem.

-Olaf.
-- 
___ Olaf 'Rhialto' Seibert - rhialto@polder    -- Ah only did well at school
\X/ land.nl       -- tae git intae an O level class tae git away fae Begbie.
Hi! I am a .signature virus. Copy me into your .signature to help me spread.