大整数的乘法运算

通常，在分析一个算法的计算复杂性时，都将加法和乘法运算当作是基本运算来处理，即将执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。
?? 这个假定仅在计算机硬件能对参加运算的整数直接表示和处理时才是合理的。然而，在某些情况下，我们要处理很大的整数，它无法在计算机硬件能直接表示的范围内进行处理。若用浮点数来表示它，则只能近似地表示它的大小，计算结果中的有效数字也受到限制。若要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字，就必须用软件的方法来实现大整数的算术运算。
?? 请设计一个有效的算法，可以进行两个n位大整数的乘法运算。
参考一：

设X和Y都是n位的二进制整数，现在要计算它们的乘积XY。我们可以用小学所学的方法来设计一个计算乘积XY的算法，但是这样做计算步骤太多，显得效率较低。如果将每2个1位数的乘法或加法看作一步运算，那么这种方法要作O(n2)步运算才能求出乘积XY。下面我们用分治法来设计一个更有效的大整数乘积算法。
我们将n位的二进制整数X和Y各分为2段，每段的长为n/2位（为简单起见，假设n是2的幂）:

由此，X=A2^n/2+B，Y=C^2n/2+D。这样，X和Y的乘积为：

如果按式（1）计算XY，则我们必须进行4次n/2位整数的乘法(AC，AD，BC和BD)，以及3次不超过n位的整数加法（分别对应于式（1）中的加号），此外还要做2次移位（分别对应于式（1）中乘2^n和乘2^n/2）。所有这些加法和移位共用O（n）步运算。设T（n）是2个n位整数相乘所需的运算总数，则由式（1），我们有：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

（2）
由此可得T（n）=O（n2）。因此，用（1）式来计算X和Y的乘积并不比小学生的方法更有效。要想改进算法的计算复杂性，必须减少乘法次数。为此我们把XY写成另一种形式：

虽然，式（3）看起来比式（1）复杂些，但它仅需做3次n/2位整数的乘法（AC，BD和（A-B）（D-C）），6次加、减法和2次移位。由此可得：

（4）

用解递归方程的套用公式法马上可得其解为T(n)=O(nlog3)=O(n1.59)。

(未完待续，只实现了第一种复杂度的情况)

import java.util.Scanner;

public class DaShuChengFa {
	static int[] ix;
	static int[] iy;
	public static void main(String[] args) {
		System.out.println("输入两个二进制大数(位数为2的幂)：");
		Scanner input=new Scanner(System.in);
		String  x,y;
		char[] cx;
		char[] cy;
		x=input.nextLine();
		y=input.nextLine();
		ix=new int[x.length()];
		iy=new int[y.length()];
		cx=x.toCharArray();
		cy=y.toCharArray();
		for (int i = 0; i < cy.length; i++) {
			ix[i]=(int)cx[i]-48;
			iy[i]=(int)cy[i]-48;
		}
		System.out.println(cheng(0,cy.length));
	}

	public static int cheng(int num1,int num2,int l){
		if(l==1){
			return ix[num1]*iy[num2];
		}
		else{
			return (int) (cheng(num1,num2,l/2)*Math.pow(2,l)+
					(cheng(num1,num2+l/2,l/2)+cheng(num1+l/2,l/2))*Math.pow(2,l/2)+
					cheng(num1+l/2,l/2));
		}
	}
}