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
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. :cool:
And the difference in performance can be "unbelievable".
Awesome! :)
 
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?
 
Last edited:
Sorry, @Rick Rothstein, this is the LAMBDA section, not the VBA-section. ;) :biggrin: ;) (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...". :)
 
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!

Cell Formulas
RangeFormula
B3:B10B3=XLOOKUP($A3,Scratch!$G$3#,Scratch!$H$3:$H$1003,"",0)
C3:D3C3=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:D8C4=TimeIt(FIB_Y,A4)
C9:C10C9=FIB_Y(A9)
Dynamic array formulas.
 
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).
 
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).
 
Last edited:
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... :(
 
Last edited:
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.
 
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
ABCDEFGHI
1FIB14_
2=LAMBDA(n,a,b,IF(n=0,a,FIB14_(n-1,b,ALISUM14(a,b))))
3ALISUM14
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)) )))
5CarryDigits14
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)) ))
7ALISUM14Long
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
10nFIB14_
1100
1211
1316987
14311346269
15461836311903
16612.50473E+12
17763416454622906707
18914660046610375530309
191066356306993006846248183
201218670007398507948658051921
2113611825896447871834976429068427
2215116130531424904581415797907386349
231667673480689466296922983322104048463
2418110466444782963453907530667147829489881
2519614276238357442840596168752972961528246147
2621119472799585996817536628086585786672357234389
2722626560912911538016562801306271765994056795952743
2824136229104684137440588478518382775401680142036775841
29247#NUM!
30
31nALISUM14
321272455100808199312204463756735526671841853416144979890873529337892734965757356205977573057953664940990013200856834918244018993195806729470761030585082144383093508948019597473328037734015857015249340884234483571268731913295746410478046932707942854721781664
331273736813608500330532626674242600216858479653587147490545179361015104887219145107695070924561549775785618372035244650901237877895094831251523248298642129829830987723645752943342881609295221987452136940069227668349710190309263392066283016015000766700672593
3412741191914416699642737090430978126888700333069732127381418708698907839852976501313672643982515214716775631572892079569145256871090901560722284278883724274212924496671665350416670919343311079002701477824303711239618442103605009802544329948722943621422454257
351275#VALUE!
36
Sandbox_pub
Cell Formulas
RangeFormula
C11:C29C11=FIB14_(B11,0,1)
C34:C35C34=ALISUM14(C33,C32)
 
Last edited:
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 !!
 

Forum statistics

Threads
1,216,505
Messages
6,131,026
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