3

C/C++ で Pollard Rho 整数因数分解を実装しようとしています。Google は、ここで問題の Java 実装を提供してくれます。

私はJavaをよく知らないので、これを思いついた.C ++での私の実装はほとんどの場合で機能しますが、「9999」のようにいくつかでは機能しません。

C++ には Biginteger クラスがなかったことを認識しているため、JAVA で提供されるすべての機能を使用することはできませんが、十分な 15 桁の数値を因数分解したいと考えています。unsigned long long

私の実装で何が間違っているかを指摘してください。

4

2 に答える 2

10

問題はここにあります：

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

absマクロにいくつかの括弧がありません。試す：

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

代わりは。abs(x-xx)( がの場合に展開されるとどうなるかを考えてくださいx-xx <= 0。)

また、gcd 関数が BigInteger ではなく int を返すのはなぜですか?

Nまた、（unsigned long long が 64 ビット整数型であると仮定すると）このコードは、より大きい場合は正しく機能しないことにも注意してください2**32。 if x(or xx) is greater than or equal to 2**32thenx*xは modulo をラップ2**64し、間違った値を与えます。のためにx*x % N。

于 2010-02-21T11:33:27.953 に答える
2

違いが 1 つあります。Java コードではcとが割り当てxられますがnew BigInteger(N.bitLength(), random)、C++ コードでは が使用rand() % Nされます。これはより小さなランダム範囲です。値 9999 の場合、バイナリは 10011100001111 であるため、Java コードはc最大x値 16383 を返します。

于 2010-02-21T11:21:52.477 に答える