Talk:Lagged Fibonacci generator

Large number of cycles?

I don't believe that this statement is true, is it?

"any maximum period LFG has a large number of possible cycles, all different"

For example, many M-sequences have only two cycles, one of length 2^N-1, and one of length 1 (the element 0)

I also believe that many additive LFGs have only a very small number of cycles, with extremely long cycles.

Dubious claim?

"It is important that M be greater than 100 for the additive case"

This isn't true so I've removed it. OoS (talk) 11:49, 22 November 2007 (UTC)[reply]

Reference to The Art of Computer Programming

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

Not in the third edition. In the third edition the list is as follows (table 1, page 29):

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

OoS (talk) 17:43, 23 November 2007 (UTC)[reply]

The article refers to the second edition of TAOCP. However, this talk page says that it's different in the third edition, but gives the SAME LIST. — Preceding unsigned comment added by 132.244.72.6 (talk) 12:20, 5 June 2013 (UTC)[reply]

Mention of Matlab

Matlab by default now uses the mersenne twister, article needs updating to clarify —Preceding unsigned comment added by 80.3.31.37 (talk) 12:33, 27 September 2010 (UTC)[reply]

Error in definition of the maximum period

In the article you can find the following error:

Lagged Fibonacci generators have a maximum period of (2k - 1)*2M-1 if addition or subtraction is used, and (2^k-1)*k if exclusive-or operations are used to combine the previous values.

Correct is the following:

In the case if the xor operation is used as binary operation in the Lagged Fibonacci generators the period p equals to (2^k-1)*k only if (gcd(2^k-1, k) = 1). In all other cases the period p equals to lcm(2^k-1, k).

The following table lists some examples for small values of k:

k	(2^k-1)*k	lcm(2^k-1, k)	gcd(2^k-1, k)
3	21	21	1
4	60	60	1
5	155	155	1
6	378	126	3
7	889	889	1
8	2040	2040	1
...
12	49140	16380	3
...
18	4718574	524286	9
19	9961453	9961453	1
20	20971500	4194300	5
21	44040171	6291453	7
...

Legend: (gcd: greatest common divisor; lcm: least common multiple)

--Aragorn321 (talk) 20:37, 15 February 2013 (UTC)[reply]

vandalized page

79.112.127.128 (talk) 21:13, 29 April 2013 (UTC)[reply]

Dustr.badalyan (talk) 19:32, 19 May 2013 (UTC)[reply]

Dustr.badalyan (talk) 20:38, 21 May 2013 (UTC) — Preceding unsigned comment added by 174.61.207.104 (talk) [reply]

Missing a j,k pair or wrong pair cited?

The section “Properties of lagged Fibonacci generators” list known j,k pairs for parametrization of an LFG. Then section “Problems with LFGs” talks about some known issues with two pairs, which are R(103, 250) and R(24,55). However, only the second pair in cited in the former section; it does not mention the first pair. I wonder: is the first pair missing in the former section or is this an error in the latter section? I'm too much ignorant on the topic to check it myself, so someone else will have to do it; I just wanted to point a potential inconsistency. --Hibou57 (talk) 02:17, 20 July 2013 (UTC)[reply]

Rules for multiplicative LFGs

Knuth, errata to vol 2, pag 7 of http://www-cs-faculty.stanford.edu/~uno/err2-2e.ps.gz:

""" George Marsaglia [Comp. Sci. and Statistics: Symposium on the Interface 16 (1984), 3{10] has suggested replacing ( 7 ) by X(n) = ( X(n - 24) * X(n - 55) ) mod m ( 7 0 ) where m is a multiple of 4 and where X 0 through X 54 are odd, not all congruent to 1 (modulo 4). Then the second-least signicant bits have a period of 2^55 - 1, while the most signicant bits are more thoroughly mixed than before since they depend on all bits of X n 24 and X n 55 in an essential way. """

It makes sense (think about the bits: XXXXX01 * XXXXX01 will never give XXXXX11...), but I can't seem to find the exact reference - anyone?