[Python-ideas] Add the imath module
David Mertz
mertz at gnosis.cx
Thu Jul 12 18:24:08 EDT 2018
I take it back... Tim's (really Will Ness's) version is *always* faster and
more memory friendly. I'm still trying to understand it though :-).
On Thu, Jul 12, 2018 at 6:05 PM David Mertz <mertz at gnosis.cx> wrote:
>
> 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.
>
--
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/3466dc59/attachment.html>
More information about the Python-ideas
mailing list