Тест на примитивность занимает больше времени, чем метод грубой силы, как я могу улучшить?

Я пытаюсь вычислить простые числа на одной машине размером примерно 2^30-2^100.
Мой алгоритм приведен ниже для всех, кому интересно.
Я оптимизировал этот код Python, чтобы он был O(sqrt(n/2)) ( я верю) для каждого числа: он принимает только нечетные числа, и я гарантирую, что число, переданное ему, является нечетным в другом методе.

Я использовал тест Ферма на простоту, чтобы попытаться ускорить процесс. Однако числа слишком велики для встроенного метода math.pow(), поэтому я использовал возведение в степень путем возведения в квадрат.
Однако для больших чисел это занимает очень много времени, что было бы быстрее, если использовать только грубую силу.

Моя реализация неверна?
Время исходит от алгоритма возведения в квадрат, его стек повторений также съедает мою память, есть ли для этого более быстрый алгоритм, который мне следует изучить?

Чтобы вычислить, является ли число 35184372088967 простым, потребовалось 0,00100111 секунд с использованием моего алгоритма грубой силы, но для запуска простого теста потребовалось 0,40608 секунд.

Проверка простого числа грубой силой:

def isPrime(n):
    for i in range(3,int(math.sqrt(n)),2):
        if(n%i==0):
            return False
    return True

Реализация алгоритма Ферма:

def couldBePrime(n):
        if(n>308):
            return power(2,n-1)%n==1
        else:
            return math.pow(2,n-1)%n==1

Возведение в степень по алгоритму возведения в квадрат (времязатратная часть):

def power(base,exp):
    if exp == 0:
        return 1
    elif exp == 1:
        return base
    elif (exp & 1) != 0:
        return base * power(base * base, exp // 2)
    else:
        return power(base * base, exp // 2)

python optimization bignum primes modular-arithmetic
person CS2016    schedule 13.10.2017    source источник
comment
В вашем коде есть несколько проблем, некоторые из них связаны с научным моделированием проблемы (лучше всего обрабатываются на CS.SE, но также и по теме на SO), некоторые из них связаны с реализацией Python (не по теме в CS. SE и лучше всего обрабатывается на SO). Поэтому я перехожу на Stack Overflow (пожалуйста, не делайте репост).   -  person Gilles 'SO- stop being evil'    schedule 13.10.2017
comment
Вместо степенной функции скажите pow(base,exponent,modulus), чтобы выполнить модульное возведение в степень. Это встроенная функция, вам не нужно писать ее самостоятельно.   -  person user448810    schedule 13.10.2017

Ответы (1)


arrow_upward
5
arrow_downward

Ошибка: math.pow вычисляет значения с плавающей запятой. Вычисления с плавающей запятой являются приблизительными и дадут вам здесь бессмысленные результаты. Вам нужны целочисленные вычисления, такие как вы делаете (неэффективно) в своей функции power. Встроенный в Python оператор ** и функция pow (не math.pow, которая является другой функцией) работают с целыми числами.

В Python, как и во многих языках программирования, библиотека под названием math специально предназначена для вычислений с плавающей запятой, а не для других видов математических вычислений, таких как вычисления над целыми числами.

Неэффективность: чтобы вычислить b^e по модулю n, намного эффективнее выполнить арифметические действия по модулю n, чем сначала вычислить b^e, а затем разделить результат на n. Вычисление b^e требует построения очень большого числа, и это будет медленно, потому что числа довольно быстро становятся большими по мере того, как вычисление проходит через все более и более высокие степени b. (Оптимальный способ вычисления b^e определить нелегко, но все способы включают вычисление промежуточных степеней b, единственная практическая неопределенность заключается в том, в каком порядке.) Если вы хотите получить результат по модулю n, выполните все последовательные умножения по модулю n: вычислите b^2 по модулю n, затем возведите в квадрат и уменьшите по модулю n, чтобы получить b^4 по модулю n, и т. д. Каждый раз, когда вы выполняете умножение, возьмите остаток от деления на n, прежде чем делать что-либо еще.

В Python стандартная библиотечная функция pow (помните, не math.pow) сделает это за вас. Это так же просто, как

def couldBePrime(n):
    return pow(2, n-1, n) == 1

Если бы Python не имел этой функции, то ваша функция power была бы разумным способом ее реализации, если бы вы уменьшали каждый промежуточный результат по модулю n.

def power(base, exp, mod):
    if exp == 0:
        return 1
    elif exp == 1:
        return base % mod
    elif (exp & 1) != 0:
        return (base * power((base * base) % mod, exp // 2, mod)) % mod
    else:
        return power((base * base) % mod, exp // 2)

Вызов встроенной функции, конечно, намного быстрее, потому что это достойный, но не очень хороший способ выполнения операции, а также потому, что Python больше оптимизирован для простоты написания, чем для скорости, поэтому лучше оставить как как можно больше численной тяжелой работы со встроенными функциями.

Дополнительное примечание: чтобы вычислить степень двойки, есть гораздо более быстрый способ, чем умножение — выполнить сдвиг битов. Но здесь это не поможет, потому что вы хотите вычислить 2^e mod n, а не 2^e.

person Gilles 'SO- stop being evil'    schedule 13.10.2017
comment
Это именно то, что я искал, не знаю, как я упустил из виду встроенную функцию pow, но спасибо за ваш очень подробный и полезный ответ! - person CS2016; 13.10.2017