Message408962
> 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. |
|
Date |
User |
Action |
Args |
2021-12-20 14:43:55 | rhettinger | set | recipients:
+ rhettinger, tim.peters, mark.dickinson, serhiy.storchaka, PedanticHacker, mcognetta, Stefan Pochmann, pablogsal |
2021-12-20 14:43:55 | rhettinger | set | messageid: <1640011435.57.0.278266290759.issue37295@roundup.psfhosted.org> |
2021-12-20 14:43:55 | rhettinger | link | issue37295 messages |
2021-12-20 14:43:55 | rhettinger | create | |
|