### Thread: Lagged Fibonacci generator

1. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Sep 2011
Posts
42
Rep Power
7

#### Lagged Fibonacci generator

Someone is able to explain me in detail how works the lagged Fibonacci generator?
If j and k are very large, how it's possible that in the first few cycles you can get f (n - j) and f (n - k)?
2. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Sep 2011
Posts
42
Rep Power
7
I need these informations, please don't close this post.
Thank you.
3. your j and k need not be terribly large,
and if j>k then the LFG needs j initial values.
And, you need only store j values.
In c a circular list is to me the obvious data structure to use. Here's an example using a queue.
Code:
```k is 1
j is 5
The binary operation is addition.  Many binary operations are ok, the choice affects sequence length and quality of the pseudo-random numbers.
modulus 10
n is 8

0 1 2 3 4 5 6 7     add list[n-1] to list[n-5] and append the sum mod 10
(7 + 3) mod 10  is  0.  Append the sum and
discard the first element in the list
1 2 3 4 5 6 7 0
(4+0)%10 gives 4
2 3 4 5 6 7 0 4
(4+5)%10 gives 9
3 4 5 6 7 0 4 9

etceteras gives LFG pseudo-random numbers
7 0 4 9 5 2 2 6 5 0 2 4 0 5 5 7 1 1 6 1 8 9 0 6 7 5 4 4 0 7...

4 5 6 7 0 4 9 5
5 6 7 0 4 9 5 2
6 7 0 4 9 5 2 2
7 0 4 9 5 2 2 6
0 4 9 5 2 2 6 5
4 9 5 2 2 6 5 0
9 5 2 2 6 5 0 2
5 2 2 6 5 0 2 4
2 2 6 5 0 2 4 0
2 6 5 0 2 4 0 5
6 5 0 2 4 0 5 5
5 0 2 4 0 5 5 7
0 2 4 0 5 5 7 1
2 4 0 5 5 7 1 1
4 0 5 5 7 1 1 6
0 5 5 7 1 1 6 1
5 5 7 1 1 6 1 8
5 7 1 1 6 1 8 9
7 1 1 6 1 8 9 0
1 1 6 1 8 9 0 6
1 6 1 8 9 0 6 7
6 1 8 9 0 6 7 5
1 8 9 0 6 7 5 4
8 9 0 6 7 5 4 4
9 0 6 7 5 4 4 0
0 6 7 5 4 4 0 7```