使用 BigInteger 进行 Karatsuba 乘法

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

我不明白为什么。请帮忙。

EDIT1：长时间的代码也有一个逻辑缺陷。我不确定是什么。

EDIT2： long 的代码现在可以工作了。我错误地将“%”运算符换成了“/”。

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

这是正确的代码：

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

Karasuba 与 BigInteger 代码：

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

在第一个片段中，这一行对我来说看起来是错误的：

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

所以现在你有c = d也许你想要：

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