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
mtarler's avatar
mtarler
Silver Contributor
Apr 25, 2023

PeterBartholomew1  OK all this inspired me to bring it back to this topic and create the "classic" fib spiral:

=LET(n,10, LET(a, {1,1;1,0}, IF(n>2,
    DROP(REDUCE({1,1;1,1},SEQUENCE(n-2,,0),LAMBDA(ac,n,
      LET(fibNs,TAKE(ac,1,2),
      fibSp,DROP(ac,1),
      fibNextPair,MMULT(fibNs,a),
      fibNext, INDEX(fibNextPair,1),
      fibNextBlock, SEQUENCE(fibNext,fibNext,fibNext,0),
      fibSpiral, CHOOSE(MOD(n,4)+1,VSTACK(fibSp,fibNextBlock), HSTACK(fibSp,fibNextBlock), VSTACK(fibNextBlock,fibSp),HSTACK(fibNextBlock,fibSp)),
      VSTACK(fibNextPair,fibSpiral)  ))),1),
   "n must > 2")))
PeterBartholomew1's avatar
PeterBartholomew1
Silver Contributor
Apr 25, 2023

mtarler 

I didn't even think of trying that!  How about a bit of conditional formatting?

Every workbook should have one?

  • lori_m's avatar
    lori_m
    Iron Contributor
    May 11, 2023

    Following up on the earlier BigMul idea, it seems one could apply convolution to the digits, e.g. 123*321 could be translated to

    =CONVOLVE({1,2,3},{3,2,1})

    giving {3,8,14,8,3} then carry tens to return 39483. Combining with a simplified version of the davidleal python method above (which appears to come from here ),

    def fib(n):
    a,b =  0,1                       # initialise matrix [[a+b,b] ,[b,a]]]
    for rec in bin(n)[3:]:  
        a,b = a*a+b*b,b*(2*a+b)      # square of matrix 
        if rec=='1' :  a,b = b,a+b   # multiply by initial matrix
    return b

    returned values for fib(10000) in agreement to several thousand digits. The FFT convolution method in the attachment is from this gist courtesy of aaltomani

     

    • PeterBartholomew1's avatar
      PeterBartholomew1
      Silver Contributor
      May 12, 2023

      lori_m 

      I must confess, I wouldn't have thought of a convolution to perform multiplication!  Convolution appears to be even more versatile than I had thought.  The carry step would appear to require a reverse scan (or storing the number from least to most significant digit).  

      • lori_m's avatar
        lori_m
        Iron Contributor
        May 16, 2023

        PeterBartholomew1 

        I borrowed the non-recursive Convolve function you shared before and made a few other adjustments which improved performance to sub-second for Fib(10k) and several seconds for Fib(100k). Results can also be output in a grid means we are not limited by character length in a cell. The goal I have in the back of my mind is to build a BigInt namespace including operations for arbitrary length addition, multiplication and exponentiation along the lines of the davidleal JS sample above.  

         

        The code for generating Fibonacci pairs follows the reverse SCAN method you suggest as below - digits are grouped into fives for greater efficiency.  The FFT multiplication method is detailed in Multiplication algorithm - Wikipedia (Schönhage–Strassen section)

         

         

         

        =LET(
    a, TOCOL(CHOOSEROWS(acc, 1)),
    b, TOCOL(CHOOSEROWS(acc, 2)),
    r, 2 * ROWS(b) - 1,
    aa, Convolveλ(a, a, r),
    bb, Convolveλ(b, b, r),
    ab, Convolveλ(a, b, r),
    fib, MMULT(HSTACK(aa, bb, ab), IF(bin, {0, 1; 1, 2; 2, 2}, {1, 0; 1, 1; 0, 2})),
    carry, MOD(
        SCAN(
            0,
            TRANSPOSE(TAKE(fib, MATCH(2, 1 / CHOOSECOLS(fib, 2)) + 3)),
            LAMBDA(acc, nums, nums + QUOTIENT(acc, 10 ^ 5))
        ),
        10 ^ 5
    ),
    carry
)

         

         

         

         

    • davidleal's avatar
      davidleal
      Iron Contributor
      May 12, 2023

      lori_m How it happened that we started with Fibonacci number and ended up with Fast Fourier Transformation?, 🙂 Very interesting. I am taking a look at it. Complex solution it requires several LAMBDA functions to get there and probably some additional explanation would be needed to fully understand it. 

       

      I see you use BASE function, but it has a limit (no larger than 2^53). I am wondering if this limits the size of the Fibo number to get. I see also ASC function (this is the first time I see this formula) what is this function used for in this context? Why is needed? Reading the documentation is related to languages that uses double-byte characters.

       

      In terms of performance, not a difference with the BidAdd approach, I ran it several times for FIBO(1221), and the worse case scenario was 110ms, so really great performance considering it has more complexity than the BidAdd approach. 

       

      Both solutions reach the maximum Excel computational capacity for 1221 Fibo number. Starting from 1222 both solutions return an empty result.

       

      So I would say both solutions have the same performance and the same maximum Fibo number, since BigAdd is a simple formulation I would consider this approach as the best one so far for big fibo numbers.

       

      Thanks in advance,

       

      David

      • lori_m's avatar
        lori_m
        Iron Contributor
        May 12, 2023

        Interesting - that's not the case for me. On my set up [Current Channel (Preview) 16327.20200] entering =FIB(1222) returns:


        1079969233398873236032844293301653524976362936180771647488810146258428573892502087348778468320557178381011519862132501167447528535147702705724587018435771357806213382154720957836431378302535456607039572026816018665428571946697730583021094317239872427815311

         

        Exactly the same as entering fib(1222) into https://www.wolframalpha.com/

        FIB(10000) took a few seconds to return the required result and also matched exactly. This method is specifically for evaluating large Fibonacci numbers not reachable by the BigAdd method - it won't return all numbers in the series.

         

        I've not tested it exhaustively, and there may well be some edge cases so it's good to get the feedback. Can anyone else check the previous attachment and confirm if FIB(1222) is also an issue on their set up?

Resources