Author tim.peters
Recipients PedanticHacker, Stefan Pochmann, mark.dickinson, mcognetta, rhettinger, serhiy.storchaka, tim.peters
Date 2021-12-29.19:27:39
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1640806059.89.0.147417002585.issue37295@roundup.psfhosted.org>
In-reply-to
Content
{Serhiy]
> It can benefit larger arguments if move the code in
> perm_comb_small().

Seems pretty clear that the newer code really belongs there instead.

> And perhaps loops in perm_comb_small() could be optimized 
> by using precalculated values for some products.

For all n <= 67, the newer code computes comb(n, k), for all k, in a small and fixed number of operations, all in platform C arithmetic. Two multiplies, a shift, and some fiddling to compute the shift count. No divisions. That's cheaper than almost every case handled by perm_comb_small()'s current

k < Py_ARRAY_LENGTH(fast_comb_limits)
           && n <= fast_comb_limits[k])

"iscomb" loop. That loop is constrained by that all intermediate results have to fit in a C unsigned long long, but the newer code only needs to know that the _final_ result fits (intermediate overflows are both expected and harmless - indeed, they're _necessary_ for the modular arithmetic to work as intended).
History
Date User Action Args
2021-12-29 19:27:39tim.peterssetrecipients: + tim.peters, rhettinger, mark.dickinson, serhiy.storchaka, PedanticHacker, mcognetta, Stefan Pochmann
2021-12-29 19:27:39tim.peterssetmessageid: <1640806059.89.0.147417002585.issue37295@roundup.psfhosted.org>
2021-12-29 19:27:39tim.peterslinkissue37295 messages
2021-12-29 19:27:39tim.peterscreate