Author tim.peters
Recipients PedanticHacker, Stefan Pochmann, mark.dickinson, mcognetta, rhettinger, serhiy.storchaka, tim.peters
Date 2021-12-30.03:46:55
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1640836015.89.0.904355123256.issue37295@roundup.psfhosted.org>
In-reply-to
Content
[Tim]
> That's [Mark's code] cheaper than almost every case handled by
> perm_comb_small()'s current ... "iscomb" loop.

Although I should clarify they're aimed at different things, and don't overlap all that much. Mark's code, & even more so Raymond's extension, picks on small "n" and then looks for the largest "k" such that comb(n, k) can be done with supernatural speed.

But the existing perm_comb_small() picks on small "k" and then looks for the largest "n" such that "the traditional" one-at-a-time loop can complete without ever overflowing a C uint64 along the way.

The latter is doubtless more valuable for perm_comb_small(), since its recursive calls cut k roughly in half, and the first such call doesn't reduce n at all.

But where they do overlap (e.g., comb(50, 15)), Mark's approach is much faster, so that should be checked first.
History
Date User Action Args
2021-12-30 03:46:55tim.peterssetrecipients: + tim.peters, rhettinger, mark.dickinson, serhiy.storchaka, PedanticHacker, mcognetta, Stefan Pochmann
2021-12-30 03:46:55tim.peterssetmessageid: <1640836015.89.0.904355123256.issue37295@roundup.psfhosted.org>
2021-12-30 03:46:55tim.peterslinkissue37295 messages
2021-12-30 03:46:55tim.peterscreate