Forum Discussion

Viz's avatar
Viz
Brass Contributor
Jan 05, 2021

Lambda Example: Generate Fibonacci series

In this post, I would like to explain how I have used Lambda to create a function to generate a Fibonacci series array.   This example can also be used to understand how to create an array where th...
excel
office 365
davidleal's avatar
davidleal
Iron Contributor
Apr 22, 2023

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

mtarler's avatar
mtarler
Silver Contributor
Apr 22, 2023

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)))
  • lori_m's avatar
    lori_m
    Iron Contributor
    Apr 23, 2023

    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.

Resources