Lagged Fibonacci generator

Last updated August 23, 2022

A Lagged Fibonacci generator (LFG or sometimes LFib) is an example of a pseudorandom number generator. This class of random number generator is aimed at being an improvement on the 'standard' linear congruential generator. These are based on a generalisation of the Fibonacci sequence.

In which case, the new term is some combination of any two previous terms. m is usually a power of 2 (m = 2^M), often 2³² or 2⁶⁴. The $\star$ operator denotes a general binary operation. This may be either addition, subtraction, multiplication, or the bitwise exclusive-or operator (XOR). The theory of this type of generator is rather complex, and it may not be sufficient simply to choose random values for j and k. These generators also tend to be very sensitive to initialisation.

Generators of this type employ k words of state (they 'remember' the last k values).

If the operation used is addition, then the generator is described as an Additive Lagged Fibonacci Generator or ALFG, if multiplication is used, it is a Multiplicative Lagged Fibonacci Generator or MLFG, and if the XOR operation is used, it is called a Two-tap generalised feedback shift register or GFSR. The Mersenne Twister algorithm is a variation on a GFSR. The GFSR is also related to the linear-feedback shift register, or LFSR.

Properties of lagged Fibonacci generators

Lagged Fibonacci generators have a maximum period of (2^k − 1)×2^M-1 if addition or subtraction is used, and (2^k − 1) × k if exclusive-or operations are used to combine the previous values. If, on the other hand, multiplication is used, the maximum period is (2^k − 1) × 2^M−3, or 1/4 of period of the additive case.

For the generator to achieve this maximum period, the polynomial:

y = x^k + x^j + 1

must be primitive over the integers mod 2. Values of j and k satisfying this constraint have been published in the literature.

Popular pairs of primitive polynomial degrees^[1]^[2]
j	7	5	24	65	128	6	31	97	353	168	334	273	418
k	10	17	55	71	159	31	63	127	521	521	607	607	1279

Another list of possible values for j and k is on page 29 of volume 2 of The Art of Computer Programming :

(24, 55), (38, 89), (37, 100), (30, 127), (83, 258), (107, 378), (273, 607), (1029, 2281), (576, 3217), (4187, 9689), (7083, 19937), (9739, 23209)

Note that the smaller number have short periods (only a few "random" numbers are generated before the first "random" number is repeated and the sequence restarts).

If addition is used, it is required that at least one of the first k values chosen to initialise the generator be odd; if multiplication is used, instead, it is required that all the first k values be odd.^[3]

It has been suggested that good ratios between j and k are approximately the golden ratio.^[4]

Problems with LFGs

In a paper on four-tap shift registers, Robert M. Ziff, referring to LFGs that use the XOR operator, states that "It is now widely known that such generators, in particular with the two-tap rules such as R(103, 250), have serious deficiencies. Marsaglia observed very poor behavior with R(24, 55) and smaller generators, and advised against using generators of this type altogether. ... The basic problem of two-tap generators R(a, b) is that they have a built-in three-point correlation between $x_{n}$ , $x_{n-a}$ , and $x_{n-b}$ , simply given by the generator itself ... While these correlations are spread over the size $p=max(a,b,c,\ldots )$ of the generator itself, they can evidently still lead to significant errors.".^[5] This only refers to the standard LFG where each new number in the sequence depends on two previous numbers. A three-tap LFG has been shown to eliminate some statistical problems such as failing the Birthday Spacings and Generalized Triple tests.^[4]

The initialization of LFGs is a very complex problem. The output of LFGs is very sensitive to initial conditions, and statistical defects may appear initially but also periodically in the output sequence unless extreme care is taken.^{[ citation needed ]} Another potential problem with LFGs is that the mathematical theory behind them is incomplete, making it necessary to rely on statistical tests rather than theoretical performance.

Usage

Freeciv uses a lagged Fibonacci generator with {j = 24, k = 55} for its random number generator.
The Boost library includes an implementation of a lagged Fibonacci generator.
Subtract with carry, a lagged Fibonacci generator engine, is included in the C++11 library.
The Oracle Database implements this generator in its DBMS_RANDOM package (available in Oracle 8 and newer versions).

Related Research Articles

A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. The values are usually used to index a fixed-size table called a hash table. Use of a hash function to index a hash table is called hashing or scatter storage addressing.

In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form $M n = 2 n - 1$ for some integer $n$ . They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17th century. If $n$ is a composite number then so is $2 n - 1$ . Therefore, an equivalent definition of the Mersenne primes is that they are the prime numbers of the form $M p = 2 p - 1$ for some prime $p$ .

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed. Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom number generators are important in practice for their speed in number generation and their reproducibility.

A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation. The method represents one of the oldest and best-known pseudorandom number generator algorithms. The theory behind them is relatively easy to understand, and they are easily implemented and fast, especially on computer hardware which can provide modular arithmetic by storage-bit truncation.

The Mersenne Twister is a general-purpose pseudorandom number generator (PRNG) developed in 1997 by Makoto Matsumoto and Takuji Nishimura. Its name derives from the fact that its period length is chosen to be a Mersenne prime.

In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.

In mathematics, a recurrence relation is an equation according to which the $th term of a sequence of numbers is equal to some combination of the previous terms. Often, only previous terms of the sequence appear in the equation, for a parameter that is independent of; this number is called the order of the relation. If the values of the first numbers in the sequence have been given, the rest of the sequence can be calculated by repeatedly applying the equation.$

RANDU is a linear congruential pseudorandom number generator (LCG) of the Park–Miller type, which was used primarily in the 1960s and 1970s. It is defined by the recurrence:

In finite field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite field $GF(p m)$ . This means that a polynomial $F (X)$ of degree $m$ with coefficients in $GF(p) = Z / p Z$ is a primitive polynomial if it has a root $α$ in $GF(p m)$ such that ${0, 1, α, α 2, α 3, ..., α p m -2}$ is the entire field $GF(p m)$ . This implies that $α$ is a primitive -root of unity in $GF(p m)$ .

In number theory, the nth Pisano period, written as $π$ (n), is the period with which the sequence of Fibonacci numbers taken modulo n repeats. Pisano periods are named after Leonardo Pisano, better known as Fibonacci. The existence of periodic functions in Fibonacci numbers was noted by Joseph Louis Lagrange in 1774.

A pseudorandom binary sequence (PRBS), pseudorandom binary code or pseudorandom bitstream is a binary sequence that, while generated with a deterministic algorithm, is difficult to predict and exhibits statistical behavior similar to a truly random sequence. PRBS generators are used in telecommunication, such as in analog-to-information conversion, but also in encryption, simulation, correlation technique and time-of-flight spectroscopy. The most common example is the maximum length sequence generated by a (maximal) linear feedback shift register (LFSR). Other examples are Gold sequences, Kasami sequences and JPL sequences, all based on LFSRs.

In computer science, multiply-with-carry (MWC) is a method invented by George Marsaglia for generating sequences of random integers based on an initial set from two to many thousands of randomly chosen seed values. The main advantages of the MWC method are that it invokes simple computer integer arithmetic and leads to very fast generation of sequences of random numbers with immense periods, ranging from around $to .$

The Lehmer random number generator, sometimes also referred to as the Park–Miller random number generator, is a type of linear congruential generator (LCG) that operates in multiplicative group of integers modulo n. The general formula is

Xorshift Class of pseudorandom number generators

Xorshift random number generators, also called shift-register generators, are a class of pseudorandom number generators that were discovered by George Marsaglia. They are a subset of linear-feedback shift registers (LFSRs) which allow a particularly efficient implementation in software without using excessively sparse polynomials. They generate the next number in their sequence by repeatedly taking the exclusive or of a number with a bit-shifted version of itself. This makes them execute extremely efficiently on modern computer architectures, but does not benefit efficiency in a hardware implementation. Like all LFSRs, the parameters have to be chosen very carefully in order to achieve a long period.

In sequence design, a Feedback with Carry Shift Register is the arithmetic or with carry analog of a linear-feedback shift register (LFSR). If $is an integer, then an N -ary FCSR of length is a finite state device with a state consisting of a vector of elements in and an integer . The state change operation is determined by a set of coefficients and is defined as follows: compute . Express s as with in . Then the new state is . By iterating the state change an FCSR generates an infinite, eventually periodic sequence of numbers in .$

Subtract-with-carry is a pseudorandom number generator: one of many algorithms designed to produce a long series of random-looking numbers based on a small amount of starting data. It is of the lagged Fibonacci type introduced by George Marsaglia and Arif Zaman in 1991. "Lagged Fibonacci" refers to the fact that each random number is a function of two of the preceding numbers at some specified, fixed offsets, or "lags".

In computational number theory, Marsaglia's theorem connects modular arithmetic and analytic geometry to describe the flaws with the pseudorandom numbers resulting from a linear congruential generator. As a direct consequence, it is now widely considered that linear congruential generators are weak for the purpose of generating random numbers. Particularly, it is inadvisable to use them for simulations with the Monte Carlo method or in cryptographic settings, such as issuing a public key certificate, unless specific numerical requirements are satisfied. Poorly chosen values for the modulus and multiplier in a Lehmer random number generator will lead to a short period for the sequence of random numbers. Marsaglia's result may be further extended to a mixed linear congruential generator.

References

Toward a universal random number generator, G.Marsaglia, A.Zaman

↑ "RN Chapter". www.ccs.uky.edu. Archived from the original on 9 March 2004. Retrieved 13 January 2022.
↑ "SPRNG: Scalable Parallel Pseudo-Random Number Generator Library". Archived from the original on 2010-06-14. Retrieved 2005-04-11.
↑ Parameterizing Parallel Multiplicative Lagged-Fibonacci Generators, M.Mascagni, A.Srinivasan
1 2 "Uniform random number generators for supercomputers", Richard Brent, 1992
↑ "Four-tap shift-register-sequence random-number generators", Robert M. Ziff, Computers in Physics, 12(4), Jul/Aug 1998, pp. 385–392

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] "RN Chapter". www.ccs.uky.edu. Archived from the original on 9 March 2004. Retrieved 13 January 2022.

[2] "SPRNG: Scalable Parallel Pseudo-Random Number Generator Library". Archived from the original on 2010-06-14. Retrieved 2005-04-11.

[3] Parameterizing Parallel Multiplicative Lagged-Fibonacci Generators, M.Mascagni, A.Srinivasan

[uniform-4] 1 2 "Uniform random number generators for supercomputers", Richard Brent, 1992

[5] "Four-tap shift-register-sequence random-number generators", Robert M. Ziff, Computers in Physics, 12(4), Jul/Aug 1998, pp. 385–392

[1]

[2]

[3]

[4]

[5]