Karatsuba大数乘法

Karatsuba算法是一种快速相乘算法，它由俄罗斯数学家Anatolii Alexeevitch Karatsuba于1960年提出并于1962年发表。普通乘法的复杂度是n2，而Karatsuba算法的复杂度仅为3n^log3≈3n^1.585.

步骤

现有两个大数，x，y。
首先将x，y分别拆开成为两部分，可得x1，x0，y1，y0。他们的关系如下：
x = x1 * 10^m+ x0；
y = y1 * 10^m + y0。其中m为正整数，m < n，且x0，y0 小于 10^m。
那么 xy = (x1 * 10^m + x0)(y1 * 10^m + y0)
= z2 * 10^2m + z1 * 10^m + z0 ，其中：
z2 = x1 * y1；
z1 = x1 * y0 + x0 * y1；
z0 = x0 * y0。
此步骤共需4次乘法，但是由Karatsuba改进以后仅需要3次乘法。因为：
z1 = x1 * y0+ x0 * y1
z1 = (x1 + x0) * (y1 + y0) - x1 * y1 - x0 * y0，
=(x1 + x0) * (y1 + y0)-z2-z0
故z1 便可以由一次乘法及加减法得到。

实例

设x = 12345，y=6789，令m=3。那么有：
12345 = 12 * 1000 + 345；
6789 = 6 * 1000 + 789。
下面计算：
z2 = 12 * 6 = 72；
z0 = 345 * 789 = 272205；
z1 = (12 + 345) * (6 + 789) - z2 - z0 = 11538。
然后我们按照移位公式（xy = z2 * 10^(2m) + z1 * 10^(m) + z0）可得：
xy = 72 * 10002 + 11538 * 1000 + 272205 = 83810205。

源码

这里加减法需要用到BigInteger,因为数字位数足够长的话，用long型最终还是会越界，（不过过瘾的是在jdk8中BigInteger类里面就包含了Karatsuba算法。。。。算了算了，重在了解算法━━(￣ー￣*|||━━）

import java.math.BigInteger;
import java.util.Scanner;

public class Karatsuba {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String x = in.next();
		String y = in.next();
		in.close();
		BigInteger num1 = new BigInteger(x);
		BigInteger num2 = new BigInteger(y);
		String answer = Karatsuba(num1, num2).toString();
		System.out.println(answer);

	}

	/**
	 * 
	 * @param a
	 * @param b
	 * @return 返回a*b的结果
	 */
	public static BigInteger Karatsuba(BigInteger x, BigInteger y) {
		BigInteger num1 = x;
		BigInteger num2 = y;
		if (x.toString().length() < 9 || y.toString().length() < 9) {

			return num1.multiply(num2);
		}

		else {
			int halfN = Math.max(x.toString().length(), x.toString().length()) / 2;
			// 这里不能用字符串的分割，如123456789789456123*12, 12被分割肯定报错
			BigInteger[] a_b = num1.divideAndRemainder(BigInteger.valueOf(10).pow(halfN));
			BigInteger a = a_b[0]; // 商
			BigInteger b = a_b[1]; // 余数
			BigInteger[] c_d = num2.divideAndRemainder(BigInteger.valueOf(10).pow(halfN));
			BigInteger c = c_d[0];
			BigInteger d = c_d[1];
			BigInteger z2 = Karatsuba(a, c);// a*c              ，运用了分治
			BigInteger z1 = Karatsuba(b, d);// b*d
			BigInteger step1 = Karatsuba(a.add(b), c.add(d));
			BigInteger z3 = step1.subtract(z1.add(z2)); // (a + b) * (c + d) - z2 - z1
			return z2.multiply(BigInteger.valueOf(10).pow(2 * halfN)).add(z1)
					.add(z3.multiply(BigInteger.valueOf(10).pow(halfN)));
		}
	}
}