Generalized Inversive Congruential Pseudorandom Numbers
   HOME

TheInfoList



Click Here for Items Related To - Generalized Inversive Congruential Pseudorandom Numbers
OR:
Generalized Inversive Congruential Pseudorandom Numbers on:   [Wikipedia]   [Google]   [Amazon]

An approach to nonlinear congruential methods of generating uniform pseudorandom numbers in the interval ,1) is the Inversive congruential generator with prime modulus. A generalization for arbitrary composite moduli m=p_1,\dots p_r with arbitrary distinct Prime number">primes A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
p_1,\dots ,p_r \ge 5 will be present here. Let \mathbb_ = \ . For integers a,b \in \mathbb_ with gcd (a,m) = 1 a generalized inversive congruential sequence (y_)_ of elements of \mathbb_ is defined by : y_ = : y_\equiv a y_^ + b \pmod m \textn \geqslant 0 where \varphi(m)=(p_-1)\dots (p_-1) denotes the number of positive integers less than ''m'' which are
relatively prime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
to ''m''.


Example

Let take m = 15 = 3 \times 5\, a=2 , b=3 and y_0= 1. Hence \varphi (m)= 2 \times 4=8 \, and the sequence (y_)_=(1,5,13,2,4,7,1,\dots ) is not maximum. The result below shows that these sequences are closely related to the following inversive congruential sequence with prime moduli. For 1\le i \le r let \mathbb_= \, m_= m / p_ and a_ ,b_ \in \mathbb_ be integers with : a\equiv m_^ a_\pmod \;\text\; b\equiv m_ b_\pmod \text Let (y_)_ be a sequence of elements of \mathbb_, given by : y_^\equiv a_ (y_^)^ + b_ \pmod \; \textn \geqslant 0 \;\text \;y_\equiv m_ (y_^)\pmod \;\text


Theorem 1

Let (y_^)_ for 1\le i \le r be defined as above. Then : y_\equiv m_y_^ + m_y_^ + \dots + m_y_^ \pmod m. This theorem shows that an implementation of Generalized Inversive Congruential Generator is possible, where exact integer computations have to be performed only in \mathbb_,\dots , \mathbb_ but not in \mathbb_. Proof: First, observe that m_\equiv 0\pmod , \; \text \; i\ne j, and hence y_\equiv m_y_^ + m_y_^ + \dots + m_y_^ \pmod m if and only if y_\equiv m_ (y_^)\pmod , for 1\le i \le r which will be shown on induction on n \geqslant 0 . Recall that y_\equiv m_ (y_^)\pmod is assumed for 1\le i \le r. Now, suppose that 1\le i \le r and y_\equiv m_ (y_^)\pmod for some integer n \geqslant 0 . Then straightforward calculations and Fermat's Theorem yield : y_\equiv a y_^ + b \equiv m_(a_m_^(y_^)^+ b_)\equiv m_(a_(y_^)^ + b_)\equiv m_(y_^) \pmod , 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 D_m ^=D_m (x_0,\dots , x_m-1) where x_n=(x_n, x_n+1 ,\dots , x_n+s-1) [0,1)^s of Generalized Inversive Congruential Pseudorandom Numbers for s\ge 2. Higher bound :Let s\ge 2 :Then the discrepancy D_m ^s satisfies : D_m ^s < m^ ( \frac \log m + \frac)^s \textstyle \prod_^r (2s-2 + s(p_i)^)+ s_^ for any Generalized Inversive Congruential operator. Lower bound: :There exist Generalized Inversive Congruential Generators with : D_m ^s \frac m^ : \textstyle \prod_^r (\frac )^ for all dimension ''s'' 2. For a fixed number ''r'' of prime factors of ''m'', Theorem 2 shows that D_m^ = O (m^ (\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 D_m^ which is at least of the order of magnitude m^ for all dimension s\ge 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 \textstyle \prod_^r (2s-2 + s(p_i)^)= O for every \epsilon> 0. Therefore, one obtains in the general case D_m^=O(m^) for every \epsilon> 0. Since \textstyle \prod_^r ((p_ - 3)/(p_ - 1))^ \geqslant 2^ , similar arguments imply that in the general case the lower bound in Theorem 3 is at least of the order of magnitude m^ for every \epsilon> 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^ (\log\log m)^ according to the law of the iterated logarithm for discrepancies. 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


Notes

* {{DEFAULTSORT:Generalized Inversive Congruential Pseudorandom Numbers Pseudorandom number generators