0

我正在开发一个程序来比较大整数分解的不同算法。我在比较中包括的一种算法是费马分解方法。该算法似乎适用于小数字，但当我得到更大的数字时，我会得到奇怪的结果。

这是我的代码：

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，这是不正确的，因为6194235479 * 2984853201 = 18488883597240918279。我认为我得到了这个结果是因为在算法的某个地方，我到达了一个数字变得太大或类似的点，所以算法因此有点混乱。我添加了一个检查，计算两个因子的乘积并与输入值进行比较，以便在分解错误时收到警报：

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

有趣的是，支票通过了，我没有收到警报。我尝试只打印乘法的结果，这实际上导致了输入值。所以我的问题是为什么我的程序会这样，我能做些什么呢？

4

2 回答 2

2

看起来long某处有溢出，因为 long 有 64 位和

42139523531366663 + 2^64 = 18488883597240918279

对于足够大的数字，您可能需要切换到使用BigInteger.

于 2013-02-25T17:44:43.033 回答
0

是不是因为大数相乘也有错误？

这可能是一个足够正当的理由。这就是使程序认为它的因式分解是正确的原因，但是当您在不使用程序的情况下实际乘以数字时，您会发现错误。

于 2013-02-25T17:44:36.163 回答