Lambda Example: Generate Fibonacci series

PeterBartholomew1 

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.

lori_m 

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.

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
)

Given the limitations we have with Excel precision for large Fibonacci numbers it is worth to consider this approach that uses Excel Javascript API, with the help of Microsoft Garage Project: https://github.com/OfficeDev/script-lab

Here a https://www.nayuki.io/page/fast-fibonacci-algorithms (something we discussed in this post also trying to implement it in Excel):

/**
 * @customfunction
 *  {number} n The nth Fibonacci number to be calculated
 * @returns {string} The Fibonacci number
 */
function fib(n) {
  function rec(n) {
    if (n == 0)
      return [0n, 1n];
    else {
      const [a, b] = rec(Math.floor(n / 2));
      const c = a * (b * 2n - a);
      const d = a * a + b * b;
      if (n % 2 == 0)
        return [c, d];
      else
        return [d, c + d];
    }
  }
  if (n < 0)
    throw RangeError("Negative arguments not implemented");
  return rec(n)[0].toString();
}

Please keep in mind that @tags in the comment section are required to register properly the custom function. The calculation is carried out with BigInt precision (n suffix in the numbers used) otherwise we would have the same limitation Excel has loosing precision. Working with BigInt numbers, there is no precision limitation. Finally, we convert the result into a string so the output will be as text data type.

If the function was defined, for example in the LIB Snippet, then you can invoke it as follows:

=SCRIPTLAB.LIB.FIB(10000)

It returns the correct result in less than 2 secs! I tested also for 100K Fibonacci number with similar execution time, so it a scalable solution.

Here is the output for Fibonacci number 100:

lori_mI tested it with Excel for Web (free version), I haven't tried with my work computer that comes with Excel Desktop (I cannot use AFE Add-ins, that is why I prefer to test on the free version online).

CORRECTION: The limit is reached with the function I used to calculate the performance (https://github.com/microsoft/advanced-formula-environment/blob/main/examples/Lib.md from Andrew D Gordon from AFE Add-ins). Now I tested it without using this function, and results now look better:

• FIB (lor_m using convolution) for 10K Fibo number: 1,150 ms
• FIBO_STR (using BigAdd) for 10K Fibo number.: 12,510 ms

so FIB solution is about 10x faster!!!, not just that, the duration is not linear, so it is very efficient, for example for FIBO 100K it takes around 2,000 ms. Obviously the number cannot be represented in Excel entirely, but it returns a result. Python is not even able to compute this number. 

Great solution lori_m finally we have an Excel efficient solution for large Fibonacci numbers!

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

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?

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