How good a pseudo-random number generator is the Fibonacci series?

BINSIC is moving on and now this code…

10 REM Fibonacci Series
20 LET X = 0.0
30 LET Y = 1.0
31 PRINT "How many numbers in series?"
32 INPUT FIBMAX
35 PRINT "Thanks"
36 PRINT "Now input some string, please"
37 INPUT A$38 PRINT "You entered ", A$
40 LET COUNT = 0
50 DIM Z(FIBMAX)
60 GOSUB 110
62 FOR I = 1 TO FIBMAX
64 PRINT "Fibonacci number ", I, " in series called ", A\$," is ", Z(I - 1)
66 NEXT I
70 END
110 IF COUNT = FIBMAX THEN RETURN
120 LET Z(COUNT) = X + Y
130 LET X = Y
140 LET Y = Z(COUNT)
160 LET COUNT = COUNT + 1
170 GOSUB 110


…will indeed generate a Fibonacci series (like all readers of the peerless Structure and Interpretation of Computer Programs I know I am using a lousy algorithm to generate the series but I hope you understand it is demonstration, rather than production, code).

This can work up to quite large values of FIBMAX – the poor algorithm gets in the way and the stack gets blown somewhere between 250 and 260 iterations, but the 250th number is 12776523572924732586037033894655031898659556447352249.

Now, very recently I was reading that the digits in Fibonacci numbers were an excellent way to generate (pseudo-)random numbers, so it strikes me that this number is a good candidate to test that theory on. So, I shall reprise the methods I used in January (from Data Analysis: A Bayesian Tutorial) to see just how random these digits are.

The Bayesian formula is: $pdf(H \vert \{data\},I) \propto pdf(\{data\} \vert H,I) \times pdf(H \vert I)$

Where, $pdf( ... )$ is a probability density function (PDF) and the above states that the final PDF is proportional to the product of the  initial (guessed or guided) PDF and the densities of the observed results.

I am going to start with an initial PDF that assumes that the distributions of digits inside a Fibonacci number are indeed truly random – i.e. each digit is as likely to come up as any other (1 in 10 times in other words, meaning each digit should have a probability of 0.1 of appearing). This makes it very easy to calculate a posterior PDF (the left hand term above) as the prior (the most rightwing term) is the same for all values.

The result is not too hot…

But maybe it is just not a long enough series – so let’s look at the 255th: 141693817714056513234709965875411919657707794958199867

But it seems to be even worse, though there seems to be no sign of a consistent bias, just a bias:

In short, I think I would be wary of claims that the Fibonacci series is a good basis for a high-quality pseudo-random number generator at least in the region I am testing here.

Advertisements