Be the first to rate this file! 147 downloads (last 30 days) File Size: 114.76 KB File ID: #24022

Fibonacci and Lucas numbers

07 May 2009

A variety of methods are compared for the computation of Fibonacci and Lucas numbers

File Information
Description	A quick search on the file exchange reveals many examples of how to compute Fibonacci numbers. IMHO, most are rather poor. They are either brutishly recursive, or use Binet's formula, or use simple loops. All of these methods have serious limits. So, when I decided to write a Fibonacci/Lucas number code for my own vpi tools, I decided to also write up my thoughts as I did so in a MATLAB "published" form. This submission shows many different ways to compute Fibonacci and Lucas numbers, the good, the bad, and the just plain ugly. The end result is the fibonacci.m file, now found in my vpi toolbox. This function is non-recursive and quite efficient. tic [Fn,Ln] = fibonacci(1000); toc Elapsed time is 0.089860 seconds. Fn = 43466557686937456435688527675040625802564660517371780402 48172908953655541794905189040387984007925516929592259308 03226347752096896232398733224711616429964409065331879382 98969649928516003704476137795166849228875 Ln = 97194177735908175207981982079326473737797879155345685082 72808108477251881844481526908061914904596829767957830540 32093474011630369076605739717408624637518016412014902840 97309096322681531675707666695323797578127 I've included the source code for all the functions described. Best is simply to open the fibonacciEvolution.html file in your browser. For those who wish to play more extensively with these tools, I would recommend that you download the most recent release of my vpi toolbox. (Writing this submission helped me to find a few enhancements to make all computations run more quickly in this recent release.) http://www.mathworks.com/matlabcentral/fileexchange/22725
Acknowledgements	The author wishes to acknowledge the following in the creation of this submission: Fibonacci.m, Lucas.m, FIBONACCI, Fibonacci Number Generator, Fibonacci, Variable Precision Integer Arithmetic
MATLAB release	MATLAB 7.5 (R2007b)
Other requirements	This uses my vpi toolbox for all computations.
Zip File Content
Published M Files	fibonacciEvolution
Other Files	FibonacciSequence/fibonacci.m, FibonacciSequence/fibonacciEvolution.m, FibonacciSequence/fibonacciEvolution.m~, FibonacciSequence/fibrecur.m, FibonacciSequence/fibrecurmemo.m, FibonacciSequence/fibs1.m, FibonacciSequence/fibs2.m, FibonacciSequence/fibs3.m, FibonacciSequence/html/fibonacciEvolution.png, FibonacciSequence/html/fibonacciEvolution_01.png, FibonacciSequence/html/fibonacciEvolution_02.png, FibonacciSequence/html/fibonacciEvolution_03.png, FibonacciSequence/html/fibonacciEvolution_04.png, FibonacciSequence/html/fibonacciEvolution_eq10728.png, FibonacciSequence/html/fibonacciEvolution_eq13042.png, FibonacciSequence/html/fibonacciEvolution_eq15684.png, FibonacciSequence/html/fibonacciEvolution_eq16838.png, FibonacciSequence/html/fibonacciEvolution_eq177592.png, FibonacciSequence/html/fibonacciEvolution_eq18225.png, FibonacciSequence/html/fibonacciEvolution_eq19980.png, FibonacciSequence/html/fibonacciEvolution_eq19981.png, FibonacciSequence/html/fibonacciEvolution_eq22694.png, FibonacciSequence/html/fibonacciEvolution_eq22727.png, FibonacciSequence/html/fibonacciEvolution_eq234886.png, FibonacciSequence/html/fibonacciEvolution_eq4510.png, FibonacciSequence/html/fibonacciEvolution_eq6302.png, FibonacciSequence/html/fibonacciEvolution_eq73732.png, FibonacciSequence/html/fibonacciEvolution_eq9194.png, FibonacciSequence/html/fibonacciEvolution_eq9212.png, FibonacciSequence/html/fibonacciEvolution_eq9338.png, license.txt

Tags for This File
Everyone's Tags	fibonacci, lucas, memoization, numbers, recurrence, recursion, vpi
Tags I've Applied
Add New Tags	Please login to tag files.

Please login to add a comment or rating.

Tag Activity for this File
Tag	Applied By	Date/Time
fibonacci	John D'Errico	07 May 2009 13:41:15
lucas	John D'Errico	07 May 2009 13:41:15
numbers	John D'Errico	07 May 2009 13:41:15
recursion	John D'Errico	07 May 2009 13:41:15
recurrence	John D'Errico	07 May 2009 13:41:15
memoization	John D'Errico	07 May 2009 13:41:15
vpi	John D'Errico	07 May 2009 13:41:15

MATLAB Central Terms of Use

NOTICE: Any content you submit to MATLAB Central, including personal information, is not subject to the protections which may be afforded information collected under other sections of The MathWorks, Inc. Web site. You are entirely responsible for all content that you upload, post, e-mail, transmit or otherwise make available via MATLAB Central. The MathWorks does not control the content posted by visitors to MATLAB Central and, does not guarantee the accuracy, integrity, or quality of such content. Under no circumstances will The MathWorks be liable in any way for any content not authored by The MathWorks, or any loss or damage of any kind incurred as a result of the use of any content posted, e-mailed, transmitted or otherwise made available via MATLAB Central. Read the complete Terms prior to use.