[Python-ideas] Add the imath module

[David Mertz]

On Thu, Jul 12, 2018 at 2:22 PM Chris Angelico <rosuav at gmail.com> 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.
>

Miller-Rabin or other pseudo-primality tests do not produce false negatives
IIUC.

I'm more concerned in the space/time tradeoff in the primes() generator. I
like this implementation for teaching purposes, but I'm well aware that it
grows in memory usage rather quickly (the one Tim Peters posted is probably
a better balance; but it depends on how many of these you create and how
long you run them).

from math import sqrt, ceil

def up_to(seq, lim):
    for n in seq:
        if n < lim:
            yield n
        else:
            break

def sieve_generator():
    "Pretty good Sieve; skip the even numbers, stop at sqrt(candidate)"
    yield 2
    candidate = 3
    found = []
    while True:
        lim = int(ceil(sqrt(candidate)))
        if all(candidate % prime != 0 for prime in up_to(found, lim)):
            yield candidate
            found.append(candidate)
        candidate += 2


So then how do you implement isprime().  One naive way is to compare it
against elements of sieve_generator() until we are equal or larger than the
test element.  But that's not super fast.   A pseudo-primality test is much
faster (except for in the first few hundred thousand primes, maybe).

-- 
Keeping medicines from the bloodstreams of the sick; food
from the bellies of the hungry; books from the hands of the
uneducated; technology from the underdeveloped; and putting
advocates of freedom in prisons.  Intellectual property is
to the 21st century what the slave trade was to the 16th.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20180712/ebdd6874/attachment-0001.html>