[Python-ideas] Add the imath module

[Steve Barnes]

Looking for some information on how long it has taken to generate large 
primes I stumbled across 
https://arxiv.org/ftp/arxiv/papers/1709/1709.09963.pdf which makes 
interesting reading. It concentrates on giving no false negatives (never 
saying n is not a prime when it is) but giving an increasing probability 
that n is a prime as testing goes on.

I did find an article from 2016 that mentioned M77232917 (a 23,249,425 
digit Mersenne prime) and M74207281 (22,338,618 digit Mersenne prime) 
with the latter taking a month to check with the Lucas-Lehmer test.


On 14/07/2018 05:54, Steven D'Aprano wrote:
> On Fri, Jul 13, 2018 at 10:52:38AM -0500, Tim Peters wrote:
> 
>> Steven's numbers are pretty baffling to me, since these are all composite
>> and so iterating Miller-Rabin "should get out" pretty fast:
> 
> That's because you haven't seen my code :-)
> 
> It's over-engineered, class-based, and written as a learning exercise.
> There's a compatibility layer so it will work back to Python 2.4 and an
> instrumentation layer which I inserted in a fit of enthusiasm to gather
> staticistics, which I have never once looked at since.
> 
> And *even so* it is still fast enough for casual use at the interactive
> interpreter, compared to more naive algorithms with worse Big O
> performance characteristics.
> 
> You might think 5 seconds is slow, but I'm serious when I say some of
> the other algorithms I played with would take *days* to generate,
> or check, largish primes.
> 
> 

-- 
Steve (Gadget) Barnes
Any opinions in this message are my personal opinions and do not reflect 
those of my employer.

---
This email has been checked for viruses by AVG.
https://www.avg.com