Целочисленная факторизация Полларда Ро

Я пытаюсь реализовать целочисленную факторизацию Полларда Ро в C/C++. Google дает мне реализацию проблемы на Java здесь.

Я не очень хорошо знаю Java, поэтому то, что я придумал это. Моя реализация на C++ работает для большинства случаев, но не в нескольких, как тот "9999", который я использовал там.

Я знаю, что в С++ не было класса Biginteger, поэтому я не могу иметь полную функциональность, как в JAVA, но я хочу разложить на множители 15-значные числа, которых достаточно для unsigned long long

Пожалуйста, укажите, что не так в моей реализации.


c c++ java math factorization
person whacko__Cracko    schedule 21.02.2010    source источник
comment
Есть ли шанс, что вы могли бы вставить свой код C в вопрос, чтобы он был доступен для потомков? (Или это не подходит? Я относительный новичок в SO; возможно, 60-строчные пасты не одобряются.)   -  person Mark Dickinson    schedule 21.02.2010
comment
Существуют также большие целочисленные реализации для C++. Самый популярный, вероятно, принадлежит GNU: gmplib.org.   -  person Manuel    schedule 21.02.2010

Ответы (2)


arrow_upward
10
arrow_downward

Проблема именно здесь:

#define abs(x) (x>0)?(x):(-x)

В макросе abs вам не хватает скобок. Пытаться:

#define abs(x) ((x)>0 ? (x) : -(x))

вместо. (Подумайте, что происходит, когда abs(x-xx) расширяется в случае x-xx <= 0.)

Кроме того, почему ваша функция gcd возвращает int, а не BigInteger?

Вы также должны знать, что (при условии, что unsigned long long является 64-битным целочисленным типом), этот код не будет работать правильно для N больше, чем 2**32: если x (или xx) больше или равно 2**32, то x*x будет переноситься по модулю. 2**64, что дает неверное значение для x*x % N.

person Mark Dickinson    schedule 21.02.2010
comment
Вот почему встроенные функции предпочтительнее макросов везде, где это возможно. - person BlueRaja - Danny Pflughoeft; 22.02.2010
comment
Просто для ясности: на самом деле важны не отсутствующие скобки, а неуместные скобки рядом со знаком минус. Для безопасного выполнения умножения найдите SqrMod и MultiplyMod. - person xan; 23.02.2010

arrow_upward
2
arrow_downward

Я заметил одно отличие: код Java присваивает c и x значение new BigInteger(N.bitLength(), random), тогда как код C++ использует rand() % N, что является меньшим случайным диапазоном. Для значения 9999 двоичный код равен 10011100001111, поэтому код Java даст c и x максимальное значение 16383.

person Adrian Cox    schedule 21.02.2010
comment
Меньший диапазон rand() может повлиять на производительность, когда N больше 32767, но ваше объяснение того, что происходит, когда N = 9999, не имело для меня никакого смысла. - person President James K. Polk; 21.02.2010
comment
Я сделал ошибку из-за одной опечатки: десятичное число 9999 равно 10011100001111, и для его представления требуется 14 бит. Если N=9999, BigInteger(N.bitLength(), random) выдаст целое число от 0 до 2^14-1, тогда как rand() % N выдаст целое число от 0 до 9998. Это не ключевая ошибка в коде, но это также не точный перевод версии Java. . - person Adrian Cox; 21.02.2010