Python: "long int слишком большой, чтобы преобразовать его в float" при проверке (действительно больших) простых чисел - PullRequest
Новая
       14

Python: "long int слишком большой, чтобы преобразовать его в float" при проверке (действительно больших) простых чисел

0 голосов
/ 01 мая 2018

Я попытался реализовать первую функцию is_prime из этого ответа: https://stackoverflow.com/a/17298131/6208280

# for large numbers, xrange will throw an error.
# OverflowError: Python int too large to convert to C long
# to get over this:

def mrange(start, stop, step):
    while start < stop:
        yield start
        start += step

# benchmarked on an old single-core system with 2GB RAM.

from math import sqrt

def is_prime(num):
    if num == 2:
        return True
    if (num < 2) or (num % 2 == 0):
        return False
    return all(num % i for i in mrange(3, int(sqrt(num)) + 1, 2))

Все же у меня есть небольшая проблема при тестировании больших чисел.

Для действительно больших чисел я получаю ошибку переполнения: long int too large to convert to float

Я проверил макс для поплавка: 

sys.float_info.max
1.7976931348623157e+308

для is_prime(10**308) все работает нормально ... но, например, с is_prime(10**309) будет эта ошибка переполнения (из-за числа с плавающей запятой max?).

Означает ли это, что 1.7976931348623157e + 308 является пределом для такого рода функции is_prime () или есть какое-либо решение для проверки старших чисел с помощью функции is_prime ()?

На мой взгляд, такие решения, как «использовать десятичное число», на самом деле не решат проблему, из-за недостаточной точности потребуется функция проверки простых чисел?

1 Ответ

0 голосов
/ 01 мая 2018

Если единственная причина, по которой вам нужно плавать, - это возможность int(sqrt(num)), вы можете найти достаточно эффективную функцию intsqrt и использовать ее вместо этого. См. этот вопрос и сообщение в блоге, связанное с принятым ответом, для некоторых идей.

Или вы можете просто изменить свой код, чтобы он вообще не нуждался в sqrt. Например, вместо диапазона, заканчивающегося int(sqrt(num))+1, вы можете использовать takewhile, который проверяет lambda i: i*i <= num. Или, поскольку у вас уже есть эта mrange функция: 

def sqrmrange(start, sqrstop):
    while start*start < sqrstop:
        yield start
        start += step

Или, если вам не нужно, чтобы он был однострочным, вы можете написать что-то менее абстрактное (и, возможно, более эффективное?), Чем любое из них. (Но на самом деле любой intsqrt может быть быстрее, чем лучший из возможных **2 тестов, потому что вам нужно выполнить intsqrt только один раз, в начале цикла, а не каждый раз через цикл.)

Или, если вы действительно хотите сохранить структуру таким образом, вы можете просто использовать decimal. Вы говорите:

На мой взгляд, такие решения, как "использовать десятичное число", на самом деле не решат проблему, из-за недостаточной точности потребуется функция проверки простых чисел?

Но это не так. Использование float означает, что вы по своей сути ограничены 52 битами точности, что, если возникнет проблема задолго до того, как вы переполнитесь. Использование decimal означает, что вы получите столько цифр точности, сколько вы просите, и даже 30 цифр по умолчанию уже намного больше 52 бит. Например: 

>>> float(10**20) == float(10**20)+1
True
>>> Decimal(10**20) == Decimal(10**20)+1
False

(На самом деле, поскольку вы создаете Decimal из огромного int, он будет автоматически расширяться, чтобы отследить столько цифр, сколько необходимо для int…, но вам все равно нужно установить точность перед вызовом sqrt на нем.)

Может быть сложно программно вычислить и установить желаемую точность для операции, но в этом случае это довольно просто. Большая проблема в том, что действительно большие Decimals намного медленнее, чем действительно большие целые.

...