0

大きな整数の因数分解のさまざまなアルゴリズムを比較するプログラムに取り組んでいます。比較に含めているアルゴリズムの 1 つは、Fermats 因数分解法です。このアルゴリズムは、小さな数では問題なく機能しているように見えますが、大きな数になると奇妙な結果が得られます。

これが私のコードです：

public void fermat(long n)
{
    ArrayList<Long> factors = new ArrayList<Long>();
    a = (long)Math.ceil(Math.sqrt(n));
    b = a*a - n;
    b_root = (long)(Math.sqrt(b)+0.5);
    while(b_root*b_root != b)
    {
        a++;
        b = a*a - n;
        b_root = (long)(Math.sqrt(b)+0.5);
    }
    factors.add(a-b_root);
    factors.add(a+b_root);
}

ここで、42139523531366663 を因数分解しようとすると、結果の因数6194235479と2984853201が得られます。この結果が得られたのは、アルゴリズムのどこかで数字が長くなりすぎたり、似たようなものになるポイントに到達したためだと考えました。そのため、アルゴリズムが少し混乱しました。2 つの因数の積を計算し、入力値と比較するチェックを追加して、因数分解に問題がある場合にアラートを受け取るようにしました。

long x,y;
x = factors.get(0);
y = factors.get(1);
if(x*y!=n)
    System.out.println("Faulty factorization.");

興味深いことに、チェックは true として渡され、アラートは表示されませんでした。乗算の結果を印刷してみましたが、これが実際に入力値になりました。私の質問は、なぜ私のプログラムがこのように動作するのか、それに対して何ができるのかということです。

4

2 に答える 2

2

longlong は 64 ビットであり、どこかにオーバーフローがあるようです。

42139523531366663 + 2^64 = 18488883597240918279

数値が十分に大きい場合は、 を使用するように切り替える必要がある場合がありますBigInteger。

于 2013-02-25T17:44:43.033 に答える
0

大きな数のかけ算にも誤差があるからでしょうか。

それは十分に正当な理由かもしれません。これがプログラムに因数分解が正しいと思わせる理由ですが、実際にプログラムを使用せずに数を乗算すると、エラーが発見されます。

于 2013-02-25T17:44:36.163 に答える