Lagged Fibonacci generator

This is a discussion on Lagged Fibonacci generator within the General Discussions forums, part of the Community Boards category; Someone is able to explain me in detail how works the lagged Fibonacci generator? If j and k are very ...

  1. #1
    Registered User
    Join Date
    Sep 2011
    Posts
    78

    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
    Left
    Join Date
    Oct 2011
    Posts
    816
    Based on the Wikipedia article on Lagged Fibonacci generator, a type of pseudorandom number generator:
    Code:
     f(n) = ( f(n-j) OP f(n-k) ) mod m
    where j < k < n, m is usually a power of two, and OP is a binary operator (addition, subtraction, multiplication, or exclusive or, in practice).

    "Before the first cycle", f(0 .. k-1) must be computed or set first.

    In practice, you keep f(n-k) to f(n-1) stored in an array. Then, the next value is obtained via
    Code:
    f[ n mod k ] = f[ (n + k - j) mod k ] OP f[ (n + k - k) mod k ]
    where the oldest value in the array is always replaced with the new value, and you only need an array with k entries.

  3. #3
    Registered User
    Join Date
    Sep 2011
    Posts
    78
    I've understood what you said, but i knew that you can generate pseudorandom sequence of numbers from one seed.
    Do I have to set/know n bits at the beginning, if I want to generate a sequence of n bits from some starting bits of a cipher algorithm key with a lagged Fibonacci generator?
    I knew that if you want to do this, you only have to initialize the generator with a seed.

  4. #4
    Left
    Join Date
    Oct 2011
    Posts
    816
    Quote Originally Posted by drew99 View Post
    i knew that you can generate pseudorandom sequence of numbers from one seed. Do I have to set/know n bits at the beginning, if I want to generate a sequence of n bits from some starting bits of a cipher algorithm key with a lagged Fibonacci generator?
    I knew that if you want to do this, you only have to initialize the generator with a seed.
    The lagged Fibonacci generator has k numbers of state. That is, the initial values f(0) .. f(k-1) define the sequence.

    A random number seed is a value that can be used to define the generator state. There are two types of seeds:
    1) The seed is large enough to be the state.
    For example, linear congruential pseudorandom number generators only have one number of state, so the state and the seed are the same thing.
    2) Seed is used to generate the state using some other algorithm.
    For example, Mersenne Twister has lots of state. A very simple way to generate a full state based on just one input is included in its examples.

    You stated that k is large, so the second approach makes more sense. A typical solution is to use a well-known LGC (See here for a list), using the seed for its initial state, to fill in the first k values. To reiterate: You only need the LGC for your initialization (similar to srand() for standard C library random number generator), as it is only used when you seed the state.

    You will always need to initialize your generator state before using it. It does not matter how many bits you are going to need from it (although in certain cases some of the state bits will not be used if you need only very few bits); the state is always the same size. (As an analogy, you wouldn't expect a half-built factory to produce half a product, would you? You need the entire factory to have it work at all.)
    Last edited by Nominal Animal; 10-21-2012 at 07:49 AM. Reason: Rewording

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with a Fibonacci
    By Thedog in forum C Programming
    Replies: 3
    Last Post: 01-17-2011, 05:04 PM
  2. Fibonacci
    By saria777 in forum C Programming
    Replies: 25
    Last Post: 06-16-2010, 07:26 AM
  3. Looking for source code of Lagged Fibonacci generator
    By user_name_void in forum C Programming
    Replies: 5
    Last Post: 02-28-2010, 01:29 PM
  4. Lagged GDI paint. can't find source of problem
    By neandrake in forum Windows Programming
    Replies: 0
    Last Post: 09-10-2006, 09:25 PM
  5. Fibonacci How should I make a generator
    By cprog in forum C Programming
    Replies: 12
    Last Post: 10-06-2002, 04:04 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21