My problem is to use the fprintf command to print out the first N Fibonacci numbers in a two-column table under heading N and F_N. And for the case N >= 50, print out the last 10 Fibonacci numbers F_i for i = N – 9 in a similar two-column table.
MATLAB: Fibonacci number without any loops
fibonacci number
Related Solutions
And, why are you surprised that it fails? :)
I go into a fair amount of detail on this in my Fibonacci submission on the File Exchange. But the gist of it is that recursion is a flat out terrible way to compute Fibonacci numbers. My guess is this is why you were given that homework problem.
Lets think about what happens here. the first call, fibonacci(100), then calls itself twice, trying to compute fibonacci(99) and fibonacci(98).
No obvious problem there. But now that call to fibonacci(99) calls itself twice, trying to compute f_98 and f_97. Each successive call spawns additional calls, and in fact, many of those calls are repeated. So there are two calls to get f_98, 3 times when it will evaluate f_97. Think of those recursive calls as a tree, with many branches that intertwine, crossing. But the problem is, fibonacci does not know that it has, someplace else in the tree, needed the value of a given fibonacci number.
How many calls are there? Here are the number of calls for each specific fibonacci number in that tree. See if you recognize the pattern:
f_100 - 1f_99 - 1f_98 - 2f_97 - 3f_96 - 5f_95 - 8f_94 - 13...Interesting. So the number of calls actually grows exactly as does the fibonacci sequence, but backwards. How many calls will there be for fibonacci(1)?
I can compute this, because I'm using my own code for Fibonacci numbers, that is quite efficient. As well, my own code uses my vpi tools, so the value given is exact.
fibonacci(100)ans = 354224848179261915075DON'T TRY THAT WITH YOUR OWN CODE! My version uses a O(log(n)) scheme to compute the nth Fibonacci number.
And that is just the number of times that fibonacci(1) will be evaluated by your recursive code, so roughly 3e20 recursive calls!
vpi2english(fibonacci(100))ans =three hundred fifty four quintillion, two hundred twenty four quadrillion, eight hundred forty eight trillion, one hundred seventy nine billion, two hundred sixty one million, nine hundred fifteen thousand, seventy fiveThat is one big number. But the total number of recursive calls is even worse.
sum(fibonacci(1:100))ans = 927372692193078999175Yes, that is 927 quintillion calls (with a few to spare.)
So there are good ways to compute large Fibonacci numbers, and there are obscenely bad ways. Straight recursion (as you have) is an example of an obscenely bad way. Again, my guess is this assignment was given to make a point.
Again, there are good ways to do that computation.
fibonacci(10000)ans = 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875timeit(@() fibonacci(10000))ans = 0.027053912189So 0.027 seconds using the O(log(n)) scheme, and it is exact, down to the last digit. Had I tried to use the basic recursive scheme on this number, it would have brought the world's largest supercomputer to its knees, for the life of the universe. Sometimes the algorithm you use matters. A lot.
He, he, he. Rolls Royce? Yes, it probably is.
But for this problem, I'd make use of good old Binet and his formulaic legacy, at least for a start.
If phi is the golden ratio, then we have
phi = (1 + sqrt(5))/2;F = @(n) (phi^n - (-phi)^(-n))/sqrt(5);For example, the 12th Fibonacci number is:
F(12)ans = 144It is not truly exact, at least not in terms of floating point numbers. But we need to learn to know when to trust a number to be an integer or not. This is an essential part of computing.
F(12) - 144ans = 5.6843418860808e-14I can verify that 144 value using my Rolls Royce engine.
fibonacci(12)ans = 144Note that for n reasonably large, we get a very good approximation by ignoring the second term in that formula. For example...
format long gphi^12/sqrt(5)ans = 144.001388875493So a good approximation for the largest Fibonacci number that does not exceed some value k will be simply obtained by taking the log of that expression, and solving for n.
n_k = @(k) floor(log(k*sqrt(5))/log(phi));n_k(145)ans = 12n_k(143)ans = 11For larger values of k, say 10^23,
n_k(1e23)ans = 111fibonacci(111)ans = 70492524767089125814114fibonacci(112)ans = 114059301025943970552219You will find that the formula works quite well even for small k.
Best Answer