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

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
Full Text: