利用BigInteger实现Karatsuba乘法

Question

我首先用long编写了Karatsuba算法的代码。我觉得效果很好。使用相同的逻辑，我将代码转换为BigInteger，但出于某些原因，它给了StackOverflowError。

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

EDIT1:长时间的代码也有一个逻辑缺陷。我不知道是什么。

EDIT2: long的代码现在起作用了。我误把"%“操作符换成了"/”。

EDIT3:现在一切都好。我将.xor更改为.pow，将==更改为.equals，并修复了返回语句中的一些括号问题。谢谢大家的帮助！

以下是正确的代码：

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有长代码：

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();
}

具有BigInteger代码的Karatsuba：

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());
}

Answer 1

在第一个片段中，这一行在我看来是不对的：

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

因此，现在您可能需要c = d：

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

Answer 2

在比较和分配bigint时，您做了一些错误，因此它是无限递归调用的原因。

if (n.mod(new BigInteger("2")) == new BigInteger("1"))
        n.add(new BigInteger ("1"));

应予以纠正；

if (n.mod(new BigInteger("2")).equals(new BigInteger("1")))
      n = n.add(new BigInteger ("1"));

但还有其他问题，您应该修复它，以产生与“长”版本相同的结果。希望你能纠正它们。

Answer 3

使用Ten.pow(x.intValue())而不是Ten.xor(x)