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.