Home  |  About Us  |  Link To Us  |  FAQ  |  Contact

# The Fibonacci Sequence 1.0

Date Added: May 27, 2013  |  Visits: 191

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);tocElapsed time is 0.013347 seconds.These are big numbers, each having over 200 decimal digits.>> FF = 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875>> LL = 97194177735908175207981982079326473737797879155345685082728081084772518818444815269080619149045968297679578305403209347401163036907660573971740862463751801641201490284097309096322681531675707666695323797578127

 Requirements: No special requirements Platforms: Matlab Keyword: Achieve,  Identities,  Introduced,  Large,  Lower,  Order,  Rapidly,  Sequence Users rating: 0/10