[issue46868] Improve performance of math.prod with bignums (and functools.reduce?)

Tim Peters added the comment: > the total number of trailing 1 bits in the integers from 1 > through N inclusive is N - N.bit_count() Sorry, that's the total number of trailing 0 bits. The total number of trailing 1 bits is (N+1) - (N+1).bit_count(). -- _

[issue46868] Improve performance of math.prod with bignums (and functools.reduce?)

Tim Peters added the comment: About runtime, you're right. I did a ballpark "OK, if there are N incoming values, the inner loop has to go around, for each one, looking for a NULL, across a vector of at most log2(N) entries. So N * log2(N)". But, in fact, it's highly skewed toward getting out

[issue46868] Improve performance of math.prod with bignums (and functools.reduce?)

benrg added the comment: >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 amorti

[issue46868] Improve performance of math.prod with bignums (and functools.reduce?)

Tim Peters added the comment: Too abstract for me to find compelling. I suspect the title of this report referenced "math.prod with bignums" because it's the only actual concrete use case you had ;-) Here's another: math.lcm. That can benefit for the same reason as math.prod - provoking Kar

[issue46868] Improve performance of math.prod with bignums (and functools.reduce?)

benrg added the comment: Anything that produces output of O(m+n) size in O(m+n) time. Ordered merging operations. Mergesort is a binary ordered merge with log-depth tree reduction, and insertion sort is the same binary operation with linear-depth tree reduction. Say you're merging sorted lis

[issue46868] Improve performance of math.prod with bignums (and functools.reduce?)

Tim Peters added the comment: Hi. "It's pretty good for a lot of things" is precisely what I'm questioning. Name some, and please be specific ;-) Tree reduction is very popular in the parallel processing world, for obvious reasons. But we're talking about a single thread here, and there aren

[issue46868] Improve performance of math.prod with bignums (and functools.reduce?)

benrg added the comment: My example used ints, but I was being deliberately vague when I said "bignums". Balanced-tree reduction certainly isn't optimal for ints, and may not be optimal for anything, but it's pretty good for a lot of things. It's the comparison-based sorting of reduction alg

[issue46868] Improve performance of math.prod with bignums (and functools.reduce?)

Tim Peters added the comment: I don't know that there's a good use case for this. For floating addition, tree-based summation can greatly reduce total roundoff error, but that's not true of floating multiplication. The advantage for prod(range(2, 50001)) doesn't really stem from turning it

[issue46868] Improve performance of math.prod with bignums (and functools.reduce?)

Change by Ned Deily : -- nosy: +mark.dickinson, rhettinger, tim.peters ___ Python tracker ___ ___ Python-bugs-list mailing list Unsu

[issue46868] Improve performance of math.prod with bignums (and functools.reduce?)

New submission from benrg : math.prod is slow at multiplying arbitrary-precision numbers. E.g., compare the run time of factorial(5) to prod(range(2, 50001)). factorial has some special-case optimizations, but the bulk of the difference is due to prod evaluating an expression tree of dept