[Python-ideas] Fwd: Extremely weird itertools.permutations

[Neil Girdhar]

Did you read the problem?   Anyway, let's not get off topic (permutations).

Neil


On Sun, Oct 13, 2013 at 11:54 AM, Oscar Benjamin <oscar.j.benjamin at gmail.com
> wrote:

> On 11 October 2013 22:38, Neil Girdhar <mistersheik at gmail.com> wrote:
> > My code, which was the motivation for this suggestion:
> >
> > import itertools as it
> > import math
> >
> > def is_prime(n):
> >     for i in range(2, int(math.floor(math.sqrt(n))) + 1):
> >         if n % i == 0:
> >             return False
> >     return n >= 2
>
> I don't really understand what your code is doing but I just wanted to
> point out that the above will fail for large integers (maybe not
> relevant in your case):
>
> >>> is_prime(2**19937-1)
> Traceback (most recent call last):
>   File "<stdin>", line 1, in <module>
>   File "tmp.py", line 3, in is_prime
>     for i in range(2, int(math.floor(math.sqrt(n))) + 1):
> OverflowError: long int too large to convert to float
>
> Even without the OverflowError I suspect that there are primes p >
> ~1e16 such that is_prime(p**2) would incorrectly return True. This is
> a consequence of depending on FP arithmetic in what should be exact
> computation. The easy fix is to break when i**2 > n avoiding the
> tricky sqrt operation. Alternatively you can use an exact integer sqrt
> function to fix this:
>
> def sqrt_floor(y):
>     try:
>         x = int(math.sqrt(y))
>     except OverflowError:
>         x = y
>     while not (x ** 2 <= y < (x+1) ** 2):
>         x = (x + y // x) // 2
>     return x
>
>
> Oscar
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20131013/c4113e35/attachment.html>