Tim Peters <t...@python.org> added the comment:
{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).
----------
_______________________________________
Python tracker <rep...@bugs.python.org>
<https://bugs.python.org/issue37295>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
