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

    Join Date
    Sep 2011
    Posts
    31
    Rep Power
    3

    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)?
    Thanks in advance for your answers.
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,376
    Rep Power
    1871
    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
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2011
    Posts
    31
    Rep Power
    3
    I need these informations, please don't close this post.
    Thank you.
  6. #4
  7. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,837
    Rep Power
    480
    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 and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo