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

[Oscar Benjamin]

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