>That memory frugality adds a log2 factor to the runtime.

Your iterative algorithm is exactly the one I had in mind, but it doesn't have the run time that you seem to think. Is that the whole reason for our disagreement?

It does only O(1) extra work (not even amortized O(1), really O(1)) for each call of the binary function, and there are exactly n-1 calls. There's a log(n) term (not factor) for expanding the array and skipping NULLs in the final cleanup. The constant factor for it is tiny since the array is so small.

I implemented it in C and benchmarked it against reduce with unvarying arguments (binary | on identical ints), and it's slightly slower around 75% of the time, and slightly faster around 25% of the time, seemingly at random, even in the same test, which I suppose is related to where the allocator decides to put the temporaries. The reordering only needs to have a sliver of a benefit for it to come out on top.

When I said "at the cost of a log factor" in the first message, I meant relative to algorithms like ''.join, not left-reduce.


>I suspect the title of this report referenced "math.prod with bignums" because it's the only actual concrete use case you had ;-)

I led with math.prod because its evaluation order isn't documented, so it can be changed (and I guess I should have said explicitly that there is no up-front penalty to changing it beyond tricky cache locality issues). I said "bignums" because I had in mind third-party libraries and the custom classes that I mentioned in my last message. I put ? after reduce because its left-associativity is documented and useful (e.g. with nonassociative functions), so it would have to be extended or a new function added, which is always a hard sell. I also wanted the title to be short. I did the best I could.