How is a random fibonacci generator random?

Question

I do not understand. If it has a fixed length, the choice of delays and the mode will give the same number again and again, no?

Answer 1

To be precise, set aside Fibonacci is a pseudo random number generator. This is not true, random, but it is much better than, say, a more ordinary linear congruent generator (standard generator for C ++, Java, etc.), I'm not sure why you think that it will give the same number again, but it’s true that , like all pseudo-random number generators, it has a period after which the sequence of numbers will be repeated again.

Multiplicative LFG has a period of (2^k - 1)*2^(M-3) . For practical parameters, this is actually quite large (the LCG period is only M ).

The only catch with LFG is that the initialization procedure is very complicated, and the math behind it is incomplete. It is best to consult the literature for a good selection of parameters and the recommended procedure for proper seeding.

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

---

Additional links:

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

  More details about this generator and seeder algorithms can be found in the works of Mascagni and others.

Answer 2

It is no coincidence, its pseudorandom

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

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

Thus, given a certain initial value, the sequence of output values ​​is predictable and repeatable, and it has a cycle. It will happen again if you wait long enough, but the cycle is quite large.

For an observer who does not know the initial value, the sequence seems rather random, so it can be useful as a source of “randomness” for simulations and other situations where true randomness is not required.

Answer 3

This is random, just like any pseudo-random number generator - that is, not at all.

However, lagging Fibonacci (and all linear feedback linear PRNG shifts) improve the basic linear congruent generator by increasing staff size. That is, the next value depends on several previous values, and not only on the previous one. In combination with a decent seed, you can get pretty decent results.

Edit:

It is not clear from your message that you understand that the ground state is stored in the shift register, which means that it is not static, but is updated (by moving each value one place to the left, discarding the leftmost value, and adding the last value on the right side ) after every draw. Thus, eliminating the same number over and over can be avoided (for most seed values, at least).

Answer 4

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

Answer 5

Random number generators often have one-to-one functions, where for each input there is a constant output. To make it “random,” you must give it a seed (which must be “random”), such as the system time or the values ​​of the computer’s memory locations.

If you are wondering why you are not just using seeds (time, etc.), this is because time is sequential (1,2,3,4), while most pseudo-random number generators spit out numbers that seem random (8, 27, 13, 1). Thus, if you generate pseudo-random numbers in a loop (which happens very quickly), you are not just getting {1,2,3,4} ...