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)

 

[GeertD]

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

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]

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

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.

' 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]

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]

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	55	0.01
4	100	354224848179261915075	354224848179261915075	0.03
5	200	280571172992510140037611932413038677189525	280571172992510140037611932413038677189525	0.05
6	300	222232244629420445529739893461909967206666939096499764990979600	222232244629420445529739893461909967206666939096499764990979600	0.07
7	400	176023680645013966468226945392411250770384383304492191886725992896575345044216019675	176023680645013966468226945392411250770384383304492191886725992896575345044216019675	0.12
8	488	432995556774426913953123610518785740738997352293147773391602699511793756235520810632382557083997728981	432995556774426913953123610518785740738997352293147773391602699511793756235520810632382557083997728981	0.14
9	493	4801994309516818408452995190383973646671835537213025106017041525333156522800379742496995285687643305513	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]

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:

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]

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]

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]

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]

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	0
12		1	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]

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