|
|
Posted by --CELKO-- on 10/02/29 11:44
Here is an implementation of the additive congruential method of
generating values in pseudo-random order and is due to Roy Hann of
Rational Commerce Limited, a CA-Ingres consulting firm. It is based on
a shift-register and an XOR-gate, and it has its origins in
cryptography. While there are other ways to do this, this code is nice
because:
1) The algorithm can be written in C or another low level language for
speed. But math is fairly simple even in base ten.
2) The algorithm tends to generate successive values that are (usually)
"far apart", which is handy for improving the performance of tree
indexes. You will tend to put data on separate physical data pages in
storage.
3) The algorithm does not cycle until it has generated every possible
value, so we don't have to worry about duplicates. Just count how many
calls have been made to the generator.
4) The algorithm produces uniformly distributed values, which is a nice
mathematical property to have. It also does not include zero.
Generalizing the algorithm to arbitrary binary word sizes, and
therefore longer number sequences, is not as easy as you might think.
Finding the "tap" positions where bits are extracted for feedback
varies according to the word-size in an extremely non-obvious way.
Choosing incorrect tap positions results in an incomplete and usually
very short cycle, which is unusable. If you want the details and tap
positions for words of one to 100 bits, see E. J. Watson, "Primitive
Polynomials (Mod 2)", Mathematics of Computation, v.16, 1962,
p.368-369.
We need to tap bits 0 and 3 to construct the 31-bit random-order
generated value Generator (which is the one most people would want to
use in practice):
UPDATE Generator31
SET keyval =
keyval/2 + MOD(MOD(keyval, 2) + MOD(keyval/8, 2), 2)* 8;
Or if you prefer, the algorithm in C:
int Generator31 ()
{static int n = 1;
n = n >> 1 | ((n^n >> 3) & 1) << 30;
return n;
}
Navigation:
[Reply to this message]
|