A new class of random number generators. (English) Zbl 0733.65005

Marsaglia, George; Zaman, Arif

Ann. Appl. Probab. 1, No. 3, 462-480 (1991).

The authors define and illustrate two new types of random number generators, called “add-with-carry” and “subtract-with-borrow” obtained by modification of the process usually utilized for the so called “lagged Fibonacci” generators.
Generally a lagged Fibonacci generator is obtained considering a finite set X of integer numbers and a function f(x) that transforms an r- dimensional vector \(x=(x_ i,x_{i+1},...,x_{i+r-1})\) of X into another vector of X in the following way: \(f(x)=f(x_ i,...,x_{i+r- 1})=(x_{i+1},x_{i+2},...,x_{i+r})\) with \(x_{i+r}=x_ i\oplus x_{i+r-s},\) where \(\oplus\) is a binary operation defined on X and \(1\leq s<r\). If we choose an arbitrary initial vector \(x=(x_ 1,x_ 2,...,x_ r)\) we obtain the sequence of vectors x,f(x), f(f(x)), f(f(f(x))), and so on and the sequence of numbers: \(x_ 1,x_ 2,...,x_ k,..\)..
An add with carry generator can be obtained introducing in the function f a suitable “carry bit” c. For example we can assume that X is the set of the integer numbers x with \(0\leq x<10\) and \(f(x_ i,x_{i+1},c)=(x_{i+1},x_ i+x_{i+1}+c,0)\) if \(x_ i+x_{i+1}+c<10,\) and \(=(x_{i+1},x_ i+x_{i+1}+c-10,1),\) if \(x_ i+x_{i+1}+c\geq 10.\) If we choose the initial vector (2,3,0) we obtain the sequence: 2,3,5,8,3,2,6,8,....
Analogous procedures are defined for the “complementary add-with-carry” generator and for the “subtract-with-borrow” generators. In the paper the periods of the sequences obtained by such procedures are studied and some examples of very long period sequences are illustrated.

Reviewer: M.Cugiani (Milano)

MSC:

65C10	Random number generation in numerical analysis
65C05	Monte Carlo methods

Keywords:

Monte Carlo methods; numerical examples; subtract-with-borrow generators; random number generators; lagged Fibonacci generator; add with carry generator; very long period sequences