This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author benrg
Recipients benrg
Date 2022-02-26.23:35:52
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1645918553.19.0.346410511769.issue46868@roundup.psfhosted.org>
In-reply-to
Content
math.prod is slow at multiplying arbitrary-precision numbers. E.g., compare the run time of factorial(50000) 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 depth n. If you re-parenthesize the product so that the tree has depth log n, as factorial does, it's much faster. The evaluation order of prod isn't documented, so I think the change would be safe.

factorial uses recursion to build the tree, but it can be done iteratively with no advance knowledge of the total number of nodes.

This trick is widely useful for turning a way of combining two things into a way of combining many things, so I wouldn't mind seeing a generic version of it in the standard library, e.g. reduce(..., order='mid'). For many specific cases there are more efficient alternatives (''.join, itertools.chain, set.unions, heapq.merge), but it's nice to have a recipe that saves you the trouble of writing special-case algorithms at the cost of a log factor that's often ignorable.
History
Date User Action Args
2022-02-26 23:35:53benrgsetrecipients: + benrg
2022-02-26 23:35:53benrgsetmessageid: <1645918553.19.0.346410511769.issue46868@roundup.psfhosted.org>
2022-02-26 23:35:53benrglinkissue46868 messages
2022-02-26 23:35:53benrgcreate