Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

#1
October 21st, 2012, 05:46 AM
 drew99
Contributing User

Join Date: Sep 2011
Posts: 31
Time spent in forums: 7 h 17 m 4 sec
Reputation Power: 2
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
October 21st, 2012, 08:09 AM
 salem
Contributed User

Join Date: Jun 2005
Posts: 3,909
Time spent in forums: 2 Months 3 Weeks 4 Days 2 h 4 m 37 sec
Reputation Power: 1774
__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper

#3
October 21st, 2012, 08:16 AM
 drew99
Contributing User

Join Date: Sep 2011
Posts: 31
Time spent in forums: 7 h 17 m 4 sec
Reputation Power: 2
I need these informations, please don't close this post.
Thank you.

#4
October 21st, 2012, 02:59 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 3,460
Time spent in forums: 1 Month 2 Weeks 4 Days 6 h 56 m 42 sec
Reputation Power: 403
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```
__________________
[code]Code tags[/code] are essential for python code!

 Viewing: Dev Shed Forums > Programming Languages > C Programming > Lagged Fibonacci generator