> > [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
_______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/