Python: «long int слишком большой для преобразования в число с плавающей запятой» при проверке (действительно больших) простых чисел
Я попытался реализовать первую 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) будет эта ошибка переполнения (из-за макс. числа с плавающей запятой?).
Означает ли это, что 1.7976931348623157e + 308 является пределом для такого типа функции is_prime () или есть какое-либо решение для проверки более высоких чисел с помощью функции is_prime ()?
На мой взгляд, такие решения, как «использовать десятичную дробь», не решат проблему, потому что из-за отсутствия точности функция проверки простых чисел понадобится?
Задумывались ли вы о том, сколько операций потребуется, чтобы проверить, является ли 308-значное число простым, и сколько времени это займет? Ваша функция уже будет слишком медленной для 20-значных чисел, не говоря уже о 300-значных.
Ответы 1
Если единственная причина, по которой вам нужны поплавки, - это возможность выполнять 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. Ты говоришь:
In my mind such solutions as "use decimal" will not really solve the problem, because of the lack of precision a prime number checking function will need?
Но это не так. Использование 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 намного медленнее, чем действительно большие.
Это означает, что
(sys.float_info.max - ϵ) ** 2- это предел, поскольку вы звоните вsqrt(num). Существуют "алгоритмы извлечения квадратного корня из целых чисел", которые обходят стороной любое использование чисел с плавающей запятой, например, Вот этот.