Mathematical series of numbers where each entry is derived by adding the previous two:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377 ... etc.

Apparently, the series appears all over the place in nature.

Hi. Here's two simple c++ algorithms that calculate the first 100 fibonacci numbers. Sorry they're not more versatile, I just started learning to code last week (Sept 2000). The difference is that one returns two terms per cycle, while the other only returns one... I personally prefer the double-return, I think it's prettier.

One advantage of the algorithm that returns two is that it can easily be used to illustrate the limit of t(n)/t(n-1) as n approaches infinity... this expression converges to a fixed value, sometimes called the golden ratio.

Update: (November 22nd) I added a new algorithm to generate the sequence recursively. This is less efficient, but it's a nice looking, extremely small solution. (See Bottom.)

Oh yeah, here's the code:

        Double Generator Algoritm:
        int t1 = 0, t2 = 1;
	for (int counter = 0; counter < 50; counter++)
	{
	   cout << t1 << endl << t2 << endl;
	   t1 += t2; t2 += t1;
	}

         Single Generator Algoritm:
	int t = 0, temp1 = 1, temp2 = 1;
	for (int counter = 0; counter < 50; counter++)
	{
	   cout << t << endl;

	   temp1 = temp2;
	   temp2 = t;
	   t = temp1 + temp2;
	}

         Recursive Algoritm:
         This function returns the nth fibonacci number.  
         int f(int &n)
         {
           if ((n == 2) || (n == 1))
	     return(1);
           else
	     return(f(n-1) + f(n-2));
         }

The n-th Fibonacci number can be calculated without recursion with a simple assembly language routine (nasm syntax), callable by C programs, as:

unsigned int fibonacci(unsigned int n);

It works both with C compilers that prepend each function name with an underscore, and those that do not. Like the rest of algorithms presented here, it does not check for overflow. Here it is:

global  _fibonacci, fibonacci
_fibonacci:
fibonacci:
    sub     eax, eax         ; eax = 0
    mov     ecx, [esp+4]     ; ecx = n
    sub     edx, edx
    jecxz   .done            ; return 0 if n == 0
    inc     dl               ; edx = 1

.loop:
    push    eax
    add     eax, edx
    pop     edx
    loop    .loop

.done:
    ret

You can also create a program to calculate Fibonacci Numbers in Python, and it's smaller than most other examples:

x = int(raw_input("Go until?"))

a, b = 0, 1
while b < x
print b
a, b = b, a+b
In combinatorics, Fibonacci numbers are a sequence of numbers defined by the recurrence relation F(n) = F(n-1) + F(n-2) and the initial values F(0)=1 and F(1)=1. The Fibonacci numbers are supposed to give the number of pairs of rabbits in an enclosure n months after a breeding pair is placed in it, if newly born pairs of rabbits begin breeding themselves in their second month.

--back to combinatorics--
The Nth number in the Fibonacci sequence can be found approximately by this formula:
        / 1 + sqrt(5) \ n
F(n) = |  -----------  |   / sqrt(5)
        \      2      /
The nearest integer is the Nth Fibonacci number.
Notice that the bracketted expression (1 + sqrt(5)) / 2 is the golden ratio.

In code (BASIC, at least), that would be: Fn = int( ( ( ( 1 + sqrt(5) ) / 2 ) ^ n ) / sqrt(5) + 0.5 )

For more of this kind of thing, point your browser at
http://www.maa.org/devlin/devlin_3_99.html

SpudTater's formula for approximating the nth Fibonacci number is actually related to a larger formula which calculates the nth number exactly. The formula is:

an=((1+√(5))/2)n-((1-√(5))/2)n

Now the fun part. Why does this work? The reason is that this is the solution to the difference equation defined by the Fibonacci sequence. The Fibonacci sequence is:

an=an-1+an-2

We can form this into a polynomial in Z, where the power of Z is the term in the sequence represented by a, like this:

Zn=Zn-1+Zn-2
Zn-Zn-1-Zn-2=0
Zn-2*(Z2-Z-1)=0

The roots of this equation are 0, ((1+√(5))/2) and (1-√(5))/2). (We can obtain these by using the quadratic formula.) We ignore the trivial root 0, and using the remaining roots we can create the function:

an=c1((1+√(5))/2)n + c2((1-√(5))/2)n

Finally we solve for the constants c1 and c2 by using known values of an (in particular, when n=0 and n=1). We find c1=1 and c2=-1. From this, we get the formula above. Pretty nifty, eh?

The formula JyZude mentions is referred to as Binet's Formula for calculating the nth Fibonacci number. Of the two references I've read which skimmed across this subject, both have noted that Binet probably wasn't the first to discover this formula, and found it on his own 100 years after. They differ, in that one claims de Moivre discovered it first, and the other claims Euler did. Binet, however, eventually wound up getting the credit for it.

One of the most awe inspiring things that I was ever told about Fibonacci numbers was in relation to pine cones. Take a random pine cone off the ground. (It works better if it's a big hard one (I'm in math, not biology, excuse me) Then look at the bottom. There will be 2 sets of spirals on the bottom that look somewhat like fan blades, one going to the left, the other set going to the right. Count each spiral for each direction. The 2 numbers you get will always be sequential Fibonacci numbers. My professor said he had be doing this for years, and had never found one larger than a 13,21 (first spiral had 13, second had 21) pine cone. If we found a 21,34 cone he would buy it from us, he said. Pretty interesting, no?

See logarithmic spiral for a bit of an explanation for this.

You can write a simple program in PERL to generate Fibonacci numbers.

$m=1; $k=1;
print "Find the first how many #s: ";
$x=<stdin>;
$y=3;
print "0, ", "1, 1, ";
until ($y>$x) {
    $n=($k+$m);
    print $n, ", ";
    $k=$m; $m=$n; $y++;
}

Most algorithms I have seen that calculate the n:th fibonacci number do so in O(n) time. There is however a way to do it in O(lg n) time. The algorithm makes use of the fact that it is possible to calculate 'i to the power of n' in O(lg n) time this way:

int Pow(i, n)
{
  if (n == 0)
    return 1;
  else
  {
    int r = Pow(i, n / 2);  // assumes integer division
    r = r * r;
    if (n % 2 == 1)         // if n is odd we need to multiply
      r = r * i;            // r with i to get the correct result
    return r;
  }
}
The formula below shows that the powers of a certain 2x2 matrix results in another 2x2 matrix containing some usefull fibonacci numbers:
[0 1]^n    [fib(n - 2) fib(n - 1)]
[1 1]   =  [fib(n - 1) fib(n)    ]
The pseudo code below shows the full algorithm:
int Fib(int n)
{
  Matrix F = {{0, 1}, {1, 1}};
  F = Pow(F, n);
  return F[1][1]; // row 2, column 2
}

Matrix Pow(Matrix M, int n)
{
  if (n == 0)
    return {{1, 0}, {0, 1}}; // the identity matrix
  else
  {
    Matrix R = Pow(M, n / 2);
    R = R * R;
    if (n % 2 == 1)
      R = R * {{0, 1}, {1, 1}};
    return R;
  }
}

Fibonacci numbers are also found in a branch of stock market analysis called Technical Analysis.

Fibonacci fans, arcs and retracements are often used to try to predict future stock movements. For example after a stock price has moved upwards (rallied) and starts to move in the opposite direction, a Fibonacci retracement can be used to try to determine the point at which the stock price will start to turn upwards again.

It very often works too, spooky really.

Here's another interesting formula for finding fibonacci numbers, this one using only fn-1 and n:

fn = (fn-1 + sqrt(5fn-12 - 4(-1)n)/2

With f0 defined as 0.

The derivation for this is fairly straightforward.

First, it needs to be shown that fn+1fn-1 - fn2 = (-1)n for all n, without using the function above. It's easy to establish that for n=1, 1*0 - 1*1 = -1 = (-1)1. Since fn+1 = fn-1 + fn, fn+1fn-1 - fn2 is equivalent to fn-12 + fnfn-1 - fn2, which equals fn(fn-1 - fn) + fn-12. Replacing fn-1-fn with -fn-2 gives fn-12 - fnfn-2. In other words, letting g(n) = fn+1fn-1 - fn2, g(n) = -g(n-1), and so by induction on n, g(n) = (-1)n for all natural numbers n.

Since fn+1 = fn + fn-1, fn-1(fn + fn-1) - fn2 = (-1)n by the equation above. Simplifying to get everything on one side yields: fn2 - fn-1fn - fn-12 + (-1)n = 0. Using the quadratic formula on that gives the equation for fn in terms of fn-1 and n.

This formula makes the relation between the fibonacci numbers and the golden mean very apparent without actually using the golden mean at any point, which seemed pretty interesting to me when I first learned of it.

The Haskell Fibonacci program is even shorter than the Python program above.

fibonacci = 0 : 1 : [ this + next | (this, next) <- zip fibonacci (tail fibonacci) ]

Note that the list fibonacci actually contains every fibonacci number, in order. Haskell's lazy evaluation means that it won't actually generate the list until you ask for one of its elements.


jrn points out that calculating fibonacci numbers this way is slow and uses a bunch of memory. If you want to calculate fibonacci numbers in Haskell FAST, this is how you do it:

golden_ratio = (1 + (sqrt 5))/2

fibonacci_at :: Integer -> Integer
fibonacci_at n = round (golden_ratio^n/(sqrt 5))

But that's just not as cool as having an infinitely long list, is it? :)

In addition to all the math...

Fibonacci sequences (or similar ratios) are found often in nature. Pine cones, seed heads (ex: sunflower), how the leaves grow on a plant, ram's horns, seashells. It should be noted that the Fibonacci sequence is not the only sequence in nature that dictates spirals, but is one of many phyllotaxies (princibles governing leaf arrangement).

Fibonacci numbers also play a role in deriving the golden number (or the golden mean). By taking any number in the sequence and dividing it by the one before it, you get a number near Phi, the golden number, 1.618034 (the larger numbers you are working with, the closer it will be).

To artists, the golden mean is better known as the golden rectangle. (a good picture of it here: http://www.vashti.net/mceinc/GoldSqre.gif). Each rectangle has the proportions of a fibonacci number. The first square is 1x1, the second is 1x1, the third is 2x2, the fourth is 3x3, the fifth is 5x5 and so on. Luca Pacioli, in his Divina proportione (On Divine Proportion), wrote about the golden mean and his work influenced such artists as Da Vinci (see the Aunnuciation). Many art books and art professors will tell students that it is better to position the focus of a picture slightly to one side (on the one-third line).

The fibonacci sequence has been tied occassionally to buddhism and spirituality, being used to make such symbols as the Heart of Buddha (the golden heart), and the Grail Cup. The arms of the pentacle also conform to fibonacci ratios. Some believe that the reoccurance of the same pattern in many parts of nature is manifest of a divine plan. (see sacred geometry)

Some photos/pictures of the Fibonacci spiral as seen in nature:
Sea Shell:http://www.world-mysteries.com/fib_nautilus2.jpg
Daisy: http://www.math.unl.edu/~sdunbar1/Teaching/ExperimentationCR/Lessons/Fibonacci/daisy2.jpg
Rams Horns: http://incider.byu.edu/vwb/000.%20Example%20Sym/Bighorn%20Sheep72.jpg

Log in or register to write something here or to contact authors.