karatsuba算法（大整数乘法）
/**
* Karatsuba乘法
*/
public static BigInteger karatsuba(BigInteger num1, BigInteger num2) {
//递归终止条件
if (num1.toString().length() < 10 || num2.toString().length() < 10) return num1.multiply(num2);
//计算拆分长度
int size1 = String.valueOf(num1).length();
int size2 = String.valueOf(num2).length();
int halfN = Math.max(size1, size2) / 2;
//拆分为a，b，c，d
BigInteger a = new BigInteger(num1.toString().substring(0, size1 - halfN));
BigInteger b = new BigInteger(num1.toString().substring(size1 - halfN));
BigInteger c = new BigInteger(num2.toString().substring(0, size2 - halfN));
BigInteger d = new BigInteger(num2.toString().substring(size2 - halfN));
BigInteger ac = karatsuba(a, c);
BigInteger bd = karatsuba(b, d);
BigInteger ad_add_bc = karatsuba((a.add(b)), (c.add(d))).subtract(a.multiply(c)).subtract(b.multiply(d));
return (BigInteger) (a.multiply(c).multiply(BigInteger.valueOf((long) Math.pow(10, 2 * halfN)))
.add(ad_add_bc.multiply(BigInteger.valueOf((long) Math.pow(10, halfN)))))
.add(bd);
}
/**
* Karatsuba乘法
*/
public static long karatsuba1(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 halfN = Math.max(size1, size2) / 2;
/* 拆分为a, b, c, d */
long a = Long.valueOf(String.valueOf(num1).substring(0, size1 - halfN));
long b = Long.valueOf(String.valueOf(num1).substring(size1 - halfN));
long c = Long.valueOf(String.valueOf(num2).substring(0, size2 - halfN));
long d = Long.valueOf(String.valueOf(num2).substring(size2 - halfN));
// 计算ac, bd, ad_add_bc, 此处的乘法使用递归
long ac = karatsuba1(a, c);
long bd = karatsuba1(b, d);
long ad_add_bc = karatsuba1((a + b), (c + d)) - bd - ac;
return (long) (ac * Math.pow(10, (2 * halfN)) + ad_add_bc * Math.pow(10, halfN) + bd);
}