[Python-ideas] Add the imath module

[Tim Peters]

>
> [Steven D'Aprano]
 > about 4.7 seconds to test 2**800 + 1;

[Jeroen Demeyer]

> In SageMath:
>
> sage: n = 2**800+1; timeit('is_prime(n)')
> 625 loops, best of 3: 303 µs per loop
>
> That's 4 orders of magnitude faster...
>

More like 6, yes?  My Python version is more like 3, but is way fast enough
for most things I do:

$ py -m timeit -s "from temp3 import pp; n=2**800+1" "pp(n)"
200 loops, best of 5: 1.71 msec per loop

$ py -m timeit -s "from temp3 import pp; n=2**900+1" "pp(n)"
100 loops, best of 5: 2.32 msec per loop

$ py -m timeit -s "from temp3 import pp; n=2**1000+1" "pp(n)"
100 loops, best of 5: 3.15 msec per loop

Steven's numbers are pretty baffling to me, since these are all composite
and so iterating Miller-Rabin "should get out" pretty fast:

about 4.7 seconds to test 2**800 + 1;
> less than a tenth of a millisecond to test 2**900 + 1;
> and about 8.6 seconds to test 2**1000 + 1.


Here's the Python code I used:

def pp(n, k=10):
    """
    Return True iff n is a probable prime, using k Miller-Rabin tests.

    When False, n is definitely composite.
    """
    from random import randrange

    if n < 4:
        return 2 <= n <= 3
    d = nm1 = n-1
    s = 0
    while d & 1 == 0:
        s += 1
        d >>= 1
    if s == 0:
        return False # n >= 4 and even
    ss = range(1, s)
    for _ in range(k):
        a = randrange(2, nm1)
        x = pow(a, d, n)
        if x == 1 or x == nm1:
            continue
        for _ in ss:
            x = x*x % n
            if x == nm1:
                break
            if x == 1:
                return False
        else:
            return False
    return True
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20180713/76bdc1e1/attachment-0001.html>