[Python-ideas] Add the imath module

[David Mertz]

Oops... yeah.  I had fixed the "up to and including" previously, but
somehow I copied the wrong version to the thread.

On Thu, Jul 12, 2018 at 6:36 PM Tim Peters <tim.peters at gmail.com> wrote:

> [David Mertz]
>
>> Miller-Rabin or other pseudo-primality tests do not produce false
>> negatives IIUC.
>>
>
> That's true if they're properly implemented ;-)  If they say False, the
> input is certainly composite (but there isn't a clue as to what a factor
> may be); if the say True, the input is "probably" a prime.
>
>
>> 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).
>>
>
> As you noted later:
>
> I take it back... Tim's (really Will Ness's) version is *always* faster
>> and more
>
> memory friendly.
>
>
> The original version of this came from an ActiveState recipe that many on
> c.l.py contributed to (including me) years ago, and that's where all the
> speed came from.  There is, for example, no division or square roots.
> Will's contribution was the unexpected way to slash memory use, via the
> generator calling itself recursively.  Elegant and effective!
>
>
>> I'm still trying to understand it though :-).
>
>
> Picture doing the Sieve of Eratosthenes by hand, crossing out multiples of
> "the next" prime you find.  That's basically what it's doing, except doing
> the "crossing out" part incrementally, using a dict to remember, for each
> prime p, "the next" multiple of p you haven't yet gotten to.
>
>
>
>> 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
>>
>>
>>
> Note that this generates squares of odd primes too (9, 25, ...).  `up_to`
> needs to be more like `up_to_and_including`.
>
>
>

-- 
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/c6eb3550/attachment-0001.html>