Gaussian Noise Generation

Gordon Sande wrote:
(snip on linear congruential RNGs)

> Depends on the multiplier and the additive constant. In general yes but
> for the common cases running around wild no. The additive constant of
> zero, which is very common, is enough for no.

Well, it also (and primarily) depends on the modulus.  Most of
the popular generators have a power of two modulus.  In that case,
lower bits can effect higher bits, but not the other way around.

With an odd multiplier and odd additive term and even modulus
the LSB will change each cycle.  With a power of two modulus
the best you can do for the low N bits is a cycle of 2**N.

When I need a random number between 1 and M, I take the result
from the generator, divide it by a prime number somewhere
around the square root of the modulus divided by M, and then
take the result modulo M and add one.   If that is fast enough,
it usually generates good results.

Otherwise, LFSR's such as the CRC generators are better at
mixing up the bits and if you have XOR available as an operation
should be very fast.

> See Knuth or some other reliable source for the number theory details.

Yes, volume 2 specifically.

-- glen

glen herrmannsfeldt wrote:
> Gordon Sande wrote:

   ...

>> See Knuth or some other reliable source for the number theory details.
> 
> Yes, volume 2 specifically.

Chapter three, even more specifically.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯