Re: [Python-ideas] Add the imath module
On 2018-07-13 04:02, Chris Angelico wrote:
Haha. Okay. I'm not familiar with every possible primality test, so I had no idea that they ALL have the same failure mode :)
There exist guaranteed primality tests, but those are much slower and more complicated. The state of the art is ECPP: https://en.wikipedia.org/wiki/Elliptic_curve_primality
If there's going to be failure possible primality tests, there should also exist certain ones. No matter how slow it can be to do it. Python if often a language for beginners. I think it'd be confusing to a lot of people that there's going to be tests that show "This one is probably prime", instead of sure tests. I'd call the functions is_prime() and is_likely_prime() (or is_likely_not_prime(), depending on where it fails), to make it really clear which you're picking and avoid confusion. 2018-07-13 10:21 GMT+02:00 Jeroen Demeyer <J.Demeyer@ugent.be>:
On Fri, Jul 13, 2018 at 10:43:12AM +0200, Jacco van Dorp wrote:
I think that it is precisely because this will be used by beginners that we shouldn't offer such a choice. Its our job to curate the APIs in the std lib, not to burden inexpert users with excess choices that will only worry them. If this were a third-party module, I would say, "the more the merrier". Let it provide a dozen different implementations, that's cool. But the stdlib is batteries, not nuclear reactors. If you want a choice of algorithms, or the ability to configure space versus time versus guarantees, I think you ought to be using a 3rd party module, not the std library. I'm not saying hide the fact that it is probabilistic, but that's an implementation detail that *in practice* makes no difference at all. Using Miller-Rabin and 30 randomly chosen witnesses, the probability of a wrong answer is < 0.000000000000000001. If we tested a million numbers a second, it would take an average of 18,000+ years to come across a single such error. In comparison, your computer probably experiences something of the order of 1 cosmic-ray induced bit-flip causing data corruption per week. https://stackoverflow.com/questions/2580933/cosmic-rays-what-is-the-probabil... Since using probabilistic methods is good enough for PGP and other high-security protocols, it's surely good enough for Tom Schoolboy testing whether 1234567890123456789 is prime. (For the record: it isn't.) -- Steve
There is a VERY slow certain test for primality: divide by every candidate factor (up to sqrt(N)). This is certainly not what we want for very large numbers. But the uncertainty of the probabilistic tests is very small. Steven likened the odds of the test being wrong to "less than the chance of a cosmic ray hitting a memory cell and altering the result." In any case, an amateur programmer could write a tight loop testing random large numbers and leave it running for the rest of their life without ever encountering a false positive. Number theorists have constructed these false positives... But if you know enough to do that construction, this isn't going to confuse you. On Fri, Jul 13, 2018, 4:44 AM Jacco van Dorp <j.van.dorp@deonet.nl> wrote:
If there's going to be failure possible primality tests, there should also exist certain ones. No matter how slow it can be to do it. Python if often a language for beginners. I think it'd be confusing to a lot of people that there's going to be tests that show "This one is probably prime", instead of sure tests. I'd call the functions is_prime() and is_likely_prime() (or is_likely_not_prime(), depending on where it fails), to make it really clear which you're picking and avoid confusion. 2018-07-13 10:21 GMT+02:00 Jeroen Demeyer <J.Demeyer@ugent.be>:
On Fri, Jul 13, 2018 at 10:43:12AM +0200, Jacco van Dorp wrote:
I think that it is precisely because this will be used by beginners that we shouldn't offer such a choice. Its our job to curate the APIs in the std lib, not to burden inexpert users with excess choices that will only worry them. If this were a third-party module, I would say, "the more the merrier". Let it provide a dozen different implementations, that's cool. But the stdlib is batteries, not nuclear reactors. If you want a choice of algorithms, or the ability to configure space versus time versus guarantees, I think you ought to be using a 3rd party module, not the std library. I'm not saying hide the fact that it is probabilistic, but that's an implementation detail that *in practice* makes no difference at all. Using Miller-Rabin and 30 randomly chosen witnesses, the probability of a wrong answer is < 0.000000000000000001. If we tested a million numbers a second, it would take an average of 18,000+ years to come across a single such error. In comparison, your computer probably experiences something of the order of 1 cosmic-ray induced bit-flip causing data corruption per week. https://stackoverflow.com/questions/2580933/cosmic-rays-what-is-the-probabil... Since using probabilistic methods is good enough for PGP and other high-security protocols, it's surely good enough for Tom Schoolboy testing whether 1234567890123456789 is prime. (For the record: it isn't.) -- Steve
There is a VERY slow certain test for primality: divide by every candidate factor (up to sqrt(N)). This is certainly not what we want for very large numbers. But the uncertainty of the probabilistic tests is very small. Steven likened the odds of the test being wrong to "less than the chance of a cosmic ray hitting a memory cell and altering the result." In any case, an amateur programmer could write a tight loop testing random large numbers and leave it running for the rest of their life without ever encountering a false positive. Number theorists have constructed these false positives... But if you know enough to do that construction, this isn't going to confuse you. On Fri, Jul 13, 2018, 4:44 AM Jacco van Dorp <j.van.dorp@deonet.nl> wrote:
participants (4)
-
David Mertz -
Jacco van Dorp -
Jeroen Demeyer -
Steven D'Aprano