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?
A:
It all depends on the seed. Most random number generators do give the same sequence of numbers for a fixed seed value.
zdav
2010-03-02 04:29:54
*all pseudorandom* number generators give the same sequence of numbers for a fixed seed value... otherwise they would be truly random instead of pseudorandom.
Tyler McHenry
2010-03-02 04:31:47
@Tyler I vote that comment up but you make it sound as if not being periodical is sufficient to be random, which it is not (the decimals of pi are not random). I was once shown a nice definition of randomness in terms of the asymptotic evolution of the Kolmogorov complexity of the prefixes of an infinite string, but I can't find a reference online.
Pascal Cuoq
2010-03-02 04:41:18
Randomness is indeed a tricky subject.
zdav
2010-03-03 06:56:01
+1
A:
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).
Drew Hall
2010-03-02 04:33:29
initialization is complex? I thought it would be as easy as choosing (p,q) pairs like those that Kudth recommended. Maybe a sufficiently large table of such pairs.
chester.boo
2010-03-02 05:15:40
Choosing (p,q) is just fixing the "engine". You "run" it with a seed of q numbers, which must be chosen wisely. At least one of these numbers must be odd. In fact, if I remember correctly, I think all of them have to be odd if you're using multiplicative LFG. There's still a lot of possible seeds to chose from, so your choice is not limited, you just have to choose carefully. Traditionally the seed is generated with another generator, such as LCG.
polygenelubricants
2010-03-02 05:27:54
+3
A:
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.
John Knoeller
2010-03-02 04:35:48
Just to clarify, the seed value we are talking about is like (31,52), (24,55), (31,55), (7,57), (50,57)...and so on? Therefore, to make it seem random, we need a new (p,q) pair?
chester.boo
2010-03-02 05:01:30
Those pairs that you listed is not the seed. They're the `(j, k)` parameters.
polygenelubricants
2010-03-02 05:12:02
John Knoeller
2010-03-02 05:14:04
Note from the article _Freeciv uses a lagged Fibonacci generator with {j = 24, k = 55} for its random number generator._ so for that implementation, j and k are fixed, and the seed would just be the starting point.
John Knoeller
2010-03-02 05:15:14
I can see i misunderstood what the seed is. What would be the seed value or how is it selected for a LFG?
chester.boo
2010-03-02 05:18:35
@chester.boo: the seed can be any M-bit value, where M is usually either 32 or 64. from the article _the new term is some combination of any two previous terms. m is usually a power of 2 (m = 2^M), often 2^32 or 2^64_
John Knoeller
2010-03-02 05:48:24
Before generating the rnd number, the seed offsets the starting point in the fibonacci sequence?
chester.boo
2010-03-02 05:54:48
A:
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}...
advs89
2010-03-02 04:36:23