Оптимизация моего кода для поиска факторов заданного целого числа
Вот мой код, но я бы хотел его оптимизировать. Мне не нравится идея тестирования всех чисел перед квадратным корнем из n, учитывая тот факт, что можно столкнуться с поиском факторов большого числа. , Ваши ответы будут очень полезны. Заранее спасибо.
unsigned int* factor(unsigned int n)
{
unsigned int tab[40];
int dim=0;
for(int i=2;i<=(int)sqrt(n);++i)
{
while(n%i==0)
{
tab[dim++]=i;
n/=i;
}
}
if(n>1)
tab[dim++]=n;
return tab;
}
Решение
Вот предложение о том, как сделать это в «правильном» C ++ (так как вы пометили как C ++).
PS. Почти забыл упомянуть: я оптимизировал звонок на sqrt далеко 🙂
Смотрите это в прямом эфире http://liveworkspace.org/code/6e2fcc2f7956fafbf637b54be2db014a
#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>
typedef unsigned int uint;
std::vector<uint> factor(uint n)
{
std::vector<uint> tab;
int dim=0;
for(unsigned long i=2;i*i <= n; ++i)
{
while(n%i==0)
{
tab.push_back(i);
n/=i;
}
}
if(n>1)
tab.push_back(n);
return tab;
}
void test(uint x)
{
auto v = factor(x);
std::cout << x << ":\t";
std::copy(v.begin(), v.end(), std::ostream_iterator<uint>(std::cout, ";"));
std::cout << std::endl;
}
int main(int argc, const char *argv[])
{
test(1);
test(2);
test(4);
test(43);
test(47);
test(9997);
}
Выход
1:
2: 2;
4: 2;2;
43: 43;
47: 47;
9997: 13;769;
Другие решения
Есть простое изменение, которое несколько сократит время выполнения: вычеркните все 2, затем проверьте только нечетные числа.
Если вы используете
... i*i <= n; ...
Это может работать намного быстрее, чем я <= sqrt (n)
Кстати, вы должны попытаться обработать факторы с отрицательным n или, по крайней мере, быть уверенным, что вы никогда не пропустите отрицательное число
Я боюсь ты не сможешь. На планете нет известного метода, позволяющего разложить большие целые числа за полиномиальное время. Однако, есть некоторые методы, которые могут помочь вам немного (не значительно) ускорить вашу программу. Ищите Википедию для большего количества ссылок. http://en.wikipedia.org/wiki/Integer_factorization
Как видно из вашего решения, вы найдете в основном все простые числа (условие while (n%i == 0)) работает так, особенно в случае больших чисел, вы можете заранее вычислить простые числа и продолжать проверять только их. Вычисление простого числа может быть выполнено с использованием метода сита Эратосфена или другого эффективного метода.
unsigned int* factor(unsigned int n)
Если unsigned int типичный 32-битный тип, числа слишком малы, чтобы окупить его любой из более продвинутых алгоритмов. Обычные улучшения для пробного отдела, конечно, стоят того.
Если вы перемещаете деление на 2 вне цикла и делите только на нечетные числа в цикле, как упоминается Пит Беккер, по сути, вы вдвое уменьшаете число делений, необходимое для вычисления входного числа, и, таким образом, ускоряете функцию почти в 2 раза.
Если вы продвинетесь на один шаг дальше, а также удалите кратные 3 из делителей в цикле, вы уменьшите число делений и, следовательно, увеличите скорость примерно в 3 раза (в среднем; большинство чисел не имеют больших простые факторы, но делятся на 2 или на 3, и для них ускорение намного меньше, но эти числа, в любом случае, можно быстро учитывать. Если вы учитываете более длинный диапазон чисел, большая часть времени тратится на разложение нескольких чисел с большими простыми делителями).
// if your compiler doesn't transform that to bit-operations, do it yourself
while(n % 2 == 0) {
tab[dim++] = 2;
n /= 2;
}
while(n % 3 == 0) {
tab[dim++] = 3;
n /= 3;
}
for(int d = 5, s = 2; d*d <= n; d += s, s = 6-s) {
while(n % d == 0) {
tab[dim++] = d;
n /= d;
}
}
Если вы вызываете эту функцию очень часто, было бы целесообразно предварительно вычислить 6542 простых числа, не превышающих 65535, сохранить их в статическом массиве и разделить только на простые числа, чтобы исключить все деления, которые априори гарантированно не найдут делитель ,
Если unsigned int бывает больше 32 бит, тогда использование одного из более продвинутых алгоритмов будет выгодно. Вы все еще должны начать с пробных делений, чтобы найти малые главные факторы <= 1000, <= 10000, <= 100000 или возможно <= 1000000 должно быть проверено, мое внутреннее чувство говорит, что одно из меньших значений было бы лучше в среднем). Если после фазы пробного разделения факторизация еще не завершена, проверьте, является ли оставшийся фактор простым, используя, например, детерминистический (для рассматриваемого диапазона) вариант теста Миллера-Рабина. Если это не так, ищите фактор, используя ваш любимый продвинутый алгоритм. Для 64-битных чисел, я бы порекомендовал Алгоритм Полларда или факторизация эллиптической кривой. Алгоритм Полларда проще реализовать, и для чисел такой величины он находит факторы за сопоставимое время, так что это моя первая рекомендация.
Int — это маленький путь к проблемам производительности. Я просто попытался измерить время вашего алгоритма с помощью boost, но не смог получить какой-либо полезный вывод (слишком быстро). Так что вам не стоит беспокоиться о целых числах.
Если вы используете i * i, я смог вычислить 1.000.000 9-значных чисел за 15.097 секунд. Хорошо оптимизировать алгоритм, но вместо того, чтобы «тратить» время (зависит от вашей ситуации), важно учитывать, действительно ли небольшое улучшение действительно стоит усилий. Иногда вы должны спросить себя, нужно ли вам рассчитывать, чтобы иметь возможность рассчитать 1.000.000 дюймов за 10 секунд или 15 тоже хорошо.
detector