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位二進制數(shù)與1位二進制數(shù)相乘，則可以直接計算 */
		if (X.compareTo(BigInteger.ONE)<=0
			|| Y.compareTo(BigInteger.ONE)<=0)
		{
			Count++;  /*累計做1位二進制乘法運算的次數(shù)*/
			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位二進制數(shù)與1位二進制數(shù)相乘，則可以直接計算 */
		if (X.compareTo(BigInteger.ONE)<=0
			|| Y.compareTo(BigInteger.ONE)<=0)	
		{
			Count++;  /*累計做1位二進制乘法運算的次數(shù)*/
			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，保存結(jié)果 */
		           BD=Multiply2(B,D),   /* 遞歸計算B*D，保存結(jié)果 */
		           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計算乘法結(jié)果，并統(tǒng)計總共進行了多少次的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計算乘法結(jié)果，并統(tǒng)計總共進行了多少次的1位二進制乘法運算 */
		Count=0;
		System.out.print("Method 2:\nResult=");
		System.out.println(Multiply2(X,Y));
		System.out.println("Multiplications Count="+String.valueOf(Count));
	}
}
/* 
 * 運行結(jié)果：
 * 
 * 38456
 * Multiplication Count=25
 * 38456
 * Multiplication Count=10
 * 
 */