granvold@tymix.UUCP (01/24/84)
-
A few years ago I saw a memory test program that used the Fibonacci
sequence as a random number generator (Yes, I know that it makes a lousy
random number generator). This was for a minicomputer that had a 16 bit
word size. Fairly quickly the magnitude of the Fibonacci numbers would
become greater than two to the sixteenth. The high order bits would be
dropped, keeping only the low order 16 bits. That is all the calculations
of the Fibonacci numbers would be done modulo 2 to the 16th.
My questions are; how many numbers are generated before it enters a
repeating cycle, and how long is that cycle? A lower bound is a cycle of
2. This would occure if for some n:
f(n) = f(n+2)(mod 2 to the 16th)
The upper bound is 2 to the 32th. This is for a 16 bit word size.
For a cycle to repeat 2 consecutive numbers in the sequence must be the
same as 2 consecutive numbers earlier in the sequence. Any one number
can have one of 2 to the 16th possible values. So for 2 numbers, there
are 2 to the 32th possible values.
This is as for as my mathematic ability takes me. I would appreciate
answers to the questions above. Also, is it possible to generalize the
answers to any word size?
Thanks,
Tom Granvold
Tymshare
Cupertino, Calif.
decvax!ucbvax!oliveb!tymix!granvold
P.S. I will the answers in net.math in a week or two.