How is the lagged fibonacci generator random?

I dont get. If it has a fixed length, choosing the lags and the mod over and over again will give the 开发者_如何学运维same number, no?

To be precise, the lagged Fibonacci is a pseudo-random number generator. It's not true random, but it's much better than, say, the more commonly used linear congruential generator (the standard generator for C++, Java, etc). I'm not sure why you think it will give the same number all over again, but it's true that like all pseudo-random number generator, it has a period after which the sequence of numbers will repeat again.

The multiplicative LFG has a period of (2^k - 1)*2^(M-3). For practical parameters, this is actually quite huge (LCG's period is only M).

The only catch with LFG is that the initialization procedure is very complex, and the mathematics behind it is incomplete. It's best to consult the literature for good choice of parameters and recommended procedure for proper seeding.

As an illustration, a multiplicative LFG with parameters (j=31, k=52) and modulus m=2^32 is seeded with an array of 52 32-bit numbers.

Additional references:

• http://sprng.fsu.edu/Version4.0/generators.html

  More details on this generator and the seeding algorithms can be found in papers by Mascagni, et al.

It's not random, its pseudorandom

From this http://en.wikipedia.org/wiki/Lagged_Fibonacci_generator

Lagged Fibonacci generators have a maximum period of (2^k - 1)*2^(M-1) if addition or subtraction is used, and (2^k-1) if exclusive-or operations are used to combine the previous values. If, on the other hand, multiplication is used, the maximum period is (2^k - 1)*2^(M-3), or 1/4 of period of the additive case.

So, given a certain seed value, the sequence of output values is predictable and repeatable, and it has a cycle. It will repeat if you wait long enough - but the cycle is quite large.

For an observer that doesn't know the seed value, the sequence appears to be quite random so it can be useful as a source of "randomness" for simulations and other situations where true randomness isn't required.

It's random in the same way that any pseudorandom number generator is--which is to say, not at all.

However, lagged fibonacci (and all linear feedback shift register PRNGs) improve on a basic linear congruential generator by increasing the state size. That is, the next value depends on several former values, rather than just the immediate previous one. Combined with a decent seed you should be able to get fairly decent results.

Edit:

From your post, it isn't clear that you understand that the underlying state is stored in a shift register, meaning that it isn't static but updated (by shifting each value one place to the left, dropping the leftmost value, and appending the most recent value on the right side) after each draw. In this way, drawing the same number over & over again is avoided (for most seed values, at least).

It all depends on the seed. Most random number generators do give the same sequence of numbers for a fixed seed value.

Random number generators are often one-to-one functions where for every input there is a constant output. To make it "random" you have to feed it a seed (which must be "random"), like the system time or the values of computer memory locations, for example.

If you're wondering why you don't just straight up use the seed (the time, etc.), it's because the time is sequential (1,2,3,4) whereas most pseudorandom number generators spit out numbers that appear random (8, 27, 13, 1). That way if you're generating pseudorandom numbers in a loop (which happens very fast), you're not just getting {1,2,3,4}...