Author rhettinger
Recipients PedanticHacker, Stefan Pochmann, mark.dickinson, mcognetta, pablogsal, rhettinger, serhiy.storchaka, tim.peters
Date 2021-12-20.14:43:55
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1640011435.57.0.278266290759.issue37295@roundup.psfhosted.org>
In-reply-to
Content
> 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.
History
Date User Action Args
2021-12-20 14:43:55rhettingersetrecipients: + rhettinger, tim.peters, mark.dickinson, serhiy.storchaka, PedanticHacker, mcognetta, Stefan Pochmann, pablogsal
2021-12-20 14:43:55rhettingersetmessageid: <1640011435.57.0.278266290759.issue37295@roundup.psfhosted.org>
2021-12-20 14:43:55rhettingerlinkissue37295 messages
2021-12-20 14:43:55rhettingercreate