Generalized inversive congruential pseudorandom numbers

An approach to nonlinear congruential methods of generating uniform pseudorandom numbers in the interval [0,1) is the Inversive congruential generator with prime modulus. A generalization for arbitrary composite moduli m=p1,…pr with arbitrary distinct primes p1,…,pr≥5 will be present here.

Let ℤm={0,1,...,m−1}. For integers a,b∈ℤm with gcd (a,m) = 1 a generalized inversive congruential sequence (yn)n⩾0 of elements of ℤm is defined by

y0=seed
yn+1≡aynφ(m)−1+b(modm), n⩾0

where φ(m)=(p1−1)…(pr−1) denotes the number of positive integers less than m which are relatively prime to m.

## Contents

* 1 Example
* 2 Theorem 1
* 3 Discrepancy bounds of the GIC Generator
* 4 See also
* 5 References
* 6 Notes

## Example

Let take m = 15 = 3×5a=2,b=3 and y0=1. Hence φ(m)=2×4=8 and the sequence (yn)n⩾0=(1,5,13,2,4,7,1,…) is not maximum.

The result below shows that these sequences are closely related to the following inversive congruential sequence with prime moduli.

For 1≤i≤r let ℤpi={0,1,…,pi−1},mi=m/pi and ai,bi∈ℤpi be integers with

a≡mi2ai(modpi)and b≡mibi(modpi).

Let (yn)n⩾0 be a sequence of elements of ℤpi, given by

yn+1(i)≡ai(yn(i))pi−2+bi(modpi), n⩾0wherey0≡mi(y0(i))(modpi)is assumed.

## Theorem 1

Let (yn(i))n⩾0 for 1≤i≤r be defined as above. Then

yn≡m1yn(1)+m2yn(2)+…+mryn(r)(modm).

This theorem shows that an implementation of Generalized Inversive Congruential Generator is possible, where exact integer computations have to be performed only in ℤp1,…,ℤpr but not in ℤm.

Proof:

First, observe that mi≡0(modpj),fori≠j, and hence yn≡m1yn(1)+m2yn(2)+…+mryn(r)(modm) if and only if yn≡mi(yn(i))(modpi), for 1≤i≤r which will be shown on induction on n⩾0.

Recall that y0≡mi(y0(i))(modpi) is assumed for 1≤i≤r. Now, suppose that 1≤i≤r and yn≡mi(yn(i))(modpi) for some integer n⩾0. Then straightforward calculations and Fermat's Theorem yield

yn+1≡aynφ(m)−1+b≡mi(aimiφ(m)(yn(i))φ(m)−1+bi)≡mi(ai(yn(i))pi−2+bi)≡mi(yn+1(i))(modpi),

which implies the desired result.

Generalized Inversive Congruential Pseudorandom Numbers are well equidistributed in one dimension. A reliable theoretical approach for assessing their statistical independence properties is based on the discrepancy of s-tuples of pseudorandom numbers.

## Discrepancy bounds of the GIC Generator

We use the notation Dms=Dm(x0,…,xm−1) where xn=(xn,xn+1,…,xn+s−1) ∈ [0,1)s of Generalized Inversive Congruential Pseudorandom Numbers for s≥2.

Higher bound

Let s≥2
Then the discrepancy Dms satisfies
Dm s < m−1/2 × (2π × log⁡m+75)s × ∏i=1r(2s−2+s(pi)−1/2)+sm−1 for any Generalized Inversive Congruential operator.

Lower bound:

There exist Generalized Inversive Congruential Generators with
Dm s ≥ 12(π+2) × m−1/2 : × ∏i=1r(pi−3pi−1)1/2 for all dimension s :≥ 2.

For a fixed number r of prime factors of m, Theorem 2 shows that Dm(s)=O(m−1/2(log⁡m)s) for any Generalized Inversive Congruential Sequence. In this case Theorem 3 implies that there exist Generalized Inversive Congruential Generators having a discrepancy Dm(s) which is at least of the order of magnitude m−1/2 for all dimension s≥2. However, if m is composed only of small primes, then r can be of an order of magnitude (log⁡m)/log⁡log⁡m and hence ∏i=1r(2s−2+s(pi)−1/2)=O(mϵ) for every ϵ>0.[1] Therefore, one obtains in the general case Dms=O(m−1/2+ϵ) for every ϵ>0.

Since ∏i=1r((pi−3)/(pi−1))1/2⩾2−r/2, similar arguments imply that in the general case the lower bound in Theorem 3 is at least of the order of magnitude m−1/2−ϵ for every ϵ>0. It is this range of magnitudes where one also finds the discrepancy of m independent and uniformly distributed random points which almost always has the order of magnitude m−1/2(log⁡log⁡m)1/2 according to the law of the iterated logarithm for discrepancies.[2] In this sense, Generalized Inversive Congruential Pseudo-random Numbers model true random numbers very closely.

## See also

* Pseudorandom number generator
* List of random number generators
* Linear congruential generator
* Inversive congruential generator
* Naor-Reingold Pseudorandom Function

## References

1. ↑ G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Clarendon Press, Oxford, 1979.
2. ↑ J. Kiefer, On large deviations of the empiric d.f. Fo vector chance variables and a law of the iterated logarithm, PacificJ. Math. 11(1961), pp. 649-660.

## Notes

* Eichenauer-Herrmann, Jürgen (1994), "On Generalized Inversive Congruential Pseudorandom Numbers", Mathematics of Computation (American Mathematical Society) 63 (207): 293–299, doi:10.1090/S0025-5718-1994-1242056-8

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Generalized inversive congruential pseudorandom numbers. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Generalized_inversive_congruential_pseudorandom_numbers&oldid=4410994"