FIBONACCI

Xlambda · Mar 24, 2021

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

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

instant

4

18

2584

instant

5

20

6765

instant

6

30

832040

1s

7

35

9227465

?s

share this

8

38

39088169

?s

values

9

40

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 · Mar 24, 2021

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 · Mar 24, 2021

GeertD said:
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 · Mar 25, 2021

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 · Mar 25, 2021

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 · Mar 25, 2021

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 · Mar 25, 2021

GeertD said:
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))

tboulden · Mar 25, 2021

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

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

A

B

C

D

E

1

Seconds

2

n

Lookup

FIBONACCI (Tree)

TimeIt

Stopwatch

3

10

55

0.00

4

20

6,765

0.01

5

30

832,040

1.58

3.62

6

31

1,346,269

2.56

6.44

7

32

2,178,309

4.17

8.80

8

33

3,524,578

10.00

17.00

9

34

5,702,887

17.00

34.60

10

35

9,227,465

26.51

53.89

11

36

14,930,352

40.82

81.98

12

37

24,157,817

66.84

135.11

13

38

39,088,169

112.12

225.99

14

15

n

Lookup

FIB (Bottom-up)

TimeIt

16

10

55

0.00

17

20

6,765

0.00

18

30

832,040

0.00

19

40

102,334,155

0.00

20

50

12,586,269,025

0.00

21

60

1,548,008,755,920

0.00

22

70

190,392,490,709,135

0.00

23

73

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

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

35

90

2880067194370816120

36

100

354224848179261915075

37

164

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 · Mar 26, 2021

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 · Mar 26, 2021

Xlambda said:
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}

Xlambda said:
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.

Xlambda said:
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).

Xlambda said:
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 · Mar 26, 2021

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

FIBONACCI

Xlambda

Well-known Member

Xlambda

Well-known Member

Xlambda

Well-known Member

GeertD

Board Regular

Xlambda

Well-known Member

GeertD

Board Regular

Eric W

MrExcel MVP

tboulden

Board Regular

Xlambda

Well-known Member

tboulden

Board Regular

Xlambda

Well-known Member

Forum statistics

Share this page

FIBONACCI

Well-known Member

Well-known Member

Well-known Member

Board Regular

Well-known Member

Board Regular

MrExcel MVP

Board Regular

Well-known Member

Board Regular

Well-known Member

Forum statistics

Share this page

We've detected that you are using an adblocker.

Which adblocker are you using?

Disable AdBlock

Disable AdBlock Plus

Disable uBlock Origin

Disable uBlock