Subject: Inconsistency in libkern/arch/*/random.S
To: None <current-users@netbsd.org>
From: Olaf Seibert <rhialto@polderland.nl>
List: current-users
Date: 10/14/2000 18:47:07
```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.
```