Forum Discussion
Lambda Example: Generate Fibonacci series
(check the UPDATE section for the shortest and fastest solution)
Viz RecalcOrDie tboulden PeterBartholomew1 lori_m
Just to add here some of the research I did around this problem. Due to some of the limitation the recursive Lamba function have, some of the mentioned here. First I was trying to find a way to get the Fibonacci number without using the classical Fibo calculation (formula 1):
nfib_v1 = LAMBDA(n, IF(n <= 2, 1, nfib_v1(n - 1) + nfib_v1(n - 2)))
If found the following approach to avoid recursion (formula 2)
nfib_v2 = LAMBDA(n,REDUCE({1;1},SEQUENCE(IF(n<=2,1,n-2)),
LAMBDA(ac,a, IF(n<=2,1,LET(x_1,TAKE(ac,1),x_2,DROP(ac,1),
IF(a=(n-2),x_1+x_2, VSTACK(x_2, x_1+x_2)))))))
Taking into consideration the performance:
- formula 1 for 30 Fibonacci numbers takes 1800ms. Around 50 Fibonacci number start crashing
- formula 2 for 30 Fibonacci numbers returns the result instantaneously. My Excel reports 0ms. It starts showing some time consuming around 1000 Fibonacci numbers, consuming 20ms.
So the recursive approach is an elegant approach, but not a good one in terms of performance.
Back to the original problem generating a sequence of Fibonacci numbers is straightforward using formula 2 (formula 3):
nfibo_serie = LAMBDA(m, MAP(SEQUENCE(m), LAMBDA(x, nfib_v2(x))))
The good news about this approach is that you can generate any sequence of numbers (x), with a simple modification:
nfibo_serie = LAMBDA(x, MAP(x, LAMBDA(n, nfib_v2(n))))
The bad news is the performance, compared to the elegant solution provided by: lori_m : (formula 4)
FIBO_SERIE.v0 = LAMBDA(n,IF(n<=2,SEQUENCE(n,,1,0),
LET(b,FIBO_SERIE.v0(n-1), IF(SEQUENCE(n)<n,b,
INDEX(b,n-1) + INDEX(b,n-2)))))
Note: I just adapted the solution to start from F1=1.
Here are the performance results for n=1000
- Formula 3: nfibo_serie(1000): 1,230ms
- Formula 4: FIBO_SERIE.v0(1000): 110ms
as you can see it is a huge difference, I would suspect the main reason is MAP call (I also tested it with BYROW a little bit faster, but nothing relevant). and under this approach, I don't see a way to get rid of MAP.
So as you can see we have several situations where the recursive approach has been significantly time-consuming, but not for this case.
To understand how the recursion works for this case (Formula 4) provided by lori_m. We can see how it works for the case of 5. From the formula as you can see the recursion ends when n=2, so for this case what it does is the following process:
In column, A you have the final result, but the recursion goes back up to the n=2 (column D), so you should read it from column D (n=2) to column C (n=3), etc. so the formula does this backward calculation until the entire recursion is expanded up to the end n=2. On each call of the recursion, only the last row changes from the previous one, adding the next Fibonacci number. It is ensured by the second IF condition until it goes to the last one which is the sequence: {1;1}.
I hope this graphical representation helps to understand the formula.
UPDATE
Later I found that we can use an indirect way to obtain the Fibonacci number using the following mathematical formulation based on the https://math.libretexts.org/Bookshelves/Applied_Mathematics/Book%3A_College_Mathematics_for_Everyday_Life_(Inigo_et_al)/10%3A_Geometric_Symmetry_and_the_Golden_Ratio/10.04%3A_Fibonacci_Numbers_and_the_Golden_Ratio:
F(n) = (phi^n - (1-phi)^n) / sqrt(5)
where phi is the golden ratio: 1.618, so in Excel it can be formulated as follows using the simplified Binet formula (check the link):
=LAMBDA(n,ROUND(POWER((1+SQRT(5))/2,n)/SQRT(5),0))
I verified this formula has the fastest performance among all the formulas on this post. Using this formula, you can now generate the sequence as follows:
FIBO_SERIE=LAMBDA(x, BYROW(x, LAMBDA(n, FIBO(n))));
Here is the performance result for the first 1000 Fibonacci numbers:
- FIBO_SERIE.v0(1000): Around 100ms
- FIBO_SERIE(SEQUENCE(1000)): less than 20ms
So, the last FIBO_SERIE formula is not just very short, but the fastest solution among others.
NOTE: there is no need to create an additional LAMBDA function, since all the functions involved in FIBO work with arrays, i.e.:
FIBO(SEQUENCE(1000))
which should be even faster than FIBO_SERIE which uses BYROW. I tested it for the first 10K Fibonacci numbers and almost instantaneously, the worst try was 20ms.
- PeterBartholomew1Apr 12, 2023Silver Contributor
I rarely use recursion these days, preferring instead to use Lambda helper functions. Occasionally it might be a built-in SCAN or BYROW but, more often, it is a mocked-up version built from REDUCE/VSTACK since it is unusual to require an array of scalars; an array of arrays is far more useful and more frequently encountered.
For the Fibonacci series, one needs to take an array of 2 values forward so
Fibonacciλ(priorTerms, [currentData]) = LET( F₁, INDEX(priorTerms, 1), F₂, INDEX(priorTerms, 2), HSTACK(F₁ + F₂, F₁) )
The vertical SCAN is achieved by using
SCANV(initialValues, scannedArray, Fnλ) = REDUCE( initialValues, SEQUENCE(1, ROWS(scannedArray)), LAMBDA(accumulation, parameter, LET( priorResult, CHOOSEROWS(accumulation, -1), currentData, CHOOSEROWS(scannedArray, parameter), newResult, Fnλ(priorResult, currentData), VSTACK(accumulation, newResult) ) ) )
In this instance, the scanned array does not figure in the calculation so the function could be simplified, but at the cost of generality. For the Fibonacci series only one column of the results is needed, so
= LET( k, SEQUENCE(n-1), f, SCANV({1,1}, k, Fibonacciλ), TAKE(f,,-1) )
returns the first 1,000 Fibonacci numbers in 100 ms. I couldn't extend the test that much without hitting #NUM! overflow errors.
Out of interest, I had lifted the SCANV function directly from a workbook that calculated the motion of a container slung from an overhead crane, by tenths of a second for 20 secs. That required 4 variables at each step, namely the cart position, the pendulum angle subtended by the container and the corresponding velocities. The name of the game was to provide force inputs that led to a final state in which the container was hanging vertically with zero velocity since placing a swinging cargo on a truck is tricky.
The parameters were optimised by using Solver to reduce the terminal energy of the system, though lori_m has written optimisation routines as Lambda functions!
= SCANV(X₀, t, RK4Stepλ(Dλ))
- davidlealApr 12, 2023Iron Contributor
PeterBartholomew1 I don't know if at the time you replied you haven't seen the update I did to my post in the UPDATE section. I don't think any other approach can beat this one FIBO using the https://math.libretexts.org/Bookshelves/Applied_Mathematics/Book%3A_College_Mathematics_for_Everyday_Life_(Inigo_et_al)/10%3A_Geometric_Symmetry_and_the_Golden_Ratio/10.04%3A_Fibonacci_Numbers_and_the_Golden_Ratio:
=LAMBDA(n,ROUND(POWER((1+SQRT(5))/2,n)/SQRT(5),0))
I tested it for FIBO(SEQUENCE(10000)) and in the worst-case scenario, it took 20ms, so it serves to get a single Fibonacci number or a series. Short, no recursive, and low computation effort. It reminds me of this heuristic rule that I heard once, :-):
T+S+H=C
Thinking (T) plus Software (S) plus Hardware(H) is equal to Constant(C). This is what the Binet formula does. Simplified the mathematical formulation, then you can minimize the Software and Hardware effort/investment, in our case Software is Excel and Hardware is the computer where it runs.
Thanks for your replay, similar to my approach (formula 2 in my post) using REDUCE to avoid the recursion.
- PeterBartholomew1Apr 13, 2023Silver Contributor
Please accept my apologies. I hadn't noticed your use of the Binet formula. I simply revisited the problem as an exercise, since the original Viz post seemed to predate the Lambda helper functions. Somewhat oddly, I did use the Binet formula to determine why my pseudo-SCAN failed with #NUM! errors long before I reached the 10,000th term you mentioned. I hit overflow errors somewhere before the 1,500th term which in turn meant that my formula returned nothing but the error.
The main takeaway for me from the exercise is that the inbuilt Excel functions SCAN, MAP, BYCOL, BYROW are all inadequately scoped since the nested array should be the basic building block of the functionality, not an error. As it stands, the use Lambda helper functions in formulas can be more restrictive than relying on the underlying array methods they support, since the lifting and broadcasting behaviours of the array formula are not generalised as one might hope.