Что не так с этой реализацией Полларда Ро

#include <iostream>
#include <cstdlib>
typedef  unsigned long long int ULL;
ULL gcd(ULL a, ULL b)
{
   for(; b >0 ;)
   {
       ULL rem = a % b;
       a = b;
       b = rem;
   }
   return a;
}
void pollard_rho(ULL n)
{
   ULL i = 0,y,k,d;
   ULL *x = new ULL[2*n];
   x[0] = rand() % n;
   y = x[0];
   k = 2;
   while(1){
       i = i+1;
       std::cout << x[i-1];
       x[i] = (x[i-1]*x[i-1]-1)%n;
       d = gcd(abs(y - x[i]),n);
       if(d!= 1 && d!=n)
          std::cout <<d<<std::endl;
       if(i+1==k){
         y = x[i];
         k = 2*k;
       }
   }
}

int main()
{
   srand(time(NULL));
   pollard_rho(10);

}

Эта реализация получена из 2-го издания CLRS (номер страницы 894). while(1) выглядит подозрительно для меня. Каким должно быть условие завершения цикла while?

Я пробовал k<=n, но это не работает. Я получаю ошибку сегментации. Что за ошибка в коде и как ее исправить?


c++ algorithm factorization clrs
person Pointer    schedule 18.05.2011    source источник
comment
Вы правы насчет цикла while; завершения нет, поэтому i становится большим и индексируется в x с недопустимым значением, что вызывает ошибку сегментации.   -  person Richard Schneider    schedule 18.05.2011
comment
Итак, каким должно быть условие завершения? Пожалуйста, ознакомьтесь с алгоритмом Полларда Ро в CLRS.   -  person Pointer    schedule 18.05.2011
comment
Это вопрос с подвохом? Откуда нам знать, что с ним не так?   -  person Gabe    schedule 18.05.2011
comment
Нет, это не вопрос с подвохом. Я хочу знать, как исправить код.   -  person Pointer    schedule 18.05.2011

Ответы (3)


arrow_upward
1
arrow_downward

У меня есть только 1-е издание CLRS, но, если предположить, что оно не слишком отличается от 2-го издания, ответ на условие завершения находится на следующей странице:

Эта процедура нахождения фактора может сначала показаться несколько загадочной. Обратите внимание, однако, что POLLARD-RHO никогда не печатает неправильный ответ; любое число, которое он выводит, является нетривиальным делителем n. Однако POLLARD-RHO может вообще ничего не печатать; нет никакой гарантии, что это даст какие-либо результаты. Мы увидим, однако, что есть веские основания ожидать, что POLLARD-RHO напечатает множитель p из n примерно после sqrt(p ) итераций цикла while. Таким образом, если n является составным, мы можем ожидать, что эта процедура обнаружит достаточно делителей, чтобы полностью разложить n приблизительно после n1/4. обновление, так как каждый простой множитель p числа n, за исключением, возможно, самого большого, меньше sqrt(n).

Итак, с технической точки зрения, представление в CLRS не имеет условия завершения (вероятно, поэтому они называют его «эвристикой» и «процедурой», а не «алгоритмом»), и нет никаких гарантий, что оно когда-либо действительно что-то выдаст. полезный. На практике вы, вероятно, захотите ограничить количество итераций на основе ожидаемых n1/4 обновлений.

person mhum    schedule 18.05.2011

arrow_upward
1
arrow_downward

Зачем хранить все эти промежуточные значения? Вам действительно не нужно помещать x и y в массив. Просто используйте 2 переменные, которые вы постоянно используете повторно, x и y.

Также замените while(1) на while(d == 1) и разрежьте петлю перед

 if(d!= 1 && d!=n)
      std::cout <<d<<std::endl;
   if(i+1==k){
     y = x[i];
     k = 2*k;

Таким образом, ваш цикл должен стать

while(d == 1)
{
    x = (x*x - 1) % n;
    y = (y*y - 1) % n;
    y = (y*y - 1) % n;
    d = abs(gcd(y-x,n))%n;
}
if(d!=n)
  std::cout <<d<<std::endl;
else
  std::cout<<"Can't find result with this function \n";

Дополнительные баллы, если вы передаете функцию, используемую внутри цикла, в качестве параметра в pollard, так что, если он не может найти результат с помощью одной функции, он пытается использовать другую.

person Cronco    schedule 18.05.2011
comment
Хм. while завершается, когда d != 1, так что d != 1 в операторе if не является избыточным? - person estan; 10.10.2013

arrow_upward
0
arrow_downward

Попробуйте заменить while(1) { i = i + 1; на это:

for (i = 1; i < 2*n; ++i) {
person Richard Schneider    schedule 18.05.2011