karatsuba乘法java实现

下面是使用Karatsuba算法实现的Java代码，用于两个大整数的乘法。

import java.math.BigInteger;

public class KaratsubaMultiplication {
    public static BigInteger karatsuba(BigInteger x, BigInteger y) {
        // 如果乘数小于10，则使用传统乘法
        if (x.compareTo(BigInteger.TEN) == -1 || y.compareTo(BigInteger.TEN) == -1) {
            return x.multiply(y);
        }

        // 计算每个乘数的位数
        int n = Math.max(x.bitLength(), y.bitLength());
        int half = (n + 32) / 64 * 32;

        // 分割乘数
        BigInteger mask = BigInteger.ONE.shiftLeft(half).subtract(BigInteger.ONE);
        BigInteger xHigh = x.shiftRight(half);
        BigInteger xLow = x.and(mask);
        BigInteger yHigh = y.shiftRight(half);
        BigInteger yLow = y.and(mask);

        // 计算中间值
        BigInteger a = karatsuba(xHigh, yHigh);
        BigInteger b = karatsuba(xLow, yLow);
        BigInteger c = karatsuba(xHigh.add(xLow), yHigh.add(yLow)).subtract(a).subtract(b);

        // 合并结果
        return a.shiftLeft(2 * half).add(c.shiftLeft(half)).add(b);
    }

    public static void main(String[] args) {
        BigInteger x = new BigInteger("12345678987654321");
        BigInteger y = new BigInteger("98765432123456789");
        BigInteger result = karatsuba(x, y);
        System.out.println(result);
    }
}

在这个实现中，我们首先检查输入的乘数是否小于10，如果是，我们使用传统的乘法算法计算结果。否则，我们计算每个乘数的位数，并将它们分割成高位和低位。然后，我们计算中间值 `a`, `b` 和 `c`，并将它们合并以获得最终结果。

该算法的时间复杂度为 $O(n^{\log_2 3})$，其中 $n$ 是输入乘数的位数。相比于传统的乘法算法，Karatsuba算法可以大大减少计算次数。