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…

Fibonacci digits probability density function

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:

Fibonacci series digit PDF

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.

Some BASIC I can now run


10 REM Fibonacci Series
20 LET X = 0
30 LET Y = 1
40 LET COUNT = 0
45 IF COUNT < 1 THEN PRINT "HELLO THERE"
50 DIM Z(40)
60 GOSUB 100
62 FOR I = 0 TO 39
64 PRINT "Fibonacci number ", I, " is ", Z(I)
66 NEXT I
70 END
100 IF (COUNT > 39) THEN RETURN
110 LET Z(COUNT) = X + Y
120 LET X = Y
130 LET Y = Z(COUNT)
140 LET COUNT = COUNT + 1
150 GOSUB 100
160 RETURN

Meta programming: giving Integers a “fibonacci” property in Groovy


A tiling with squares whose sides are successi...
Image via Wikipedia

So, you just decide that each Integer should have an automatic property of knowing it’s Fibonacci number, well now your wish is granted:
Integer.metaClass.getFibonacci {
     fib = delegate
     def fibno = 1
     while (fib) {
         fibno += fibno
     fib--
     }
     return fibno
}

     Integer x = 25
     println x.fibonacci

I admit this is probably not the most useful additional property one could add to an integer and, of course, it is a function of an integer and not a property, but that was not my point…

Something more on Fibonacci numbers


Pascal triangle Fibonacci
Image via Wikipedia

My earlier blog about the Fibonacci series gets a lot of hits, so I thought I would write something more, as clearly there is interest.

Once again this is from “Structure and Interpretation of Computer Programs” (available for free here electronically):

Let \psi = (1 - \sqrt{5})/2 and \phi = (1 + \sqrt{5}/2) . Then Fib(n) = (\phi^n - \psi^n)/\sqrt{5} .

So Fib(1) = (\frac{1}{2} +\frac{\sqrt{5}}{2} - \frac{1}{2} + \frac{\sqrt{5}}{2})/\sqrt{5} = 1 .

(1)Fib(n) = (\phi^n - \psi^n)/\sqrt{5} = Fib(n - 1) + Fib(n - 2)

(2) Then Fib(n -1) + Fib( n - 2) = \frac{\phi^{n-1} - \psi^{n-1}}{\sqrt{5}} + \frac{\phi^{n-2} - \psi^{n-2}}{\sqrt{5}}

(3) Simplifying (2) Fib(n) = \frac{\phi^{n-1} - \psi^{n-1} + \phi^{n-2} - \psi^{n-2}}{\sqrt{5}}

(4) Simplifying further – from (1): \phi^n - \psi^n = \phi^{n-1} - \psi^{n-1} + \phi^{n-2} - \psi^{n-2}

(5) \phi^n - \psi^n = \phi^{n - 2}(\phi + 1) -\psi^{n- 2} - \psi^{n - 1}

(6) We know that \phi^2 = (\phi + 1) so we can restate (5) as \phi^n - \psi^n = \phi^n - \psi^{n - 2} - \psi^{n - 1}

So (7) \psi^n = \psi^{n - 2} + \psi^{n - 1}

But \psi^2 = \psi + 1 also and (7) can be restated as \psi^n = \psi^{n-2}(\psi + 1) = \psi^{n-2}\psi^2 = \psi^n

In other words, Fib(n) = (\phi^n - \psi^n)/\sqrt{5} .

Something interesting about Fibonacci numbers


Maybe everyone else knows this already – but I did not until I was reading Structure and Interpretation of Computer Programs and I picked it up…

Well, the Fibonacci series are defined as:

Fibonacci series definitionThis generates the sequence 0, 1, 1, 2, 3, 5 etc.

(Apparently Fibonacci, real name Leonardo Pisano Bigollo, used the sequence to model rabbit populations in the 13th century, though perhaps more importantly he essentially codified the western system of arabic numbers. The sequence was known by Indian mathematicians long before then though.)

But the sequence is perhaps most interesting for its relationship to the “golden ratio” (or golden mean), phi:

Golden meanwhich means phi has the value:

phi

This is the ratio where:

Golden ratio

 

The interesting thing about the Fibonacci series for n is that each number in the series is the closest integer to:

SeriesProof

 

%d bloggers like this: