Самый быстрый способ вычислить число до 10^18

Question

Самый быстрый способ вычислить число до 10^18

Учитывая номер 1 <= n <= 10^18Как я могу учесть это в минимальной сложности времени?

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

Я использую алгоритм ро Полларда в дополнение к сите Эратосфена:

Используя сито, найдите все простые числа в первых 10⁷ числах, а затем разделите n с этими простыми числами как можно больше.
Теперь используйте алгоритм rho Полларда, чтобы попытаться найти остальные простые числа, пока n не станет равным 1.

Моя реализация:

#include <iostream>
#include <vector>
#include <cstdio>
#include <ctime>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>

using namespace std;

typedef unsigned long long ull;
typedef long double ld;
typedef pair <ull, int> pui;
#define x first
#define y second
#define mp make_pair

bool prime[10000005];
vector <ull> p;

void initprime(){
    prime[2] = 1;
    for(int i = 3 ; i < 10000005 ; i += 2){
        prime[i] = 1;
    }
    for(int i = 3 ; i * i < 10000005 ; i += 2){
        if(prime[i]){
            for(int j = i * i ; j < 10000005 ; j += 2 * i){
                prime[j] = 0;
            }
        }
    }
    for(int i = 0 ; i < 10000005 ; ++i){
        if(prime[i]){
            p.push_back((ull)i);
        }
    }
}

ull modularpow(ull base, ull exp, ull mod){
    ull ret = 1;
    while(exp){
        if(exp & 1){
            ret = (ret * base) % mod;
        }
        exp >>= 1;
        base = (base * base) % mod;
    }
    return ret;
}

ull gcd(ull x, ull y){
    while(y){
        ull temp = y;
        y = x % y;
        x = temp;
    }
    return x;
}

ull pollardrho(ull n){
    srand(time(NULL));
    if(n == 1)
        return n;
    ull x = (rand() % (n - 2)) + 2;
    ull y = x;
    ull c = (rand() % (n - 1)) + 1;
    ull d = 1;
    while(d == 1){
        x = (modularpow(x, 2, n) + c + n) % n;
        y = (modularpow(y, 2, n) + c + n) % n;
        y = (modularpow(y, 2, n) + c + n) % n;
        d = gcd(abs(x - y), n);
        if(d == n){
            return pollardrho(n);
        }
    }
    return d;
}
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
initprime();
ull n;
cin >> n;
ull c = n;
vector <pui> o;
for(vector <ull>::iterator i = p.begin() ; i != p.end() ; ++i){
    ull t = *i;
    if(!(n % t)){
        o.push_back(mp(t, 0));
    }
    while(!(n % t)){
        n /= t;
        o[o.size() - 1].y++;
    }
}
while(n > 1){
    ull u = pollardrho(n);
    o.push_back(mp(u, 0));
    while(!(n % u)){
        n /= u;
        o[o.size() - 1].y++;
    }
    if(n < 10000005){
        if(prime[n]){
            o.push_back(mp(n, 1));
        }
    }
}
return 0;
}

Есть ли какой-нибудь более быстрый способ для вычисления таких чисел? Если возможно, объясните почему вместе с исходным кодом.

7

algorithm primes prime-factoring sieve-of-eratosthenes factorization

Источник

user8004869 09 май '18 в 10:48

2 ответа

Решение

Самым быстрым решением для 64-битных входов на современных процессорах является небольшое количество пробных делений (количество будет отличаться, но что-то меньше 100), за которым следует Rho Полларда. Вам понадобится хороший детерминированный тест на простоту с использованием Миллера-Рабина или BPSW, а также инфраструктура для обработки нескольких факторов (например, если композит разбит на несколько композитов). Для 32-битных вы можете оптимизировать каждую из этих вещей еще больше.

Вам понадобится быстрый мультимод, так как он является ядром как для Полларда Ро, Миллера-Рабина, так и для теста Лукаса. В идеале это делается в виде крошечного фрагмента ассемблера.

Время должно быть меньше 1 миллисекунды для учета любого 64-битного ввода. Значительно быстрее под 50 бит.

Как показала реализация spBrent Бена Броува, алгоритм P2'' из статьи Брента 1980 года, похоже, работает так же быстро, как и другие реализации, о которых я знаю. Он использует улучшенный поиск цикла Brent, а также полезный трюк с задержкой GCD с необходимым добавленным возвратом.

Посмотрите эту ветку на Mersenneforum, чтобы узнать о некоторых проблемах и тестировании различных решений. У меня есть несколько тестов этих и других реализаций разных размеров, но я ничего не опубликовал (отчасти потому, что существует так много способов взглянуть на данные).

Одна из действительно интересных вещей, которые можно извлечь из этого, заключалась в том, что SQUFOF, которая в течение многих лет считалась лучшим решением для верхнего уровня 64-битного диапазона, больше не является конкурентоспособной. SQUFOF имеет то преимущество, что ему нужен только быстрый детектор совершенных квадратов для лучшей скорости, который не обязательно должен быть действительно быстрым.

3

Источник

user3126317 10 май '18 в 16:56

Другие вопросы по тегам algorithm primes prime-factoring sieve-of-eratosthenes factorization

user5407898 10 май '18 в 17:25 2018-05-10 17:25 · Accepted Answer · 2018-05-10 17:25

Подход

Допустим, у вас есть номер n это идет до 10^18, и вы хотите, чтобы факторизовать его. Поскольку это число может быть как единичным, так и равным 10¹⁸, все время оно может быть как простым, так и составным, таков мой подход -

Используя тестирование простоты Миллера Рабина, убедитесь, что число составное.
факторизовать n с использованием простых чисел до 10⁶, которые можно рассчитать с помощью сита Эратосфена.

Теперь обновленное значение n таков, что он имеет простые факторы только выше 10^6, а так как значение n может по-прежнему быть равным 10¹⁸, мы заключаем, что число либо простое, либо имеет ровно два простых фактора (не обязательно различающихся).

Запустите Миллера Рабина снова, чтобы убедиться, что число не простое.
Используйте алгоритм Полларда, чтобы получить один простой фактор.

У вас есть полная факторизация сейчас.

Давайте посмотрим на сложность времени вышеупомянутого подхода:

Миллер Рабин принимает O(log n)
Сито Эратосфена принимает O(n*log n)
Реализация Поллард Ро я поделился, берет O(n^0.25)

Сложность времени

Шаг 2 занимает максимальное время, равное O(10^7), что, в свою очередь, является сложностью вышеуказанного алгоритма. Это означает, что вы можете найти факторизацию за секунду практически для всех языков программирования.

Космическая сложность

Пространство используется только на шаге 2, где реализовано сито, и равно O(10^6), Опять же, очень практично для этой цели.

Реализация

Полный код реализован в C++14, В коде есть скрытая ошибка. Вы можете раскрыть это в следующем разделе или перейти к задаче;)

Ошибка в коде

В line 105итерации до i<=np, В противном случае вы можете пропустить случаи, когда prime[np]=999983 это главный фактор

Вызов

Дай мне значение nесли есть, где общий код приводит к неправильной первичной факторизации.

бонус

Сколько таких значений n существовать?

намек

Для такого значения n утверждение в Line 119 может потерпеть неудачу.

Решение

Давай позвоним P=999983, Все числа в форме n = p*q*r где p, q, r - простые числа>= P так что хотя бы один из них равен P приведет к неправильной первичной факторизации.

Бонусное решение

Таких чисел ровно четыре: {P₀³, P₀² P₁, P₀² P₂, P₀ P₁²}, где P₀= P = 999983, P₁= next_prime (P₀) = 1000003, P₂= следующий_прайм (P₁) = 1000033.