Forum Discussion
Lambda Example: Generate Fibonacci series
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 breturned values for fib(10000) in agreement to several thousand digits. The FFT convolution method in the attachment is from this gist courtesy of aaltomani
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).
I think the far harder part of the calculation is the FFT convolution method - though I would also have struggled to create a recursive carry function like that of mtarler. Being more familiar with array operations, I found considering numbers as vectors more intuitive. I took the bit reversal method from the SO post. It allows one to quickly calculate matrix powers using a "shift and add" approach:
MPOWER =LAMBDA(M, n, REDUCE( MUNIT(ROWS(M)), --MID(BASE(n, 2), SEQUENCE(1 + LOG(n, 2)), 1), LAMBDA(A, b, IF(b, MMULT(M, MMULT(A, A)), MMULT(A, A)) ) ) )For Fibonacci numbers one can set M={1,1;1,0} and return the (2,1) element. The previous method uses convolution in place of MMULT to return larger numbers - as you say, perhaps there are further improvements to be made? One thing I realise is an extra convolution could be saved by writing as Convolveλ(b, 2*a+b, r)*{1,1}-Convolveλ(a, 2*b-a, r)*{1,0} where a and b are equally sized.
Mind blown! As someone that struggles to remember 6 digits, and given that one row of your number is sufficient to index every atomic particle in the universe, the idea of a number 20899 digits long is beyond my comprehension. I wouldn't have managed to frame the question, never mind answer it!
Something that might save time, is I think it is possible to omit the bit reversal steps. The transformation will contain the right numbers but not the right sequence. Once the product and inverse transformation is performed, I believe the issue is sorted.
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 )