使用BigInteger的唐津乘法 [英] Karatsuba Multiplication using BigInteger

问题描述

我首先用long编写了Karatsuba算法的代码。我认为它运作良好。使用相同的逻辑，我将代码转换为BigInteger，但由于某些原因，它给出了StackOverflowError。

I first wrote a code for Karatsuba algorithm using long. It works perfectly I think. Using the same logic I converted the code to BigInteger but for some reasons its giving StackOverflowError.

我不知道为什么。请帮忙。

I cant figure out why. Please help.

编辑1：长时间的代码也有逻辑上的缺陷。我不知道该怎么办。

The code for long also has a logical flaw. I am not sure what.

EDIT2：现在可以长时间使用的代码了。我错误地将％运算符切换为 /。

The code for long works now. I switched a "%" operator with "/" by mistake.

EDIT3：现在一切顺利。我将.xor更改为.pow，将==更改为.equals，并修复了return语句中的某些括号问题。谢谢大家的帮助！

All good now. I changed .xor to .pow and == to .equals and fixed some bracket issues in the return statement. Thank you everyone for the help!

这是正确的代码：

public static BigInteger karatsuba3(BigInteger i, BigInteger j){
    if (i.compareTo(Ten) == -1 || j.compareTo(Ten) == -1)
        return i.multiply(j);
    String length = getLength(i.max(j));
    BigInteger n = new BigInteger(length);
    if (n.mod(Two).equals(One))
        n = n.add(One);

    BigInteger a = i.divide(Ten.pow(n.divide(Two).intValue()));
    BigInteger b = i.mod(Ten.pow(n.divide(Two).intValue()));
    BigInteger c = j.divide(Ten.pow(n.divide(Two).intValue()));
    BigInteger d = j.mod(Ten.pow(n.divide(Two).intValue()));

    BigInteger first = karatsuba3(a,c);
    BigInteger second = karatsuba3(b,d);
    BigInteger third = karatsuba3(a.add(b),c.add(d));

    return ((first.multiply(Ten.pow(n.intValue()))).add ((((third.subtract(first)).subtract( second))).multiply(Ten.pow(n.divide((new BigInteger("2"))).intValue()))).add(second));
}

Karatsuba，长代码：

Karatsuba with long code:

public static long karatsuba1(long i, long j){
    if (i < 10 || j < 10) 
        return i*j;
    double n = getLength(Math.max(i,j));
    if (n%2 == 1)
        n++;
    long a = (long) (i/Math.pow(10,(n/2)));
    long b = (long) (i%Math.pow(10,(n/2)));
    long c = (long) (j/Math.pow(10,(n/2)));
    long d = (long) (j%Math.pow(10,(n/2)));

    long first = karatsuba1(a, c);
    long second = karatsuba1(b, d);
    long third = karatsuba1(a + b, c + d);

    return ((long) ((first * Math.pow(10, n)) + ((third - first - second) * Math.pow(10, (n/2))) + second));
}

public static int getLength( long a){
    String b = Long.toString(a);
    return b.length();
}

Karatsuba的BigInteger代码：

Karatsuba with BigInteger code:

public static BigInteger karatsuba3(BigInteger i, BigInteger j){
    BigInteger Ten = new BigInteger("10");
    if (i.compareTo(Ten) == -1 || j.compareTo(Ten) == -1)
        return i.multiply(j);
    String length = getLength(i.max(j));
    BigInteger n = new BigInteger(length);
    if (n.mod(new BigInteger("2")) == new BigInteger("1"))
        n.add(new BigInteger ("1"));

    BigInteger a = i.divide(Ten.xor(n.divide((new BigInteger("2")))));
    BigInteger b = i.mod(Ten.xor(n.divide((new BigInteger("2")))));
    BigInteger c = j.divide(Ten.xor(n.divide((new BigInteger("2")))));
    BigInteger d = j.mod(Ten.xor(n.divide((new BigInteger("2")))));

    BigInteger first = karatsuba3(a,c);
    BigInteger second = karatsuba3(b,d);
    BigInteger third = karatsuba3(a.add(b),c.add(d));

    return ((first.multiply(Ten.xor(n))).add (((third.subtract(first).subtract( second)))).multiply(Ten.xor(n.divide((new BigInteger("2"))))).add(second));
}

public static String getLength( BigInteger a){
    String b = a.toString();
    return Integer.toString(b.length());
}

推荐答案

在第一个代码段中，这行对我来说似乎是错的：

In the first snippet, this line looks wrong to me:

long d = (long) (j/Math.pow(10,(n/2)));

所以现在您有 c = d
可能要：

so right now you have c = d probably you want:

long d = (long) (j%Math.pow(10,(n/2)));

这篇关于使用BigInteger的唐津乘法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！