[Python-ideas] Add the imath module
Steven D'Aprano
steve at pearwood.info
Thu Jul 12 20:40:48 EDT 2018
On Fri, Jul 13, 2018 at 04:20:55AM +1000, Chris Angelico wrote:
> On Fri, Jul 13, 2018 at 4:11 AM, Steven D'Aprano <steve at pearwood.info> wrote:
> > There is no reason why primality testing can't be deterministic up to
> > 2**64, and probabilistic with a ludicrously small chance of false
> > positives beyond that. The implementation I use can be expected to fail
> > on average once every 18 thousand years if you did nothing but test
> > primes every millisecond of the day, 24 hours a day. That's good enough
> > for most purposes :-)
>
> What about false negatives? Guaranteed none? The failure mode of the
> function should, IMO, be a defined and documented aspect of it.
If a non-deterministic primality tester such as (but not limited to)
Miller-Rabin says a number is composite, it is definitely composite
(ignoring bugs in the implementation, or hardware failures). If it says
it is prime, in the worst case it is merely "probably prime", with an
error rate proportional to 1/4**k where we can choose the k.
(The bigger the k the more work may be done in the worst case.)
--
Steve
More information about the Python-ideas
mailing list