Lambda Example: Generate Fibonacci series

lori_m 

I suspect it is the demands of memory management that kills the REDUCE/VSTACK.  I had the idea of splitting the calculation into smaller blocks.  I had visualised nesting REDUCE but, when I followed the logic of partitioning the problem to the extreme, I finished with a scalar calculation that does not require REDUCE.  That was when I decided to dig back and resurrect the binary tree idea that I had used in the pre-helper-function days.

Ways of performing Accumulation with Dynamic Arrays - Microsoft Community Hub

I think it should be possible to combine the binary tree with a basic calculation using MMULT (maybe 512x512 might be a reasonable size).  A combination of a fast calculation method and reducing the bisection levels should be a double payoff.

One thing I still need to do is to take another look at your multiplication algorithm using convolution.  The number of digits your Fibonacci calculation reached was amazing. 

Nice recursive bisection method! There's no chance I'd have been able to figure that out... I will need to spend more time studying this!

It seems bisection is a bit faster for general accumulations and REDUCE/VSTACK is several times slower on a thousand or more rows. Removing the extra LET variable in the thunk method gave a slight performance increase and was equally fast for Fibonacci series when returning a single column (combined with mtarler's BIGADD function). 

I also included an optimised MMULT version for comparison using scaled down matrices. The 3 step version was about 50% faster than SCAN on both 4000 and 40000 rows. It should be possible to extend this to n steps, but I don't know if going beyond 3 steps would make much difference - and I couldn't work out the logic to do that yet anyway - but if I do I plan to revisit the FFT algorithm because it follows much the same algorithm.

In general Python will be considerably faster and there are also optimisations for big integers. For example running '%timeit fib(100000)' takes just 5.25ms to return all 20899 digits. In Excel however much of the gains will probably be lost in data transfer so I think lambda solutions are not going away any time soon.

lori_m 

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!

Playing with the concept a bit more, it could be worth defining a generalised SCAN function that applies to both types of setup. For Fibonacci sequence,

=SCANLIST({0,1},SEQUENCE(1000),LAMBDA(acc,i,MMULT(acc,{1,1;1,0})))

or for horizontal accumulations

=SCANLIST(SEQUENCE(ROWS(data),,0,0),SEQUENCE(, COLUMNS(data)),LAMBDA(acc,i,CHOOSECOLS(data, i) + acc))

and the definition can be hidden from view if desired:

SCANLIST=LAMBDA(initial_value, array, function,
    LET(
        list, LAMBDA(vector, LAMBDA([i], INDEX(vector, i))),
        indices, SEQUENCE(
            ROWS(initial_value),
            COLUMNS(initial_value)
        ),
        acclist, SCAN(
            LAMBDA(initial_value),
            array,
            LAMBDA(acc, i, list(function(acc(), i)))
        ),
        MAP(
            IF(indices, acclist),
            IF(array, indices),
            LAMBDA(acc, i, acc(i))
        )
    )
)

Hi Peter, I must admit I had replied from my phone to the previous message without examining your file - looking more closely I see your formulas are running horizontally across the table. As Sergei implies, I think you'd need to transpose the Fibonacci setup and augment the MAP parameters to include column indices. I didn't check closely but perhaps a setup similar to below would fair better?

=LET(
    n, ROWS(data),
    m, COLUMNS(data),
    thunks, SCAN(
        LAMBDA(SEQUENCE(n, , 0, 0)),
        SEQUENCE(, m),
        LAMBDA(thunk,i, LET(acc, CHOOSECOLS(data, i) + thunk(), LAMBDA(acc)))
    ),
    MAP(
        IF(SEQUENCE(n), thunks),
        IF(SEQUENCE(, m), SEQUENCE(n)),
        LAMBDA(thunk,i, INDEX(thunk(), i))
    )
)

SergeiBaklan we all learn off each other - I am just about keeping up with formula developments but not other areas the breadth of knowledge in your posts far exceeds mine (I have very little knowledge of OfficeScript, DAX, M, web, etc.) . If my post is hard to follow that is poor explanation on my part - it is the description of the concept and not any related language construct that is important. In the present situation 'list' works much the same as a thunk, the difference is only that one can include a position index if one chooses rather than leaving the argument empty.

PeterBartholomew1 

Every time I read your posts I understand that my 200 English words vocabulary is not enough to understand the content properly. 

Back to your performance tests. Not sure they are applied correctly to this Fibonacci case, but I'll try to play more with them.

lori_m 

I see. Having no python or any other functional programming language background, I better understand array of thunks.

In general that's great that people with other background introduce their experience to poor Excel people. Functional programmers to Excel lambdas and OfficeScript, SQL people to DAX, etc. Even more great if such people have deep Excel background, as you are.

Hi Lori

I remember MMULT with the upper triangular matrix as being remarkably effective even for quite large problems.  I just chickened out at having to explain the method to a non-mathematically inclined financial modeller as the answer to their corkscrew prayers!

The formulae in my spreadsheet are worse than the REDUCE/VSTACK row-based solutions you mention.  I have taken a vertical slice through the data array and accumulated all four rows simultaneously.  That requires 1000 applications of HSTACK.  The advantage of such an approach is that it works even when the accumulated rows are not independent.  In a time series financial model, it is possible that some accumulated arrays may depend upon more than one input row and need to be treated simultaneously.  

An approach I finished with there was to write a Lambda function that advances the model one period (essentially providing the derivative with respect to time of the entire model).  It should then be possible to place the Lambda function within SCAN to generate the entire timeseries model as an array of arrays.

SergeiBaklan 

The second List-based approach makes sense to me coming from a python background where thunks could be thought of as list generators. To get around the arrays of arrays limitation one could convert either to a list of arrays or an array of lists.

PeterBartholomew1 
I think the fibonacci examples given here and your examples both suggest moving away from REDUCE / VSTACK row-based solutions. Recommended alternatives might be:
- TOCOL for sorting rows
- SCAN (possibly with thunks) / MMULT for long / short accumulations
e.g. pre-multiplying by a lower triangular matrix of ones seems fastest on your example data