( ESNUG 285 Item 4 ) ----------------------------------------------- [4/3/98]
Subject: Non-XOR Oriented Ways Of Generating Random Numbers
> How can you implement a random number generator?
>
> I remember thet it can be done with a shift register and XOR gates, but I
> forgot which bits to XOR for best results. The next possibility is with
> formula, but I can not remember them.
>
> - Simon Hribernik
> Metrel
From: nesterov@holo.ioffe.rssi.ru (Andrew V. Nesterov)
You can XOR, but it fails most of rigorous tests for randomness. Try a web
search on either Marsaglia or DIEHARD. Dr. Marsglia of FSU has written
several papers on the subject, some of them are accessible over the net.
Alternate approaches are with formulas like Multiply With Carry (MWC), Add
With Carry (AWC), Subtract With Borrow (SWB), Lagged Fibonacci (LFG) or any
of linear combinations of modulo M.
MWC: x(n) = A*x(n-1) + C mod M (upper bits are the new carry (C), lower
bits are the new pseudo-random number)
LFG: x(n) = x(n-s) op x(n-p) mod M (s > p > 0, op is either + or -)
AWC: x(n) = x(n-s) + x(n-p) + C mod M
SWB: x(n) = x(n-s) - x(n-p) - B mod M
For further reference take a look at:
http://www.taygeta.com/random.html
http://www.ncsa.uiuc.edu/Apps/SPRNG/www/paper/node1.html
ftp://stat.fsu.edu/pub/diehard
Hope it helps,
- Andrew V. Nesterov
Ioffe Phys. Techn. Institute Russia
|
|
