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 the value of an element in the array depends on previous elements in the same array.
This function has been created using three function in two layers. The inner layer functions include the following:
InFib: This function generates the Nth Fibonacci number
InFibSer: This function generates the entire Fibonacci series up to the Nth number
The two functions mentioned above require arguments that are complicated and less intuitive. Therefore, we use an outer layer function (FibSeries) that generates the necessary argument and calls the two functions to generate the series.
=InFIB
'This function returns nth Fibonacci using tail recursion
'It takes three arguments n, a=0 , b=1 as argument and returns the nth Fibonacci value
=LAMBDA(n,a,b,IF(n=1,a,IF(n=2,b,Infib(n-1,b,a+b))))
/* The value for the arguments a and b should be passed as 0 and 1, respectively. */
Example:
=InFIB(10,0,1) would generate 34 as the value
Our objective, here, is not to obtain a single value but to generate an entire array. However, here is where we have a challenge: While it is easier to manipulate an existing array, it is far more to difficult to create a new array (other than sequence array) or extend an existing array.
Therefore, in order to create a Fibonacci series, we are going to pass a dummy array of n values. This array will have 0 as the first element and 1 as the value for all the other elements.
The following image portrays the recursive addition process that converts that the initial array into a Fibonacci series.
The following code does carries out the process recursively till the maximum value of the array equals the nth Fibonacci value.
=INFIBSER
'This inner function takes three arguments and returns a Fibonacci series
'The three arguments are nth Fibonacci value, the initial array and a sequence array (sequential numbers from 1 to n)
'Note, the sequence array can instead be generated inside the function but it may inefficient
=Lambda(NthFib, Initval, Sqn,
Let(
Maxval,Max(Initval),
If(Maxval = NthFib,
Initval,
Let(
NewVal,If(Maxval=1,Initval+1*(Sqn>=4),
Let(
StPos,Match(Maxval,Initval,0)+1,
adval,Large(unique(Initval),2),
Initval+adval*(Sqn>=StPos)
)
),
InFibser(NthFib,NewVal,Sqn)
)
)
)
)
In the first iteration, the above function adds one to all the values from the fourth position onwards. For the subsequent iterations it adds the second largest unique value to all values that all 2 places after the position of such second largest value. The above function uses the match function to identify the position pointer.
Although the above function can generate the Fibonacci series, as mentioned earlier, it requires arguments that are less intuitive and which requires some set up.
Therefore, here we have an outer layer function that requires only one argument, n. It creates the necessary argument to be passed to the inner layer function and calls them.
=FIBSERIES
'This outermost function generates an initial array, a sequence array, and nth fibonnaci value
'It then calls the inner functions with these parameters
=Lambda(n,
Let(
Sqn,sequence(n),
initval,sign(Sqn-1),
Nthfib,Infib(n,0,1),
InFibser(Nthfib, Initval, Sqn)
)
)
This final function can be used by the user to generate the Fibonacci series by merely passing the number of values required as argument.
Hope you found this useful. I would love to know if you think there is a way to improve the algorithm, here. I am especially looking for suggestions that could replace the match / xmatch in the InFibSer function to get the position pointer. Since the positions move sequentially, I believe a mathematical solution may exist.
Thank you
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: Script Lab Add-ins.
Here a javascript algorithm that uses Matrix Exponentiation by squaring (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:
I have run a number of tests summing 4 columns by various methods including picking up and dusting down a recursive bisection approach that I wrote before Lambda helper functions and array shaping functions came out. I have included a Thunk solution with your MAP concept. I am not absolutely sure I have got the code right but the performance is acceptable.
Now it may be possible to do some of these things in Python but that is some way off for me!
