A new class of random number generators (Q809537)

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.