Грубая сила, однопоточная первичная факторизация
Рассмотрим следующую функцию, которая может быть использована (относительно быстро) для разложения 64-битного целого числа без знака в его основные множители. Обратите внимание, что факторинг не является вероятностным (т. Е. Точным). Алгоритм уже достаточно быстр, чтобы обнаружить, что число является простым или имеет несколько очень больших факторов в течение нескольких секунд, на современном оборудовании.
Вопрос: можно ли внести какие-либо улучшения в представленный алгоритм, сохранив его однопоточность, чтобы он мог вычислять (произвольно) очень большие 64-разрядные целые числа без знака быстрее, предпочтительно без использования вероятностного подхода (например, Миллера-Рабина) для определения первичности?
// system specific typedef for ulong should go here (or use boost::uint64_t)
typedef unsigned __int64 ulong;
typedef std::vector<ulong> ULongVector;
// Caller needs to pass in an empty factors vector
void GetFactors(ULongVector &factors, ulong num)
{
// Num has to be at least 2 to contain "prime" factors
if (num<2)
return;
ulong workingNum=num;
ulong nextOffset=2; // Will be used to skip multiples of 3, later
// Factor out factors of 2
while (workingNum%2==0)
{
factors.push_back(2);
workingNum/=2;
}
// Factor out factors of 3
while (workingNum%3==0)
{
factors.push_back(3);
workingNum/=3;
}
// If all of the factors were 2s and 3s, done...
if (workingNum==1)
return;
// sqrtNum is the (inclusive) upper bound of our search for factors
ulong sqrtNum=(ulong) sqrt(double(workingNum+0.5));
// Factor out potential factors that are greate than or equal to 5
// The variable n represents the next potential factor to be tested
for (ulong n=5;n<=sqrtNum;)
{
// Is n a factor of the current working number?
if (workingNum%n==0)
{
// n is a factor, so add it to the list of factors
factors.push_back(n);
// Divide current working number by n, to get remaining number to factor
workingNum/=n;
// Check if we've found all factors
if (workingNum==1)
return;
// Recalculate the new upper bound for remaining factors
sqrtNum=(ulong) sqrt(double(workingNum+0.5));
// Recheck if n is a factor of the new working number,
// in case workingNum contains multiple factors of n
continue;
}
// n is not or is no longer a factor, try the next odd number
// that is not a multiple of 3
n+=nextOffset;
// Adjust nextOffset to be an offset from n to the next non-multiple of 3
nextOffset=(nextOffset==2UL ? 4UL : 2UL);
}
// Current workingNum is prime, add it as a factor
factors.push_back(workingNum);
}
Спасибо
Изменить: я добавил еще больше комментариев. Причина, по которой вектор передается по ссылке, заключается в том, что он позволяет повторно использовать вектор между вызовами и избегать динамического распределения. Причина, по которой вектор не очищен в функции, заключается в том, что он допускает нечетное требование добавления текущих «числовых» факторов к факторам, уже имеющимся в векторе.
Сама функция не симпатична и может быть реорганизована, но вопрос в том, как сделать алгоритм быстрее. Поэтому, пожалуйста, никаких предложений о том, как сделать функцию более красивой, читаемой или C ++. Это детская игра. Сложнее всего усовершенствовать этот алгоритм, чтобы он мог быстрее находить (проверенные) факторы.
Обновить:Potatoswatter пока что есть несколько отличных решений, обязательно посмотрите его MMX-решение внизу.