bigintmultiplication.java

大整数乘法例子代码 /* 递归边界

import java.math.*;

public class BigIntMultiplication {
	
	static long Count;
	
	/* 计算X是2的多少次幂，即计算(log(X)/log(2))+1 */
	public static int get_n(BigInteger X)
	{	
		int n=0;
		BigInteger two=new BigInteger("2");
		while (X.compareTo(BigInteger.ZERO)>0)
		{
			n++;
			X=X.divide(two);
		}		
		return n;
	}
	
	/* 第一种计算方法 */
	public static BigInteger Multiply1(BigInteger X,BigInteger Y)
	{
		/* 递归边界，如果是1位二进制数与1位二进制数相乘，则可以直接计算 */
		if (X.compareTo(BigInteger.ONE)<=0
			|| Y.compareTo(BigInteger.ONE)<=0)
		{
			Count++;  /*累计做1位二进制乘法运算的次数*/
			return X.multiply(Y);  /* return (X*Y) */
		}
		
		/* 计算n的值 */
		int n=get_n(X);
		
		/* 把X和Y拆分开来，令X=A*2^(n/2)+B, Y=C*2^(n/2)+D */
		BigInteger mod=BigInteger.ONE.shiftLeft(n/2); /* 左移位运算，mod = 1<<(n/2) */
		BigInteger A=X.divide(mod), B=X.remainder(mod),
		           C=Y.divide(mod), D=Y.remainder(mod);
		
		/* 计算XY=AC*2^n+(AD+CB)*2^(n/2)+BD */
		BigInteger a1=Multiply1(A,C).shiftLeft(n),  /* 计算A*C，再向左移n位 */
		           a21=Multiply1(A,D),      /* 递归计算A*D */      
		           a22=Multiply1(C,B),      /* 递归计算C*B */
		           a2=a21.add(a22).shiftLeft(n/2),  /*  计算a21+a22,再向左移n/2位 */
		           a3=Multiply1(B,D);      /* 递归计算B*D */
		BigInteger XY=a1.add(a2).add(a3);      /* XY=a1+a2+a3 */
		
		return XY;		
	}
	
	/* 第二种计算方法 */
	public static BigInteger Multiply2(BigInteger X,BigInteger Y)
	{	
		/* 递归边界，如果是1位二进制数与1位二进制数相乘，则可以直接计算 */
		if (X.compareTo(BigInteger.ONE)<=0
			|| Y.compareTo(BigInteger.ONE)<=0)	
		{
			Count++;  /*累计做1位二进制乘法运算的次数*/
			return X.multiply(Y);  /* return (X*Y) */
		}
		
		/* 计算n的值 */
		int n=get_n(X);
		
		/* 把X和Y拆分开来，令X=A*2^(n/2)+B, Y=C*2^(n/2)+D */
		BigInteger mod=BigInteger.ONE.shiftLeft(n/2);	/* 左移位运算，mod = 1<<(n/2) */	
		BigInteger A=X.divide(mod), B=X.remainder(mod),
		           C=Y.divide(mod), D=Y.remainder(mod);
		
		/* 计算XY=AC*2^n+((A-B)(D-C)+AC+BD)*2^(n/2)+BD */
		BigInteger AC=Multiply2(A,C),   /* 递归计算A*C，保存结果 */
		           BD=Multiply2(B,D),   /* 递归计算B*D，保存结果 */
		           a1=AC.shiftLeft(n),     /* a1=AC左移n位 */
		           a21=Multiply2(A.subtract(B),D.subtract(C)), /* a21=(A-B)(D-C) */		           		           
		           a2=a21.add(AC).add(BD).shiftLeft(n/2), /* a2=(a21+AC+BD)<<(n/2) */
		           a3=BD;
		BigInteger XY=a1.add(a2).add(a3);   /* XY=a1+a2+a3 */     
		
		return XY;
	}
	
	public static void main(String args[])
	{
		/* 计算示例: 11010001 * 10111000 （二进制表示） 
		 * 十进制表示为： 209 * 184    */
		BigInteger X=new BigInteger("209"),   /* X=11010001 */ 
		           Y=new BigInteger("184");   /* Y=10111000 */
		
		/* 用方法1计算乘法结果，并统计总共进行了多少次的1位二进制乘法运算 */
		Count=0;
		System.out.print("Method 1:\nResult=");
		System.out.println(Multiply1(X,Y));
		System.out.println("Multiplications Count="+String.valueOf(Count)+"\n");
		
		/* 用方法2计算乘法结果，并统计总共进行了多少次的1位二进制乘法运算 */
		Count=0;
		System.out.print("Method 2:\nResult=");
		System.out.println(Multiply2(X,Y));
		System.out.println("Multiplications Count="+String.valueOf(Count));
	}
}
/* 
 * 运行结果：
 * 
 * 38456
 * Multiplication Count=25
 * 38456
 * Multiplication Count=10
 * 
 */