Что такое эффективный алгоритм для нахождения всех факторов целого числа?

Question

я писал очень простую программу для изучения, если число может разделить другое число равномерно:

// use the divider squared to reduce iterations 
for(divider = 2; (divider * divider) <= number; divider++) 
    if(number % divider == 0) 
     print("%d can divided by %d\n", number, divider); 

Теперь мне было интересно, если задача может быть сделано путем нахождения квадратного корня из числа и сравнить его делитель. Однако, похоже, что sqrt() на самом деле не может повысить эффективность. Как sqrt() обрабатывался на C и как я могу повысить эффективность sqrt()? Кроме того, есть ли другой способ подойти к ответу с еще большей эффективностью?

Кроме того,

number % divider == 0 

используется для проверки, если делитель может равномерно разделить число, есть также более эффективный способ, чтобы сделать тест, кроме использования%?

Answer 1

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

Есть ты условными тесты дел рассмотреть

1. (divider * divider) <= number
2. divider <= number/divider
3. divider <= sqrt(number)

См Conditional tests in primality by trial division для более detials.

Корпус для использования зависит от ваших целей и оборудования.

Преимущество случая 1 состоит в том, что он не требует разделения. Однако он может переполняться, когда divider*divider больше, чем наибольшее целое число. Второй случай не имеет проблемы с переполнением, но требует разделения. Для case3 sqrt нужно рассчитать только один раз, но для этого требуется, чтобы функция sqrt вернулась к идеальным квадратам.

Но есть что-то еще, чтобы рассмотреть множество наборов инструкций, включая набор команд x86, и вернуть остальную часть при выполнении деления. Поскольку вы уже делаете number % divider, это означает, что вы получаете его бесплатно при выполнении number/divider.

Следовательно, случай 1 полезен только в системе, где деление и остаток не вычисляются в одной инструкции, и вы не беспокоитесь о переполнении.

Между корпусом 2 и корпусом 3 Я думаю, что основной проблемой является снова набор инструкций. Выберите случай 2, если sqrt слишком медленный по сравнению с case2 или если ваша функция sqrt не вычисляет идеальные квадраты правильно. Выберите случай 3, если набор команд не вычисляет делитель и остаток в одной инструкции.

Для случая набора команд x86 1, случай 2 и случай 3 должны обеспечивать по существу равную производительность. Так что должен не иметь причины использовать случай 1 (однако см. Тонкий пункт ниже). Стандартная библиотека C гарантирует, что совершенные квадраты sqrt выполнены правильно. Таким образом, нет недостатка в случае 3.

Но есть один тонкий момент о случае 2. Я обнаружил, что некоторые компиляторы не признают, что деление и остаток вычисляются вместе. Например, в следующем коде

for(divider = 2; divider <= number/divider; divider++) 
    if(number % divider == 0) 

GCC генерирует две инструкции разделения, хотя требуется только одна. Один из способов исправить это, чтобы сохранить разделение и напоминание близко, как этот

divider = 2, q = number/divider, r = number%divider 
for(; divider <= q; divider++, q = number/divider, r = number%divider) 
    if(r == 0) 

В этом случае GCC производит только одну инструкцию деления и case1, корпус 2 и корпус 3 имеют одинаковую производительность. Но этот код немного менее читабельный, чем

int cut = sqrt(number); 
for(divider = 2; divider <= cut; divider++) 
    if(number % divider == 0) 

, так что я думаю, в целом случай 3 является лучшим выбором, по крайней мере с набором команд x86.

Answer 2

В C вы можете взять квадратные корни чисел с плавающей запятой с семейством функций sqrt() в заголовке <math.h>.

Принимая квадратные корни, как правило, медленнее, чем деление, потому что алгоритм для принятия квадратных корней более сложный, чем алгоритм деления. Это не свойство языка C, а аппаратное обеспечение, которое выполняет вашу программу. На современных процессорах использование квадратных корней может быть столь же быстрым, как и разделение. Это относится, например, к микроархитектуре Хасуэлла.

Однако, если алгоритмические улучшения хороши, то, как правило, невелика скорость звонка sqrt().

Чтобы сравнить только до квадратного корня из number, использовать такой код:

#include <math.h> 

/* ... */ 

int root = (int)sqrt((double)number); 
for(divider = 2; divider <= root; divider++) 
    if(number % divider = 0) 
     print("%d can divided by %d\n", number, divider); 

Answer 3

Тем не менее, кажется, что SQRT() на самом деле не в состоянии повысить эффективность

Этого следует ожидать, так как сохраненное умножение на итерацию в значительной степени доминирует в гораздо более медленной операции деления внутри цикла.

Кроме того, number % divider = 0 используется для проверки того, может ли разделитель равномерно делить число, существует ли более эффективный способ проведения теста, кроме использования%?

Не то, чтобы я знал. Проверка того, является ли a % b == 0 по крайней мере такой же сложной, как проверка a % b = c для некоторого c, потому что мы можем использовать первое для вычисления последнего (с одним дополнительным добавлением). И, по крайней мере, на архитектурах Intel, вычисление последнего столь же дорого стоит вычислить, как и деление, которое является одним из самых медленных операций типичных современных процессоров.

Если вы хотите значительно лучше, вам нужен лучший алгоритм факторизации, из которых there are plenty. Один конкретный простой со временем выполнения O (n ^1/4) - Pollard's ρ algorithm. Вы можете найти простую реализацию на C++ in my algorithms library. Адаптация к C оставляется в качестве упражнения для читателя:

int rho(int n) { // will find a factor < n, but not necessarily prime 
    if (~n & 1) return 2; 
    int c = rand() % n, x = rand() % n, y = x, d = 1; 
    while (d == 1) { 
    x = (1ll*x*x % n + c) % n; 
    y = (1ll*y*y % n + c) % n; 
    y = (1ll*y*y % n + c) % n; 
    d = __gcd(abs(x - y), n); 
    } 
    return d == n ? rho(n) : d; 
} 

void factor(int n, map<int, int>& facts) { 
    if (n == 1) return; 
    if (rabin(n)) { // simple randomized prime test (e.g. Miller–Rabin) 
    // we found a prime factor 
    facts[n]++; 
    return; 
    } 
    int f = rho(n); 
    factor(n/f, facts); 
    factor(f, facts); 
} 

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

Answer 4

Это просто моя случайная мысль, поэтому, пожалуйста, прокомментируйте и критикуйте ее, если это неправильно.

Идея состоит в том, чтобы прекомпретировать все простые числа ниже определенного диапазона и использовать его в качестве таблицы.

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

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

Худший случай, цикл должен идти до конца, тогда он принимает 6542 итераций.

Учитывая ввод [0, 4294967296], это похоже на O(n^3/8).

Вот MATLAB код, который реализует этот метод:

если p порожденная p=primes(65536); этот метод будет работать для всех входов между [0, 4294967296] (но не тестировалось).

function [ output_non_zero ] = fact2(input, p) 
    output_table=zeros(size(p)); 
    i=1; 
    while(i<length(p)); 
     if(input<1.5) 
      break; 
      % break condition: input is divided to 1, 
      % all prime factors are found. 
     end 
     if(rem(input,p(i))<1) 
      % if dividable, increament counter and don't increament index 
      % keep checking until not dividable 
      output_table(i)=output_table(i)+1; 
      input = input/p(i); 
     else 
      % not dividable, try next 
      i=i+1; 
     end 
    end 

    % remove all zeros, should be handled more efficiently 
    output_non_zero = [p(output_table~=0);... 
         output_table(output_table~=0)]; 
    if(input > 1.5) 
     % the last and largest prime factor could be larger than 65536 
     % hence would skip from the table, add it to the end of output 
     % if exists 
     output_non_zero = [output_non_zero,[input;1]]; 
    end 
end 

тест

p=primes(65536); 
t = floor(rand()*4294967296); 
b = fact2(t, p); 
% check if all prime factors adds up and they are all primes 
assert((prod(b(1,:).^b(2,:))==t)&&all(isprime(b(1,:))), 'test failed');