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

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

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

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

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

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

  • Используя сито, найдите все простые числа в первых 10 7 числах, а затем разделите n на эти простые числа как можно больше.
  • Теперь используйте алгоритм ро Полларда, чтобы попытаться найти остальные простые числа, пока 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;
}

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

Ответы [ 2 ]

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

подход

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

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

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

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

Теперь у вас есть полная факторизация.

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

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

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

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

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

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

Осуществление

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

Ошибка в коде

Вызов

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

Бонус

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

намек Решение Бонусное решение
0 голосов
/ 10 мая 2018

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

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

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

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

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

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

...