Properties of Lagged Fibonacci Generators
Lagged Fibonacci generators have a maximum period of (2k - 1)*2M-1 if addition or subtraction is used, and (2k-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 (2k - 1)*2M-3, or 1/4 of period of the additive case.
For the generator to achieve this maximum period, the polynomial:
- y = xk + xj + 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 are:
- {j = 7, k = 10}, {j = 5, k = 17}, {j = 24, k = 55}, {j = 65, k = 71}, {j = 128, k = 159}, {j = 6, k = 31}, {j = 31, k = 63}, {j = 97, k = 127}, {j = 353, k = 521}, {j = 168, k = 521}, {j = 334, k = 607}, {j = 273, k = 607}, {j = 418, k = 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).
It is required that at least one of the first k values chosen to initialise the generator be odd.
It has been suggested that good ratios between j and k are approximately the golden ratio.
Read more about this topic: Lagged Fibonacci Generator
Famous quotes containing the words properties of, properties and/or lagged:
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)
“When any lagged behind, the cry of “blueberries” was most effectual to bring them up.”
—Henry David Thoreau (1817–1862)