[issue37295] Possible optimizations for math.comb()

[Raymond Hettinger]

Raymond Hettinger <raymond.hettinger at gmail.com> added the comment:

> The problem here is that C gives no guarantees about accuracy of either log2 or exp2

* The input table has hard-wired constants so there is no dependency on log2().  The inputs can be as exact as pi, tau, and e.

* The C library's exp2() function doesn't have to be perfect. Just being good would suffice.  Our test suite already requires that exp2() be within 5 ulp:

    self.ftest('exp2(2.3)', math.exp2(2.3), 4.924577653379665)

* With a perfect exp2(), the first failure is at C(50, 22).  With a forced error of 5 ulp, it happens at C(48, 24).  So keeping n <= 47 that would let exp2() be off substantially and still give correct answers.

* Since exp2() is deterministic, it is easy to write a test that covers all C(n, r) where 0 <= r <= n <= 47.  If there were to be a problem, we would know right away and early during the release cycle.

* Also, it is easy to prove that C(n, r) always gives the correct result for a given ulp error bound on exp2() and a given limit on n.

* The speed-up is substantial, so this is worth consideration.



> factorial(49) has 163 significant binary digits.

Exact factorials aren't needed.  The important fact (no pun intended) is that comb(47, 23).bit_length() == 44.  For this to work, we need one addition and one subtraction of 53 bit approximations to come within 44 bits of the true answer.

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue37295>
_______________________________________