每日算法 — 使用java实现Karatsuba快速乘法：大整数分治乘法与递归优化

算法概述

Karatsuba算法由Anatolii Karatsuba于1960年提出，是首个突破O(n²)时间复杂度的大整数乘法算法。传统竖式乘法需要O(n²)次单位数字乘法，而Karatsuba算法利用分治策略，将n位大整数拆分为两部分，通过3次递归乘法而非4次，将复杂度降至O(n^log₂3)≈O(n^1.585)。这一成果开创了快速算术算法的先河，后续的Toom-Cook算法和Schönhage-Strassen算法都是在此基础上的进一步发展。

核心思想

将两个n位大整数X和Y分别拆分为高位和低位：
– X = A × 10^(n/2) + B
– Y = C × 10^(n/2) + D

传统方法计算XY = AC × 10^n + (AD + BC) × 10^(n/2) + BD，需要4次乘法。Karatsuba观察到：

AD + BC = (A + B)(C + D) – AC – BD

因此只需计算3个乘积：AC、BD、(A+B)(C+D)，再用加减法组合得到结果。

Java实现

import java.math.BigInteger;

/**
 * Karatsuba大整数快速乘法算法实现
 * 时间复杂度：O(n^1.585)
 * 空间复杂度：O(n)
 */
public class KaratsubaMultiplication {

    // 当数字位数小于此阈值时，使用普通乘法
    private static final int THRESHOLD = 32;

    /**
     * Karatsuba乘法入口
     * @param x 第一个大整数
     * @param y 第二个大整数
     * @return 乘积
     */
    public static BigInteger karatsuba(BigInteger x, BigInteger y) {
        // 处理负数情况
        boolean negative = false;
        if (x.signum() < 0) {
            x = x.negate();
            negative = !negative;
        }
        if (y.signum() < 0) {
            y = y.negate();
            negative = !negative;
        }

        BigInteger result = karatsubaPositive(x, y);
        return negative ? result.negate() : result;
    }

    /**
     * 递归实现Karatsuba乘法（仅处理非负数）
     */
    private static BigInteger karatsubaPositive(BigInteger x, BigInteger y) {
        // 小数字使用内置乘法（更高效）
        int n = Math.max(x.bitLength(), y.bitLength());
        if (n <= THRESHOLD) {
            return x.multiply(y);
        }

        // 计算分割位数（按二进制位分割）
        int half = (n / 2) + (n % 2);
        BigInteger splitPoint = BigInteger.ONE.shiftLeft(half);

        // 拆分为高位和低位
        // x = a * 2^half + b
        // y = c * 2^half + d
        BigInteger a = x.shiftRight(half);
        BigInteger b = x.and(splitPoint.subtract(BigInteger.ONE));
        BigInteger c = y.shiftRight(half);
        BigInteger d = y.and(splitPoint.subtract(BigInteger.ONE));

        // 递归计算3个乘积
        BigInteger ac = karatsubaPositive(a, c);      // a * c
        BigInteger bd = karatsubaPositive(b, d);      // b * d
        BigInteger abcd = karatsubaPositive(a.add(b), c.add(d));  // (a+b)*(c+d)

        // ad + bc = (a+b)(c+d) - ac - bd
        BigInteger ad_bc = abcd.subtract(ac).subtract(bd);

        // 组合结果：ac * 2^(2*half) + (ad+bc) * 2^half + bd
        return ac.shiftLeft(2 * half)
                 .add(ad_bc.shiftLeft(half))
                 .add(bd);
    }

    /**
     * 十进制字符串版本的Karatsuba乘法
     * 更直观展示算法原理
     */
    public static String karatsubaString(String x, String y) {
        // 处理前导零和符号
        boolean negative = false;
        if (x.startsWith("-")) {
            x = x.substring(1);
            negative = !negative;
        }
        if (y.startsWith("-")) {
            y = y.substring(1);
            negative = !negative;
        }

        // 移除前导零
        x = x.replaceFirst("^0+", "");
        y = y.replaceFirst("^0+", "");
        if (x.isEmpty()) x = "0";
        if (y.isEmpty()) y = "0";

        String result = karatsubaStringPositive(x, y);
        return negative ? "-" + result : result;
    }

    private static String karatsubaStringPositive(String x, String y) {
        int n = Math.max(x.length(), y.length());

        // 小数字使用普通乘法
        if (n <= THRESHOLD / 4) {
            return multiplySimple(x, y);
        }

        // 补零使长度为2的幂次方便分割
        int half = (n / 2) + (n % 2);
        x = padLeft(x, half * 2);
        y = padLeft(y, half * 2);

        // 分割
        String a = x.substring(0, half);
        String b = x.substring(half);
        String c = y.substring(0, half);
        String d = y.substring(half);

        // 递归计算
        String ac = karatsubaStringPositive(a, c);
        String bd = karatsubaStringPositive(b, d);
        String abcd = karatsubaStringPositive(addString(a, b), addString(c, d));

        // (a+b)(c+d) - ac - bd
        String ad_bc = subtractString(subtractString(abcd, ac), bd);

        // 结果 = ac * 10^(2*half) + ad_bc * 10^half + bd
        String result = addString(
            addString(ac + "0".repeat(2 * half), ad_bc + "0".repeat(half)),
            bd
        );

        return result.replaceFirst("^0+", "");
    }

    /**
     * 简单的大整数乘法（竖式乘法）
     */
    private static String multiplySimple(String x, String y) {
        BigInteger a = new BigInteger(x);
        BigInteger b = new BigInteger(y);
        return a.multiply(b).toString();
    }

    /**
     * 大整数加法（字符串实现）
     */
    private static String addString(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        int i = a.length() - 1, j = b.length() - 1;
        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = carry;
            if (i >= 0) sum += a.charAt(i--) - '0';
            if (j >= 0) sum += b.charAt(j--) - '0';
            sb.append(sum % 10);
            carry = sum / 10;
        }
        return sb.reverse().toString();
    }

    /**
     * 大整数减法（字符串实现，假设a>=b）
     */
    private static String subtractString(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int borrow = 0;
        int i = a.length() - 1, j = b.length() - 1;
        while (i >= 0) {
            int diff = (a.charAt(i) - '0') - borrow - (j >= 0 ? b.charAt(j) - '0' : 0);
            if (diff < 0) {
                diff += 10;
                borrow = 1;
            } else {
                borrow = 0;
            }
            sb.append(diff);
            i--; j--;
        }
        String result = sb.reverse().toString().replaceFirst("^0+", "");
        return result.isEmpty() ? "0" : result;
    }

    /**
     * 左侧补零
     */
    private static String padLeft(String s, int length) {
        if (s.length() >= length) return s;
        return "0".repeat(length - s.length()) + s;
    }

    public static void main(String[] args) {
        // 测试用例1：普通整数
        BigInteger a = new BigInteger("12345678901234567890");
        BigInteger b = new BigInteger("98765432109876543210");

        BigInteger karatsubaResult = karatsuba(a, b);
        BigInteger standardResult = a.multiply(b);

        System.out.println("Karatsuba结果: " + karatsubaResult);
        System.out.println("标准乘法结果: " + standardResult);
        System.out.println("结果一致: " + karatsubaResult.equals(standardResult));

        // 测试用例2：超大整数
        String x = "314159265358979323846264338327950288419716939937510";
        String y = "271828182845904523536028747135266249775724709369995";
        String stringResult = karatsubaString(x, y);
        String expected = new BigInteger(x).multiply(new BigInteger(y)).toString();
        System.out.println("\n超大整数测试一致: " + stringResult.equals(expected));
    }
}

复杂度分析

Karatsuba的递归关系式为T(n) = 3T(n/2) + O(n)，根据主定理，a=3, b=2, log₂3≈1.585，因此时间复杂度为O(n^1.585)。

关键优化点

1. 阈值切换：当数字位数较少时（通常32~64位），直接使用硬件乘法或内置大整数乘法，避免递归开销。
2. 二进制分割：使用位运算而非十进制分割，减少进制转换开销。
3. 内存复用：在实际工程中，可通过内存池复用临时数组，降低GC压力。

应用场景

Karatsuba算法是密码学、科学计算和高精度数学库的基础组件。RSA加密中的大数模幂运算、π的高精度计算、金融系统的精确账务计算等场景都依赖高效的大整数乘法。Java的BigInteger类在数字足够大时也会自动切换到Karatsuba或更高级的乘法算法。