Fibonacci number

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.

        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

        / 1 + sqrt(5) \ n
F(n) = |  -----------  |   / sqrt(5)
        \      2      /

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:

a_n=((1+√(5))/2)ⁿ-((1-√(5))/2)ⁿ

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:

a_n=a_n-1+a_n-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:

Zⁿ=Z^n-1+Z^n-2
Zⁿ-Z^n-1-Z^n-2=0
Z^n-2*(Z²-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:

a_n=c₁((1+√(5))/2)ⁿ + c₂((1-√(5))/2)ⁿ

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

Introduction

Fibonacci numbers may be used as an approximation to convert between miles and kilometers. Like the log tables of old, this is a great method if your multiplication is poor, but you want a more accurate value than you would reach by the super-simple method of multiplication or division by a factor of 1.5

Method

Add up your distance in terms of Fibonacci numbers.

eg. 100 = 89+8+3

Now to convert miles to km, take each of your numbers and convert it to the subsequent number in the sequence, and add these up:

100 miles (89+8+3) -> (144+13+5) = 162 km

To convert the km to miles, add up the preceding set of numbers:

100 km (89+8+3) -> (55+5+2) = 62 miles

Handle the 1īs however you like, it is only an approximation after all.

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

$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++;
}

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;
  }
}

[0 1]^n    [fib(n - 2) fib(n - 1)]
[1 1]   =  [fib(n - 1) fib(n)    ]

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;
  }
}

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