How is the lagged fibonacci generator random?
c, numbers, random
Solution
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.
Problem
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?