Fibonacci numbers at work

Posted on by John

Today I needed to use Fibonacci numbers to solve a problem at work. Fibonacci numbers are great fun, but I don’t recall needing them in an applied problem before.

I needed to compute a series of integrals of the form

f(x, y) = x^a (1-x)^b y^c (1-y)^d \,p(x, y)

over the unit square for a statistical application. The function p(x, y) is a little complicated but its specific form is not important here. If the constants a, b, c, and d are all positive, as they usually are in my application, the integrand can be extended to a continuous periodic function in the plane. Lattice rules are efficient for such integration problems, and the optimal lattice rules for two-variable integration are given by Fibonacci lattice rules.

If Fk is the kth Fibonacci number and {x} is the remainder when subtracting off the greatest integer less than x, the kth Fibonacci lattice rule approximates the integral of f by

\frac{1}{F_n} \sum_{j=0}^{F_n-1} f\left( \left\{ \frac{j}{F_k}\right\}, \left\{\frac{jF_{n-1}}{F_n}\right\} \right)

This rule worked well. I compared the results to those using the two-variable trapezoid rule and the lattice rule always gave more accuracy for the same number of integration points. (Normally the trapezoid rule is not very efficient. However, it can be surprisingly efficient for periodic integrands. See point #2 here. But the Fibonacci lattice rule was even more efficient.)

To implement this integration rule, I first had to write a function to compute Fibonacci numbers. This is such a common academic exercise that it is almost a cliché. I was surprised to have a practical need for such a function. My implementation was

    int Fibonacci(int k)
    {
        double phi = 0.5*(1.0 + sqrt(5.0));
        return int( pow(phi, k)/sqrt(5.0) + 0.5 );
    }

The reason this works is that

equation for Fibonacci numbers

where

definition of phi, golden ratio

is the golden ratio. The second term in the formula for Fk is smaller than 1, and Fk is an integer, so by rounding the first term to the nearest integer we get the exact result. Adding 0.5 before casting the result to an integer causes the result to be rounded to the nearest integer.

If you’re interested in technical details of the numerical integration method, see Lattice Methods for Multiple Integration by I. H. Sloan and S. Joe.

10 thoughts on “Fibonacci numbers at work”

  1. One interesting thing about these classic sequences is that they grow very quickly. So if you’re programming in C++ with fixed width integers, int Fibonacci(int) might as well use a simple lookup table. For a 4 byte int, you’d need fewer than 50 entries. And int Factorial(int) would only need 13 entries! Of course you’d still use a program to calculate these entries.

  2. Never seen the formula written like ((GoldenRatio)^n – (-GoldenRatio)^-n)/Sqrt[5] as you do, but it is correct and I liked it ( but mathematicians should be conservative to preserve past work ).

    The most efficient way of calculating the Fibonacci numbers I have found thus far is f(n_):=Floor[(GoldenRatio)^n/Sqrt[5]+0.5]. (Using Mathematica syntax)

    I like your blog and have added it to Math Blogs on http://mathematics-diary.blogspot.com/

  3. Jonathan Hogg

    There really is something about seeing the old-school examples pop up in the real world…I think it speaks volumes about the way we are all, at some level, verschulert to the point that even the most avid learner starts to believe that the things of education are part of a mythical world only loosely related to reality.

  4. paul

    Interesting post.
    It is possible to generate a Fibonacci sequence for a 3D function ?
    I was thinking as something like:

    j/Fk(1,Fk-1,Fk-2)

    Thanks.

  5. John

    Paul, I have only seen Fibonacci points defined for 2D. For 3D, you could use a quasi-random sequence such as the Sobol sequence. Numerical Recipes has a description of these sequences.

  7. jerryk

    I’ve seen the golden ratio used in a virtual machine’s garbage collection code before… for no discernible reason other than nerdery, I’d expect that 3/2 would have yielded no meaningfully different behavior.

  9. msk2

    Fibonacci 71 by your method gives 308061521170130 and the actual value is one less than this. For less than 71, your method beats traditional method in python (2.7.6)
    Here is my python code
    def method2(n):
    return int(math.pow(0.5*(1+math.sqrt(5.0)), n)/math.sqrt(5.0)+0.5)

    Did I do something wrong?

Comments are closed.