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

Patrick2788 

No, like yours it is left stacked.  Far more effort would be required for they layout than was needed for the calculation!  The main difference is that mine is more primitive in that it uses the recurrence relation from row to row rather that the functional form of the result.

Since you mention it though, how about this?

= REDUCE(1, SEQUENCE(n),
    LAMBDA(triangle,k,
      LET(
        previous, TAKE(triangle, -1),
        left,     HSTACK(previous, {0,0}),
        right,    HSTACK({0,0}, previous),
        triangle, VSTACK(HSTACK(0,triangle), left + right),
        IFERROR(IF(triangle,triangle,""),"")
      )
    )
  )

 

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

Resources