题目：使用分治算法实现两个大整数的相乘

实现算法：

public class Main {
    //核心算法
    public static long big_integer_multiplication(long num1, long num2) {
        //递归终止条件
        if(num1 < 10 || num2 < 10) return num1 * num2;

        // 计算拆分长度
        int size1 = String.valueOf(num1).length();
        int size2 = String.valueOf(num2).length();
        int half_N = Math.max(size1, size2) / 2;

        // 拆分为a, b, c, d
        long A = Long.valueOf(String.valueOf(num1).substring(0, size1 - half_N));
        long B = Long.valueOf(String.valueOf(num1).substring(size1 - half_N));
        long C = Long.valueOf(String.valueOf(num2).substring(0, size2 - half_N));
        long D = Long.valueOf(String.valueOf(num2).substring(size2 - half_N));

        // 计算z2, z0, z1, 此处的乘法使用递归
        long z2 = big_integer_multiplication(A, C);
        long z0 = big_integer_multiplication(B, D);
        long z1 = big_integer_multiplication((A + B), (C + D)) - z0 - z2;

        return (long)(z2 * Math.pow(10, (2*half_N)) + z1 * Math.pow(10, half_N) + z0);
    }

    // 测试
    public static void main(String[] args) {
        System.out.println(big_integer_multiplication(1234,4567)); //True
        System.out.println("------------------------------------");
        System.out.println(big_integer_multiplication(123456789,987654321)); //True
        System.out.println("------------------------------------");
        System.out.println(big_integer_multiplication(12345,1234)); //True
    }
    
}

参考资料：

• 维基百科：Multiplication algorithm
• 大数乘法，在算法上，主要有几种思路？
• 华为OJ机试题目：两个大整数相乘(纯C语言实现两个大整数相乘，两种方法实现大数相乘)
• 算法理解 — 大数相乘问题
• KaraTsuba乘法 — 高效的大数乘法
• Karatsuba Multiplication Algorithm – Python Code
• Toom-Cook 3-Way Multiplication from GMP Documentations
• 大数相乘(from滴答滴答百度空间)
• 大整数运算
• Java的BigInteger的乘法运算是用什么算法实现的？