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.