Modification of Linear Congruential Generator

[ttw]

I have since discovered that, although there are lots of "local" theorems about the independence of quadratic residues, there are still problems. For primes of the form 4*k+3, the number of residues in (1,2k) is greater than the number in (2k+1,4k); I have been able to detect these even with 64+bit primes. For primes of the form 4*k+1, the intervals, (1,k) and (3k,4k) have more quadratic residues than do (k,2k) and (2k,2k). Also with primes of the form 3*k+1, the number of primes in (2k, 3k) is k, but the other intervals are not equal.

I did find a common computation that may suffer from this; if one computes Gaussian (or normal) variates using the Box-Muller or similar forms, one uses the random numbers u(n) and u(n+1) differently; one is for the radius and the other for the angle in the formula. While the u (Uniform random numbers) are uniformly distributed, the even or odd subsets are not necessarily uniform.

What's happening is that in a purely multiplicative generator (which has lots of good features), the multiplier is a "primitive root" of the base (so all powers of the multiplier cover the entire range). The square of a primitive root cannot be a primitive root (it's a perfect square) but will "walk" along the quadratic residues (or non-residues depending on the initial value) and covers half the range.

This problem does not occur with the usual pseudo-random number generators based on powers of two.

My fancier RNGs do combine various processes with LGCs and shift register generators. This removes all the "usual" problems. I'll post something later after I compute some parameters.