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)

GeertD · Mar 26, 2021

tboulden said:

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

Your implementation of the Fibonacci formula in FIB is BRILLIANT! Really love it!
It has all the good properties of the most efficient of implementations as far as recursive formulas go:

you generalized the starting conditions with your a & b parameters,
you created a recursive function that calls itself only once, making it linear and thus super efficient to compute.
only the closed-form analytic solution formula is more efficient to compute (for large n), IMO.

And I saw what you did there, using those additional arguments so smartly.
This proves that the guy with the smartest algorithm will always beat the guy with the most powerful computer.

And the difference in performance can be "unbelievable".
Awesome!

Rick Rothstein · Mar 26, 2021

Eric W said:
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))

This formual fails at 55 (starts reporting result in E-notation meaning digits were lost). By contrast, here is a UDF (user defined function) with "infinite precision" (assuming you are willing to wait while it calculates very large numbers). The remarks refer to timing on a computer I owned probably a dozen or more years ago when running the compiled version of Visual Basic... I have no idea of timing for Excel's VBA on modern computers, but the code does work.

VBA Code:

' This is an "infinite" precision calculator which prints the full Nth
' Fibonacci number up to virtually any maximum Fibonacci Number,
' limited only to the maximum number of digits that a string can hold. Be
' aware, however, this routine slows down as the inputted number gets larger;
' for example, my fairly fast computer and it took 7.8 seconds for it to
' calculate the 2090 digits for the number 9999 and 12.6 minutes to calculate
' the 20,899 digits for the Fibonacci Number 99999, so if you plan to print
' out larger Fibonacci numbers, be forewarned it could take awhile to do so.
Function FN(ByVal N As Long) As String
  Dim X As Long, Z As Long, Carry As Long, PositionSum As Long
  Dim N_minus_0 As String, N_minus_1 As String, N_minus_2 As String
  If N = 1 Or N = 2 Then
    FN = 1
  Else
    N_minus_1 = "1"
    N_minus_2 = "1"
    For X = 3 To N
      Carry = 0
      N_minus_0 = Space$(Len(N_minus_1))
      If Len(N_minus_1) > Len(N_minus_2) Then N_minus_2 = "0" & N_minus_2
      For Z = Len(N_minus_1) To 1 Step -1
        PositionSum = Val(Mid$(N_minus_1, Z, 1)) + Val(Mid$(N_minus_2, Z, 1)) + Carry
        Mid$(N_minus_0, Z, 1) = Right$(CStr(PositionSum), 1)
        Carry = IIf(PositionSum < 10, 0, 1)
      Next
      If Carry Then N_minus_0 = "1" & N_minus_0
      N_minus_2 = N_minus_1
      N_minus_1 = N_minus_0
    Next
    FN = N_minus_0
  End If
End Function

EDIT NOTE: I am guessing that besides being able to report more total digits, my UDF is also faster then the Lambda formula as well... is that correct?

GeertD · Mar 27, 2021

Sorry, @Rick Rothstein, this is the LAMBDA section, not the VBA-section.

(just kidding!)
Yes, your compiled VBA will run faster than our interpreted LAMBDAs.
OTOH, see earlier in the thread: it is possible to have arbitrary precision using LAMBDAs, as well.
But it seems that LAMBDA will not reach the level of performance of your compiled (!) VBA any time soon.
BTW: I think arbitrary length calculations should be available in Excel by means of providing the right data type(s) and extending the functions to be able to deal with said data type(s).
That would be the cleanest solution. So, here come the most used words on the internet: "Microsoft, if you're reading this...".

tboulden · Mar 28, 2021

Still trying to fully wrap my head around it, but I looked up someone's implementation of Fibonacci using the Y-combinator and converted it to Excel LAMBDA: gets us up to F(493) before running out of stack depth when using the LNum.Sum linked previously. TimeIt values aren't bad either!

LAMBDA_Testing_Mourad_Louha.xlsm

A

B

C

D

1

2

n

Lookup

FIB_Y (Y Combinator)

TimeIt

3

10

55

0.01

4

100

354224848179261915075

0.03

5

200

280571172992510140037611932413038677189525

0.05

6

300

222232244629420445529739893461909967206666939096499764990979600

0.07

7

400

176023680645013966468226945392411250770384383304492191886725992896575345044216019675

0.12

8

488

432995556774426913953123610518785740738997352293147773391602699511793756235520810632382557083997728981

0.14

9

493

4801994309516818408452995190383973646671835537213025106017041525333156522800379742496995285687643305513

10

494

7769790006581794836315417026718114982822736329999469724305586980435409187727711750121668968517028834617

#NUM!

FIB_Y

Cell Formulas
Range	Formula
B3:B10	B3	=XLOOKUP($A3,Scratch!$G$3#,Scratch!$H$3:$H$1003,"",0)
C3:D3	C3	=TimeIt(LAMBDA(n, LET( U,LAMBDA(f,f(f)), Y,U(LAMBDA(h,LAMBDA(f,f(LAMBDA(x,h(h)(f)(x)))))), loop,Y(LAMBDA(recur,LAMBDA(a,LAMBDA(b,LAMBDA(m,IF(m=0,a,recur(LNum.Sum(a,b,))(a)(m-1))))))), loop(0)(1)(n) ) ),A3)
C4:D8	C4	=TimeIt(FIB_Y,A4)
C9:C10	C9	=FIB_Y(A9)
Dynamic array formulas.

Eric W · Mar 28, 2021

Rick Rothstein said:
This formual fails at 55 (starts reporting result in E-notation meaning digits were lost).

True enough Rick, but my main purpose for presenting it was to show the closed form formula for the Fibonacci sequence for the curious. As you said, rounding causes lack of precision after a while. I like your "infinite precision" function, but it takes some time as you noted. One way you can speed it up is by using byte arrays instead of strings. String manipulation is relatively slow. At the risk of getting chided about this not being a VBA forum

, here's another function:

VBA Code:

Function Fibonacci(ByVal N As Long) As String
Dim f(1 To 3, 1 To 32767) As Byte
Dim i As Long, loc As Long
Dim addIx1 As Byte, addIx2 As Byte, sumIx As Byte
Dim Carry As Byte, MaxLen As Long, nextDigit As Byte
 
    f(1, 1) = 1
    f(2, 1) = 1
    addIx1 = 1
    addIx2 = 2
    sumIx = 3
    
    MaxLen = 1
    For i = 3 To N
        Carry = 0
        loc = 1
        Do
            nextDigit = f(addIx1, loc) + f(addIx2, loc) + Carry
            If loc > MaxLen And nextDigit = 0 Then Exit Do
            f(sumIx, loc) = nextDigit Mod 10
            Carry = nextDigit \ 10
            loc = loc + 1
        Loop
        MaxLen = loc - 1
        addIx1 = (addIx1 Mod 3) + 1
        addIx2 = (addIx2 Mod 3) + 1
        sumIx = (sumIx Mod 3) + 1
    Next i

    For i = 1 To MaxLen
        Fibonacci = f(addIx2, i) & Fibonacci
    Next i
    
End Function

The algorithm is substantially the same as yours, but it runs about 8 times faster with my rough timing (on a 10-year old computer).

Rick Rothstein · Mar 28, 2021

Eric W said:
I like your "infinite precision" function, but it takes some time as you noted. One way you can speed it up is by using byte arrays instead of strings. String manipulation is relatively slow.

The algorithm is substantially the same as yours, but it runs about 8 times faster with my rough timing (on a 10-year old computer).

Yes, I know Byte arrays are faster than String manipulations, but I wrote my routine quite a long time ago, well before I had an appreciation for Byte arrays. Fibonacci calculations have not come up all that often across the years so it never occurred to me to attempt to revise my original code. Thanks for doing so. And you are right... your revision is notable faster than my original (probably more than 8 times faster as it only took a little under 2 minutes to process 99999) on my somewhat slow laptop (my desktop died a couple of years ago and I've never gotten around to replacing it).

GeertD · Apr 6, 2021

Xlambda said:
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!! ✌✌?

Hey Xlambda, Tboulden,

I modified Tboulden's Fibonacci and your LARGESUM (sub-) functions, and tried to calculate Fibonacci numbers for large integers, but the best I can do is Fibonacci(1274).
Any suggestions for improving this a bit? Because the big boys with their VBA code can do a lot better than this...

tboulden · Apr 6, 2021

GeertD said:
Hey Xlambda, Tboulden,

I modified Tboulden's Fibonacci and your LARGESUM (sub-) functions, and tried to calculate Fibonacci numbers for large integers, but the best I can do is Fibonacci(1274).
Any suggestions for improving this a bit? Because the big boys with their VBA code can do a lot better than this...

Can you show us what you've got for modifications? F(1274) sounds pretty good considering the limitations.

GeertD · Apr 8, 2021

tboulden said:
Can you show us what you've got for modifications? F(1274) sounds pretty good considering the limitations.

Here you have it (see: below).
Some additional information:

ALISUM14 stands for: Arbitrary Length Integer SUM (but it breaks down long before one would call it "arbitrary"...) – block-length=14,
Contrary to DAX where (evaluation) contexts are wrapped around the formula, here in Excel Classic (that's what I call it) "contexts" can pop up anywhere in the formula, without prior warning...
...that's why I made an equivalent, more intuitive and more easy to understand ALISUM14_Long version.
FIB14_ breaks down at n=247.
ALISUM14 breaks down at n=1275.

Any suggestions on how to improve this a little bit?
I mean: we're never gonna beat the big boys with their VBA code, but I wouldn't mind narrowing the gap a little more...

DXLR's LAMBDA.LET Library_v00.07.xlsb

A

B

C

D

E

F

G

H

I

1

FIB14_

2

=LAMBDA(n,a,b,IF(n=0,a,FIB14_(n-1,b,ALISUM14(a,b))))

3

ALISUM14

4

=LAMBDA(A,B, IF(and(--A<1e14,--B<1e14),A+B,LET( AB,CHOOSE({1;2},A,B),L,LEN(AB),NrBlocks,ROUNDUP(MAX(L)/14,0),NrDigits,NrBlocks*14, SumDigits,CarryDigits14(MMULT({1,1},--MID(IF(L<NrDigits,REPLACE(AB,1,0,REPT(0,NrDigits-L)),AB),(SEQUENCE(,NrBlocks)-1)*14+1,14)),0), INDEX(SumDigits,1)&CONCAT(RIGHT(INDEX(SumDigits,SEQUENCE(,NrBlocks-1,2)),14)) )))

5

CarryDigits14

6

=LAMBDA(A,Stack,LET( ColsA,COLUMNS(A),ColdexSp1,SEQUENCE(,COLUMNS(Stack)+1), NewStack,IF(ColdexSp1=1,INDEX(A,ColsA)+INT(INDEX(Stack,1)/1e14),INDEX(Stack,ColdexSp1-1)), IF(ColsA=1,INDEX(NewStack,SEQUENCE(,COLUMNS(Stack))),CarryDigits14(INDEX(A,SEQUENCE(,ColsA-1)),NewStack)) ))

7

ALISUM14Long

8

=LAMBDA(A,B, IF(and(--A<1e14,--B<1e14),A+B,LET( AB,CHOOSE({1;2},A,B),L,LEN(AB), NrBlocks,ROUNDUP(MAX(L)/14,0),NrDigits,NrBlocks*14, ColdexBlocks,SEQUENCE(,NrBlocks),ColdexBlocksShift,SEQUENCE(,NrBlocks-1,2), Equalize,IF(L<NrDigits,REPLACE(AB,1,0,REPT(0,NrDigits-L)),AB), SplitDigits,--MID(Equalize,(ColdexBlocks-1)*14+1,14), SumDigits,MMULT({1,1},SplitDigits), CorDigits,CarryDigits14(SumDigits,0), ConcatDigits,INDEX(CorDigits,1)&CONCAT(RIGHT(INDEX(CorDigits,ColdexBlocksShift),14)), ConcatDigits )))

9

10

n

FIB14_

11

0

12

1

13

16

987

14

31

1346269

15

46

1836311903

16

61

2.50473E+12

17

76

3416454622906707

18

91

4660046610375530309

19

106

6356306993006846248183

20

121

8670007398507948658051921

21

136

11825896447871834976429068427

22

151

16130531424904581415797907386349

23

166

7673480689466296922983322104048463

24

181

10466444782963453907530667147829489881

25

196

14276238357442840596168752972961528246147

26

211

19472799585996817536628086585786672357234389

27

226

26560912911538016562801306271765994056795952743

28

241

36229104684137440588478518382775401680142036775841

29

247

#NUM!

30

31

n

ALISUM14

32

1272

455100808199312204463756735526671841853416144979890873529337892734965757356205977573057953664940990013200856834918244018993195806729470761030585082144383093508948019597473328037734015857015249340884234483571268731913295746410478046932707942854721781664

33

1273

736813608500330532626674242600216858479653587147490545179361015104887219145107695070924561549775785618372035244650901237877895094831251523248298642129829830987723645752943342881609295221987452136940069227668349710190309263392066283016015000766700672593

34

1274

1191914416699642737090430978126888700333069732127381418708698907839852976501313672643982515214716775631572892079569145256871090901560722284278883724274212924496671665350416670919343311079002701477824303711239618442103605009802544329948722943621422454257

35

1275

#VALUE!

36

Sandbox_pub

Cell Formulas
Range	Formula
C11:C29	C11	=FIB14_(B11,0,1)
C34:C35	C34	=ALISUM14(C33,C32)

Xlambda · Apr 11, 2021

Haha, I am impressed how a simple inocent fun quest, declared from the beginning as "not a useful formula" turned into a scientific study, with such a big traction. ??
I salute all the visitors and also, the participation of vba masters, I want them to know, as humble creator of this post, that they are more than welcomed here.
Thinking already to the next fun quest , who can find more digits of Pi. You have to beat this guys, they found only 100 000.
100,000 Digits of Pi . Some of us have too much time ?
PS. I have the solution for fib(1275), it's called pen and paper ? Peace !!

FIBONACCI

Xlambda

Well-known Member

GeertD

Board Regular

Rick Rothstein

MrExcel MVP

GeertD

Board Regular

tboulden

Board Regular

Eric W

MrExcel MVP

Rick Rothstein

MrExcel MVP

GeertD

Board Regular

tboulden

Board Regular

GeertD

Board Regular

Xlambda

Well-known Member

Forum statistics

Share this page

FIBONACCI

Well-known Member

Board Regular

MrExcel MVP

Board Regular

Board Regular

MrExcel MVP

MrExcel MVP

Board Regular

Board Regular

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