FIBONACCI

=FIBONACCI(n)

n
integer, the nth term of the sequence

calculates the nth term of a Fibonacci sequence

Xlambda

Well-known Member
Joined
Mar 8, 2021
Messages
837
Office Version
  1. 365
Platform
  1. Windows
FIBONACCI !! recursive !! calculates the nth term of the famous Fibonacci sequence . This is more of a fun quest than a useful function. ( did this on a YT channel also, had fun with Rico about this).
This reflects how limited our computers are. You will be surprised. This time is not about recursion "iterations" limit, is about the limit of the number of calculations that a computer can perform.
Open a new workbook, define the lambda FIBONACCI. Very important, first, try values of n less then 20!! . Call FIBONACC(15) ...(19) ..etc. and increase it bit by bit.
For what number "n" do you think that your computer will start struggling giving you the answer?? Share with us here, if you please, how long it took your computer to calculate FIBONACCI(35)..(38) and (40). Eventually what type of computer you are using. Processor ,RAM etc. After all, 40 is a very small number.? Give it a try!!
Note: Fibonacci sequence is this one : 1,1,2,3,5,8,13,21,34,55,89,144....the value of n term is the sum of the previous 2 terms fib( n)=fib(n-1) + fib(n-2), and fib(1)=1,fib(2)=1
Fortunately , Fibonacci has also an explicit solution (non recursive), you can define another lambda to check the results FIB( n)=LAMBDA( n,LET(a,SQRT(5),x,((1+a)/2)^n,y,((1-a)/2)^n,1/a*(x-y)))
Excel Formula:
=LAMBDA(n,IF(n<3,1,FIBBONACCI(n-1)+FIBONACCI(n-2)))
LAMBDA 6.0.xlsx
ABCDEFGH
1FIBONACCIrecursiveckeck(non recursive)
2n value=FIBONACCI(B3)=FIB(B3)time(can use phone's stopwatch)
315610610instant
41825842584instant
52067656765instant
6308320408320401s
73592274659227465?sshare this
8383908816939088169?svalues
940102334155102334155?swith us ?
10
FIBONACCI post
Cell Formulas
RangeFormula
C2:D2C2=FORMULATEXT(C3)
C3:C9C3=FIBONACCI(B3)
D3:D9D3=FIB(B3)
 
Upvote 0
Super cool that you tried?✌✌
Mines are: (used a stopwatch, approximations are accepted)
F(35): 8.23s
F(38): 44.86s
F(40) : 2m 4.29s so 124,29s

I have a Surface Book 3 i7 10th gen 32GB RAM
It will be interesting to find someone who has the new i9 11th gen intel processors or someone with a Mac with the new Apple M1 chips. What timing they will get.
Imagine everybody in a computer shop asking the salesperson, how fast this computer does FIBONACCI(50) ?? ?
If we get enough data we will see if there is correlations between CPU power or RAM, will do a chart in excel to analize.?

surface book 3.png
 
Hi Cesar,
Sorry, if I scared everybody off. It was intended as a bit of a funny remark, hence the wink ;).
Anyway, here are some calculation times for my computer:
  • F(35) => 8.5 à 8.7 seconds
  • F(40) => 106 à 108 seconds
I used the FastExcel V4 Calculation Manager for timing this.
I don't think the CPU, RAM, etc. is all that important, because my PC used less than 1 core for this and far less memory than is present in any modern computer.
I think my computer did average.

What about yours?
Super cool that you tried?✌✌
Mines are: (used a stopwatch, approximations are accepted)
F(35): 8.23s
F(38): 44.86s
F(40) : 2m 4.29s so 124,29s

I have a Surface Book 3 i7 10th gen 32GB RAM
It will be interesting to find someone who has the new i9 11th gen intel processors or someone with a Mac with the new Apple M1 chips. What timing they will get.
Imagine everybody in a computer shop asking the salesperson, how fast this computer does FIBONACCI(50) ?? ?
If we get enough data we will see if there is correlations between CPU power or RAM, will do a chart in excel to analize.?

surface book 3.png
 
I have a laptop with an i9-9900K with 64GB of RAM.
BTW: Fibonacci(50) would be brutal! :biggrin:
Like I said before: the CPU was not used 100% during calculation. Therefore this is not representative for the overall performance (monitor your Task Manager).
 
wow , gaming laptop? that's way you do not have enough time for writing formulas.??
if the computers have same architecture it does not matter if they use 1% or 120%. The proportion is kept. The purpose was not to diagnose CPU's , was to find correlations, with enough sample data.
Your laptop did better for f(40) and is more powerful, my desktops, less or more powerful than my Surface, act accordingly . So correlations are.
You made also 2 statements:
  • "don't use this kind of recursive formula's."
Recursive formulas are brilliant smart, simple, powerful and elegant. If we don't have enough power to handle them , is not the recursive's algorithms fault, it's our problem that we are not powerul enough for them. Keep the formula, always, and improve the power. We don't have the power, we don't deserve them. Everything that is inteligent around us is based on recursive algorithms.
If I can find a recursive pattern in anything I will reveal it , no matter if we can not use it today or not, we will use it tomorow. The power will come.
The second statement is purely hilarious ?
  • "recursive formula's that call themselves only once should be fine."
I want to print it on T-shirts if you give me the rights. Sounds like a Woody Allen quote.?
Somehow this triggered another quote that came to my mind (recursively) "If you are lonely when you're alone, you are in bad company." I think it was Jean Paul Sartre.?
It was fun, like always, see you around. ✌. Too much work on pending.
 
Hey Cesar,
Hardware:
  • I bought my current laptop on Black Friday 2019 to save me some money, so it's fairly recent.
  • I always buy a high-end model so it lasts me as long as possible (I don't have a desktop).
  • I haven't gamed in a long time (10+ years) – I have a fulltime job that takes up most of my time.
  • But I guess it would be more than adequate for gaming.
  • (Just not so much for calculating recursive LAMBDA Fibonacci numbers ;))
Recursive formulas:
  • Don't get me wrong: recursive formulas are great, and useful.
  • It's just that one has to be careful how to treat and calculate them: if a recursive formula calls itself more than once (per recursive iteration, that is): don't use the "recursive LAMBDA"-approach; there are far better methods, even recursive ones.
  • BTW: did you know that every discrete recursive equation with constant coefficients has a closed-form analytic solution?
    • Fibonacci is one example for this, but there are infinitely many more. :)
    • There are several ways of analytically solving equations like these; using the Z-transform is one of them.
  • In conclusion: computers can be powerful, math can be much more powerful, stil.
    • imagine if you'd combine them both!
    • for all we know, we could even play life-like games in real-time on them... ;)
 
BTW: did you know that every discrete recursive equation with constant coefficients has a closed-form analytic solution?
  • Fibonacci is one example for this, but there are infinitely many more. :)

Excel Formula:
=((((SQRT(5)+1)/2)^A1)-(-((SQRT(5)+1)/2)^-A1))/SQRT(5)

or

Excel Formula:
=LET(phi,(SQRT(5)+1)/2,n,A1,((phi^n)-(-phi^-n))/SQRT(5))
 
Thought I'd be clever and make a TimeIt function, but still had to use a stopwatch because of the behind-the-scenes house-cleaning that Excel does between function calculation completion and when it is finally loaded to the sheet: 2x function calc time! Any ideas about what's eating up this "extra" time? Running on my sad "old" desktop, nothing special about it.
1616720767480.png


Since the posted function ends up creating a tree structure, there's a lot of covering the same territory, but in branches of the tree that can't see one another, so inefficient as @GeertD points out above. FIB below uses a bottom-up approach, so doesn't do a lot of needless calculation; much faster such that TimeIt wasn't often more that 0.01 seconds.

Also created FIB_Large using FIB and Mourad Louha's Large Number LAMBDAs; Excel runs out of precision once you get to FIB(73), but can extend FIB_Large(164) when we run out of stack depth.

TimeIt
Excel Formula:
=LAMBDA(func,param,
    LET(
        begin,NOW(),
        result,func(param),
        end,NOW(),
        elapsed,end-begin,
        CHOOSE({1,2},result,elapsed*86400)
    )
)

FIB
Excel Formula:
=LAMBDA(n,a,b,
    LET(
        a_,IF(ISBLANK(a),0,a),
        b_,IF(ISBLANK(b),1,b),
        IF(
            n=0,a_,
            FIB(n-1,b_,a_+b_)
        )
    )
)

LAMBDA_Testing_Mourad_Louha.xlsm
ABCDE
1Seconds
2nLookupFIBONACCI (Tree)TimeItStopwatch
31055550.00
4206,7656,7650.01
530832,040832,0401.583.62
6311,346,2691,346,2692.566.44
7322,178,3092,178,3094.178.80
8333,524,5783,524,57810.0017.00
9345,702,8875,702,88717.0034.60
10359,227,4659,227,46526.5153.89
113614,930,35214,930,35240.8281.98
123724,157,81724,157,81766.84135.11
133839,088,16939,088,169112.12225.99
14
15nLookupFIB (Bottom-up)TimeIt
161055550.00
17206,7656,7650.00
1830832,040832,0400.00
1940102,334,155102,334,1550.00
205012,586,269,02512,586,269,0250.00
21601,548,008,755,9201,548,008,755,9200.00
2270190,392,490,709,135190,392,490,709,1350.00
2373806,515,533,049,393806,515,533,049,3930.00
247413049695449286571,304,969,544,928,6600.00
25
26nLookupFIB_Large (Bottom-up)
27105555
28206,7656765
2930832,040832040
3040102,334,155102334155
315012,586,269,02512586269025
32601,548,008,755,9201548008755920
3370190,392,490,709,135190392490709135
34802341672834846768523416728348467685
359028800671943708161202880067194370816120
36100354224848179261915075354224848179261915075
3716484040378329741348827437676267801738404037832974134882743767626780173
3816513598018856492162040239554477268290#NUM!
Scratch
Cell Formulas
RangeFormula
C3:D3C3=TimeIt(FIBONACCI,A3)
B16:B24B16=XLOOKUP($A16,$G$3#,$H$3:$H$1003,"",0)
C16:D24C16=TimeIt3(FIB,A16,,)
C27:C38C27=FIB_Large(A27,,)
Dynamic array formulas.
 
Hi, tboulden, great study!! Thanks that you took the quest. ✌✌. You choose the iteration way which is more "efficient". It will be interesting to do the same , on your computer , with this also
=LAMBDA(n,IF(n<3,1,FIBBONACCI(n-1)+FIBONACCI(n-2))) (less "efficient") to compare the timing results on a same computer.
My purpose of this quest , as I wrote in the description , was not a way to solve fib in real life, was exactly to reveal how a simple formula, in its most beautiful, simple and inofensive form , can make our self proclaimed powerful computers struggle. " This is more of a fun quest than a useful function. " "This reflects how limited our computers are. "
My approach is a tiny bit different , in a philosophical way , the formula is not inefficient , WE are. The formula is THE formula. Is how nature thrives, is how evolution works, is how our brain functions. Anybody figured out so far that I like recursion. Of course, I can find ways avoiding the "ineficient" over stacking recursion problems , (that Geert call it recursion in recursion something ?) doing everything explicit and people to think , this guy is efficient. I don't care. If excel is giving me #NUM error , excel has to improve, not me. 200 iterations, in 21 century? Come on. They have to catch up, and they will. Thats way probably we realised that we have to go quantic. In real life I do take care of "efficiency" ,no complains there, but here, let me feel free , this forum I see it like a canvas where we can create , push the limits, nobody will stop me of thinking recursive pointing: is no good, I got a num error.
A pleasure to interact with you (you know to write formulas) I bow!!?✌
 
It will be interesting to do the same , on your computer , with this also =LAMBDA(n,IF(n<3,1,FIBBONACCI(n-1)+FIBONACCI(n-2))) (less "efficient") to compare the timing results on a same computer.
That's exactly what happens in C3:D13; TimeIt just wraps the function being timed, in this case =TimeIt(FIBONACCI,n) ={FIBONACCI(_n_),Seconds to calculate}

My purpose of this quest , as I wrote in the description , was not a way to solve fib in real life, was exactly to reveal how a simple formula, in its most beautiful, simple and inofensive form , can make our self proclaimed powerful computers struggle. " This is more of a fun quest than a useful function. " "This reflects how limited our computers are. "
Yes, and I wanted to find a different limitation as the fun ended for me when I had to wait for FIBONACCI(35) to run. :) There was no hope of me finding the last accurate FIBONACCI calc that Excel could make because it would take all day if it even completed! So I switched to FIB/bottom-up approach, and found FIB(73) was the last accurate result so implemented FIB_Large. And likewise, I won't be able to find the stack-depth limitation of FIBONACCI due to calc times, so can use FIB_Large to find both accurate results and the max value of N before stack depth is exhausted.
My approach is a tiny bit different , in a philosophical way , the formula is not inefficient , WE are. The formula is THE formula. Is how nature thrives
I would argue that F(_n_) = F(n-1) + F(n-2) is NOT how nature thrives in this case; even using Fibonacci's original unrealistic example of rabbit population, you start from small population and increase :) The bottom-up approach is recursive, but perhaps not as interesting/etc. And we can create a version that performs the same calculation, but populates a helper array for everything less than n-1 the first time we call F(n-1).
If excel is giving me #NUM error , excel has to improve, not me. 200 iterations, in 21 century? Come on. They have to catch up, and they will.
I imagine Microsoft will improve the stack depth limitations, but that's a different issue than resources needed to complete a computation. As mentioned above, using FIBONACCI doesn't run into stack-depth issue, it bogs down due to resource usage. This link is good, I think, to better communicate what I mean perhaps.

* edited for issues with (n) => (_n_)
 
Uf, sorry to "trap" your computer. ? Quod erat demonstrandum !
Let's see if someone with the new M1 MacBook can share some results with us.
See you around guys, thanks for participation and have fun!! ✌✌?
 

Forum statistics

Threads
1,216,503
Messages
6,131,022
Members
449,616
Latest member
PsychoCube

We've detected that you are using an adblocker.

We have a great community of people providing Excel help here, but the hosting costs are enormous. You can help keep this site running by allowing ads on MrExcel.com.
Allow Ads at MrExcel

Which adblocker are you using?

Disable AdBlock

Follow these easy steps to disable AdBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the icon in the browser’s toolbar.
2)Click on the "Pause on this site" option.
Go back

Disable AdBlock Plus

Follow these easy steps to disable AdBlock Plus

1)Click on the icon in the browser’s toolbar.
2)Click on the toggle to disable it for "mrexcel.com".
Go back

Disable uBlock Origin

Follow these easy steps to disable uBlock Origin

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back

Disable uBlock

Follow these easy steps to disable uBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back
Back
Top