Lagged Fibonacci Generator - Problems With LFGs

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, and, simply given by the generator itself ... While these correlations are spread over the size of the generator itself, they can evidently still lead to significant errors.". 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.

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. 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.

Read more about this topic:  Lagged Fibonacci Generator

Famous quotes containing the words problems with and/or problems:

    She has problems with separation; he has trouble with unity—problems that make themselves felt in our relationships with our children just as they do in our relations with each other. She pulls for connection; he pushes for separateness. She tends to feel shut out; he tends to feel overwhelmed and intruded upon. It’s one of the reasons why she turns so eagerly to children—especially when they’re very young.
    Lillian Breslow Rubin (20th century)

    The mother’s and father’s attitudes toward the child correspond to the child’s own needs.... Mother has the function of making him secure in life, father has the function of teaching him, guiding him to cope with those problems with which the particular society the child has been born into confronts him.
    Erich Fromm (1900–1980)