FIBONACCI

[Xlambda]

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)))

=LAMBDA(n,IF(n<3,1,FIBBONACCI(n-1)+FIBONACCI(n-2)))

LAMBDA 6.0.xlsx
	A	B	C	D	E	F	G	H
1	FIBONACCI		recursive	ckeck(non recursive)
2		n value	=FIBONACCI(B3)	=FIB(B3)	time(can use phone's stopwatch)
3		15	610	610	instant
4		18	2584	2584	instant
5		20	6765	6765	instant
6		30	832040	832040	1s
7		35	9227465	9227465	?s	share this
8		38	39088169	39088169	?s	values
9		40	102334155	102334155	?s	with us ?
10
FIBONACCI post

Cell Formulas
Range	Formula
C2:D2	C2	=FORMULATEXT(C3)
C3:C9	C3	=FIBONACCI(B3)
D3:D9	D3	=FIB(B3)

 

[Xlambda]

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.?

 

[Xlambda]

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.?

 

[GeertD]

I have a laptop with an i9-9900K with 64GB of RAM.
BTW: Fibonacci(50) would be brutal!
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).

 

[Xlambda]

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.

 

[GeertD]

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...

 

[Eric W]

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.

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

or

=LET(phi,(SQRT(5)+1)/2,n,A1,((phi^n)-(-phi^-n))/SQRT(5))

 

[tboulden]

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.

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

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

FIB

=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
	A	B	C	D	E
1				Seconds
2	n	Lookup	FIBONACCI (Tree)	TimeIt	Stopwatch
3	10	55	55	0.00
4	20	6,765	6,765	0.01
5	30	832,040	832,040	1.58	3.62
6	31	1,346,269	1,346,269	2.56	6.44
7	32	2,178,309	2,178,309	4.17	8.80
8	33	3,524,578	3,524,578	10.00	17.00
9	34	5,702,887	5,702,887	17.00	34.60
10	35	9,227,465	9,227,465	26.51	53.89
11	36	14,930,352	14,930,352	40.82	81.98
12	37	24,157,817	24,157,817	66.84	135.11
13	38	39,088,169	39,088,169	112.12	225.99
14
15	n	Lookup	FIB (Bottom-up)	TimeIt
16	10	55	55	0.00
17	20	6,765	6,765	0.00
18	30	832,040	832,040	0.00
19	40	102,334,155	102,334,155	0.00
20	50	12,586,269,025	12,586,269,025	0.00
21	60	1,548,008,755,920	1,548,008,755,920	0.00
22	70	190,392,490,709,135	190,392,490,709,135	0.00
23	73	806,515,533,049,393	806,515,533,049,393	0.00
24	74	1304969544928657	1,304,969,544,928,660	0.00
25
26	n	Lookup	FIB_Large (Bottom-up)
27	10	55	55
28	20	6,765	6765
29	30	832,040	832040
30	40	102,334,155	102334155
31	50	12,586,269,025	12586269025
32	60	1,548,008,755,920	1548008755920
33	70	190,392,490,709,135	190392490709135
34	80	23416728348467685	23416728348467685
35	90	2880067194370816120	2880067194370816120
36	100	354224848179261915075	354224848179261915075
37	164	8404037832974134882743767626780173	8404037832974134882743767626780173
38	165	13598018856492162040239554477268290	#NUM!
Scratch

Cell Formulas
Range	Formula
C3:D3	C3	=TimeIt(FIBONACCI,A3)
B16:B24	B16	=XLOOKUP($A16,$G$3#,$H$3:$H$1003,"",0)
C16:D24	C16	=TimeIt3(FIB,A16,,)
C27:C38	C27	=FIB_Large(A27,,)
Dynamic array formulas.

 

[Xlambda]

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!!?✌

 

[tboulden]

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_)

 

[Xlambda]

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!! ✌✌?