Lambda Example: Generate Fibonacci series

mtarler 

I'm glad you raised this point as I think there was a misunderstanding in the "corrected" version - probably due to being insufficiently clearly expressed on my part. The REDUCE example was actually designed to show that Fib(1024) could be calculated in just 10 steps by successively squaring the 2x2 matrix. The video David linked to extends this method to calculate arbitrary fibonacci numbers faster by using the binary representation of a number to decompose into powers of 2. Iterating the 2x2 matrix multiplication misses the point somewhat.

davidleal  so I did not read up on any of this but do have 2 questions:

a) Why are you using a [2x2] * [2x2] instead of [1x2] * [2x2] ?  Basically aren't you using the matrix multiplication to hold your prior value so [a b] * [ 1,1; 1,0] => [a+b,  a] and you don't need the second row?

b) Why are you then using INDEX( .... ,2, 1) which is essentially the value 1 calculation behind instead of SEQUENCE(n-2) and INDEX(... 1,1) or in my suggestion just INDEX(..., 1)

I don't see any time performance improvements using my crude timer but it just makes sense to me:

FIBO_MAT=LAMBDA(n, LET(a, {1,1;1,0}, 
    IF(n>2,
       INDEX(REDUCE({1,1},SEQUENCE(n-2),
         LAMBDA(ac,_,MMULT(ac,a))),1),
       1)))

PeterBartholomew1 

Yes, the wikipedia entry was quite long and I hadn't noticed it before. Regarding the SCAN version above, I recall seeing some examples from you applying string concatenation in a similar way, this one compared favourably against the other REDUCE/VSTACK approach (0.2s vs 0.7s for 1024 elements)

davidleal 

If there were an efficient BigMul function available maybe we could make use of that kind of approach in Excel but otherwise i think we are limited by the precision.

lori_m just a minor correction to your first formula using matrix exponentiation, in order to make it works:

FIBO_MAT=LAMBDA(n, LET(a, {1,1;1,0}, IF(n=1,1, 
 INDEX(REDUCE(a,SEQUENCE(n-1),LAMBDA(ac,_,MMULT(ac,a))),2,1))))

Rather than the exponential matrix of the accumulator (ac), it is from the initial matrix (a), so I created a name for that. I haven't done any performance testing, but anyway I have seen this matrix multiplication can be simplified, calculating directly each element, so there is no need to do a matrix multiplication (resulting in O(log n)). I would say this would improve the performance. For example the following python code, uses this idea, but I don't know if it has an easy conversion to Excel (Fast Exponentiation)

def fib(n):
    v1, v2, v3 = 1, 1, 0    # initialise a matrix [[1,1],[1,0]]
    for rec in bin(n)[3:]:  # perform fast exponentiation of the matrix (quickly raise it to the nth power)
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec=='1':    v1, v2, v3 = v1+v2, v1, v2
    return v2

I guess the logic is based on this mathematical explanation (https://youtu.be/EEb6JP3NXBI) and also https://www.oranlooney.com/post/fibonacci/ another python implementation using fast exponentiation with the mathematical justification.

Regards,

David

lori_m 

I started by looking at 

= F(m)*F(n) + F(m+1)*F(n+1) 

setting m=1, and applying the basic recursion formula to F(n+1).  As usual, once one has finished you know what to search for and can find the answer.

PeterBartholomew1 

I wasn't aware of that sum of squares identity! After some reflection, I think it can be derived from the 2x2 matrix representation which also provides a fast calc of larger Fibonacci numbers,

=INDEX(REDUCE({1,1;1,0},SEQUENCE(10),LAMBDA(a,_,MMULT(a,a))),2,1)

This matches davidleal's FIBO_SERIE_STR_LM2(1024) last entry to 15sf as well as this alternative:

Fib(n)
=TEXTBEFORE(
    SCAN(
        "0,1",
        SEQUENCE(n),
        LAMBDA(a, _,
            TEXTAFTER(a, ",") & "," &
                BigAdd(TEXTBEFORE(a, ","), TEXTAFTER(a, ","))
        )
    ),
    ","
)