Code covered by the BSD License  

Highlights from
The Fibonacci Sequence

  • fibonacciEvolution
  • fibonacci(n,modulus)fibonacci: vpi tool to efficiently compute the n'th Fibonacci number and the n'th Lucas number
  • fibrecur(N)Computes the Fibonacci number, F(N), using recursion (a poor choice)
  • fibrecurmemo(N)Computes the Fibonacci number, F(N), using a memoized recursion
  • fibs(n)fibs: vpi tool to efficiently compute the n'th and (n-1)'th Fibonacci numbers
  • fibs2(n)fibs2: vpi tool to efficiently compute the n'th Fibonacci number and the n'th Lucas number
  • fibs3(n)fibs: vpi tool to efficiently compute the n'th Fibonacci number and the n'th Lucas number
  • View all files
5.0 | 1 rating Rate this file 17 Downloads (last 30 days) File Size: 400 KB File ID: #34766 Version: 1.1

The Fibonacci Sequence


John D'Errico (view profile)


25 Jan 2012 (Updated )

Efficient computation of Fibonacci and Lucas numbers

| Watch this File

File Information

Often I see students asking for help on a tool to compute the Fibonacci numbers. Or, I'll find them asking for help on a Project Euler problem. Or, a student has been assigned the problem of computing the fibonacci numbers using a recursive implementation. After all, these numbers lend themselves splendidly to teaching a student to use recursion.

The problem is that a direct, simple, recursive scheme is a poor one for the Fibonacci numbers, unless the recursion is written very carefully.

This tool teaches you how to compute the Fibonacci numbers in a variety of ways, good, bad, ugly. I teach the concept of memoization, a vitally important tool for many recursive schemes, not only for Fibonacci numbers. (If you do teach a student recursion, use it as an excuse to also teach them about memoization!)

Of course, I also employ some additional tricks to compute the n'th Fibonacci number without needing to compute every lower order number in the sequence. Some useful identities are introduced to achieve that task.

Since these numbers get very large, very rapidly, I return them in my VPI class, but don't be mistaken, these tools are indeed efficient. For example, to compute both the 1000'th Fibonacci and Lucas numbers, the time required was only 0.013 seconds.

>> tic,[F,L] = fibonacci(1000);toc
Elapsed time is 0.013347 seconds.

These are big numbers, each having over 200 decimal digits.

>> F
F =
>> L
L =


This file inspired Image Segmentation.

MATLAB release MATLAB 7.12 (R2011a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (1)
05 Oct 2013 Yair Altman

Yair Altman (view profile)

An excellent tutorial on the pitfalls of recursion, the benefits of memoization, and the importance of utilizing known mathematical identities to obviate the need to use any of them.

One small issue: I content that the fibrecurmemo() function is not typical use of memoization: In typical memoization the previous function results are cached and reused in subsequent function calls. In your implementation, the recursion is simply reimplemented to use a single recursion but the results are not cached and so every call to fibrecurmemo() would need to recompute them. Classic memoization would entail using persistent variables to store the results.

Another suggestion is to use round() when directly computing the fib values using Binet's formula. You rightfully mention the FP-precision issue and using round() is a natural simple workaround for values small-enough not to require VPI.

Still, these are only minor points in an otherwise excellent submission.

04 May 2012 1.1

Allows efficient computation of the modulus of large Fibonacci/Lucas numbers.

Contact us