multiplicate.java

大整数相乘

import javax.swing.text.Position;

/*
 * Created on 2006-11-12
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 */

/**
 * @author Shenjun
 *
 * 
 * 
 */
public class Multiplicate {
    
	/**
	 * 
	 */
	public Multiplicate(){
		
		
	}
	
	
	/**
	 * 实现两个大整数的相加并返回结果
	 * @param b1 加数
	 * @param b2 被加数
	 * @return   结果
	 */
	public BigNumber addBigN(BigNumber b1,BigNumber b2) {
		///long beforeTime = System.currentTimeMillis();
		BigNumber sum; 
		increment=0;
		int i, min;
		int s;
		if(b1.getCapacity()>=b2.getCapacity())sum= new BigNumber(false,b1.getCapacity());
		else sum= new BigNumber(false,b2.getCapacity());
		int b1Size=b1.getSize();
		int b2Size=b2.getSize();
		boolean isMinSize;
		if (b1Size >= b2Size) {
			min = b2Size;
			isMinSize = false;
			
		} else {
			min = b1Size;
			isMinSize = true;
			
		}

		for (i = 0; i < min; i++) {
			s = (b1.get(i) + b2.get(i) + increment) % 10;
			//s = (byte) ((get(i) + b2.get(i) + increment) % 10);
			sum.addToNums(i,s);
			
			increment = (b1.get(i) + b2.get(i) + increment) / 10;
		}

		if (isMinSize) {
			for (; i < b2Size; i++) {
				s = (b2.get(i) + increment) % 10;
				//s = (byte) ((b2.get(i) + increment) % 10);
				sum.addToNums(i,s);
				increment = (b2.get(i) + increment) / 10;
			}
			if (increment == 1)
				//sum.addToTail((byte) 1);
			    sum.addToNums(i,1);
		} else {
			for (; i <b1Size; i++) {
				s = (b1.get(i) + increment) % 10;
				//s = (byte) ((get(i) + increment) % 10);
				sum.addToNums(i,s);
				increment = (b1.get(i) + increment) / 10;

			}
			if (increment == 1)
				sum.addToNums(i,1);
			// sum.addToTail((byte) 1);
		}

		//long afterTime = System.currentTimeMillis();
		//long time = afterTime - beforeTime;

		//if(debug)System.out.println("Total Time of Add BigNum :"+time);
		return sum;

	}
	
	
	/**
	 * 实现两个数的差
	 * @param b1 被减数
	 * @param b2 减数
	 * @return 结果
	 */
	public BigNumber diffBigNum(BigNumber b1,BigNumber b2)
	{
		long beforeTime = System.currentTimeMillis();
		
		BigNumber diff;
		int b1Size=b1.getSize();
		int b2Size=b2.getSize();
		if (b1Size >= b2Size) {
			
			
			
			diff= new BigNumber(false,b1.getCapacity());
		} else {
			
			

		}
		 diff= new BigNumber(false,b2.getCapacity());
		increment=0;
		if(Compare(b1,b2)==-1){
			
				BigNumber temp= b1;
				b1= b2;
				b2=temp;
				
				//BigNumber temp=(BigNumber) b1;
				//b1=(BigNumber) b2;
				//b2=(BigNumber)temp.clone();
			
			
			diff.setPositive(false);
		}
		int min, i;
		int s;
		boolean isMinSize;
		 b1Size=b1.getSize();
		 b2Size=b2.getSize();
		if (b1Size >= b2Size) {
			min = b2Size;
			isMinSize = false;
			
		} else {
			min = b1Size;
			isMinSize = true;

		}
		

		for (i = 0; i < min; i++) {
			if(b1.get(i)-increment>=b2.get(i)){
			s = (b1.get(i) - b2.get(i) - increment) % 10;
			increment=0;
			}
			else {
				s=(b1.get(i)+10-b2.get(i)-increment);
				increment=1;
			}
			//s = (byte) ((get(i) + b2.get(i) + increment) % 10);
			diff.addToNums(i,s);
			
			
		}

		if (isMinSize) {
			for (; i < b2Size; i++) {
				if(b2.get(i)-increment>=0){
					s = ( b2.get(i) - increment) ;
				
					increment=0;
					}
					else {
						s=(b2.get(i)+10-increment);
						increment=1;
					}
				diff.addToNums(i,s);
			}
			
		} else {
			for (; i <b1Size; i++) {
				if(b1.get(i)-increment>=0){
					s = ( b1.get(i) - increment) ;
					
					increment=0;
					}
					else {
						s=(b1.get(i)+10-increment);
						increment=1;
					}
				diff.addToNums(i,s);
			}
			
		}

		long afterTime = System.currentTimeMillis();
		long time = afterTime - beforeTime;

		if(debug)System.out.println("Total Time of Add BigNum :"+time);
		return diff;

	
	}
	
	
	
	/**
	 * 实现两个数的比较
	 * @param b1 
	 * @param b2
	 * @return b1>b2->1 ,b1<b2->-1,b1=b2->0
	 */
	public int Compare(BigNumber b1,BigNumber b2)
	{
			int a = 0;
		if(b1.isPositive()&&!b2.isPositive())return a=1;
			if(!b1.isPositive()&&b2.isPositive())return a=-1;
			
			if(b1.isPositive()&&b2.isPositive()){
			    if(b1.getSize()>b2.getSize())return a=1;
			    else if(b1.getSize()<b2.getSize())return a=-1;
			         else 
			         {
			         	for(int i=b1.getSize()-1;i>=0;i--)
                        if(b1.get(i) >b2.get(i))return a=1;
                          else if(b1.get(i)<b2.get(i)) return a=-1;
			
			         	}
			
			}
			else
		    if(!b1.isPositive()&&!b2.isPositive())
			{
				 if(b1.getSize()>b2.getSize())return a=-1;
				    else if(b1.getSize()<b2.getSize())return a=1;
				         else 
				         {
				         	for(int i=b1.getSize()-1;i>=0;i--)
	                        if(b1.get(i) >b2.get(i))return a=-1;
	                          else if(b1.get(i)<b2.get(i)) return a=1;
				
				         	}
				
			
			}
		    return a;
	}
	
	
	/**
	 * 实现某个大整数与单位数相乘
	 * @param b 大整数
	 * @param n 单位数
	 * @return 大整数
	 */
	public BigNumber multiN(BigNumber b,int n) {
		//long beforeTime = System.currentTimeMillis();
		if (n > 10 || n < 0)
			return null;
		int size=b.getSize();
		//if(debug)System.out.println(size);
		BigNumber result = new BigNumber(false,size+1);
		int i, s;
		increment = 0;
		
		for (i = 0; i < size; i++) {
			s = (b.get(i) * n + increment) % 10;
			result.addToNums(i,s);
			//result.addToTail((byte) s);
			increment = (b.get(i) * n + increment) / 10;
		}

		if (increment!= 0)
			//result.addToTail((byte) 1);
			result.addToNums(i,increment);
		//long afterTime = System.currentTimeMillis();
		//long time = afterTime - beforeTime;
		//if(debug)System.out.println("Total Time of Mulit BigNum :"+time);
		return result;

	}
	
	
	/**
	 * 实现大整数乘以10，相当与左移某个数在低位补零
	 * @param m 大整数
	 * @param n 左移位数
	 */
	public BigNumber  mutliTen(BigNumber m,int n)
	{
		int oldSize=m.getSize();
		int newSize=oldSize+n;
		BigNumber result=new BigNumber(false,newSize);
		int copySize=oldSize-1;
		int position;
		for(position=newSize-1;copySize>=0;position--)
			{
			result.addToNums(position,m.get(copySize));
			copySize--;
			}
		result.setSize(newSize);
		return result;
	}
	
	/**
	 * 实现大整数乘以10，相当与左移某个数在低位补零，与上一个不同的是该实现的结果的capacity是以m的capacity而不是size值来定
	 * 这样做主要是用与递归是结果必须保证有空间用于移位
	 * @param m 大整数
	 * @param n 左移位数
	 */
	public BigNumber  mutliTenF(BigNumber m,int n)
	{
		int oldSize=m.getSize();
	
		BigNumber result=new BigNumber(false,m.getCapacity());
		int copySize=oldSize-1;
		int position;
		for(position=copySize+n;copySize>=0;position--)
			{
			result.addToNums(position,m.get(copySize));
			copySize--;
			}
		result.setSize(oldSize+n);
		return result ;
	}
	
	
	/**
	 * 实现将大整数m2复制到大整数m1中，不使用clone方法的原因是保证后面移位的空间，此时必须保证m1.capacity>m2.capacity
	 * @param m1
	 * @param m2
	 */
	public void copyFrom(BigNumber m1,BigNumber m2)
	{
		m1.setSize(0);
		int sizeOfm2=m2.getSize();
		
		int i;
		for(i=0;i<sizeOfm2;i++)
			m1.addToNums(i,m2.get(i));
		
	}
	
	/**
	 * 两个大整数相乘的最原始的算法。
	 * @param m1
	 * @param m2
	 * @return 乘积
	 */
	public BigNumber multiBigNum(BigNumber m1,BigNumber m2){
		long beforeTime=System.currentTimeMillis();
		
		int tempSize=m2.getSize();
		BigNumber result=new BigNumber(false,m1.getCapacity()+m2.getCapacity());
		BigNumber tempResult=new BigNumber(false,m1.getCapacity()+m2.getCapacity());
		
		for(int i=0;i<tempSize;i++){
			tempResult=multiN(m1,m2.get(i));
			tempResult=mutliTen(tempResult,i);
				//tempResult.addToHead((byte) 0);
			result=addBigN(tempResult,result);
		
		}
		long afterTime=System.currentTimeMillis();
		long time=afterTime-beforeTime;
		if(m1.isPositive()&&m2.isPositive())result.setPositive(true);
		else result.setPositive(false);
	    if(debug){System.out.println("一般算法所用时间:"+time);debug=false;}
	return result;
	}
	
	
	/**
	 * 两个大整数相乘的改进算法，构建乘法表
	 * @param m1
	 * @param m2
	 * @return 乘积
	 */
	public BigNumber multiBigNumAdvance(BigNumber m1,BigNumber m2){
		long beforeTime = System.currentTimeMillis();
	    
	    int sizeOfM1=m1.getSize();
	    BigNumber numList[]=new BigNumber[10];
		numList[0]=new BigNumber(false,sizeOfM1+1);
		try {
			numList[1]=(BigNumber) m1.clone();
		} catch (CloneNotSupportedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		for(int i=2;i<=9;i++)
			{
				numList[i]=multiN(m1,i);
			   // numList[i].print();
			}
		int tempSize=m2.getSize();
		BigNumber result=new BigNumber(false,m2.getCapacity()+m1.getCapacity());
		BigNumber tempResult=new BigNumber(false,m2.getCapacity()+m1.getCapacity());
		
		for(int i=0;i<tempSize;i++){
			copyFrom(tempResult,numList[m2.get(i)]);
			tempResult=mutliTenF(tempResult,i);
			
			result=addBigN(result,tempResult);
		
		}
		long afterTime=System.currentTimeMillis();
		long time=afterTime-beforeTime;
		if(m1.isPositive()&&m2.isPositive())result.setPositive(true);
		else result.setPositive(false);
	    System.out.println("乘法表算法所用时间:"+time);
	    return result;
	}
	
	
	
	/**
	 * 实现将m1从pivot位置断开形成两个大整数
	 * @param m1 原始的大整数 如12345
	 * @param firstHalf 前一部分结果 345
	 * @param secondHalf 后一部分结果12
	 * @param pivot 断开位置 如3
	 */
	public void partition(BigNumber m1,BigNumber firstHalf ,BigNumber secondHalf,int pivot)
	{
		int size=m1.getSize();
		if(size<=pivot)return;
		int i=0;
		
		for(;i<pivot;i++)
			firstHalf.addToNums(i,m1.get(i));
	    for(int j=0;i<size;i++,j++)
	    	secondHalf.addToNums(j,m1.get(i));
	
	
	}
	
	
	
	/**
	 * 两个大整数相乘的递归算法
	 * @param m1
	 * @param m2
	 * @return 乘积
	 */
	public BigNumber multiBigNumSuperR(BigNumber m1,BigNumber m2)
	{
	     int sizeOfm1=m1.getSize(),sizeOfm2=m2.getSize();
	     if(sizeOfm1<=16||sizeOfm2<=16)return multiBigNum(m1,m2);
	     int pivot;
	     if(sizeOfm1>=sizeOfm2){pivot=sizeOfm2/2;}
	     else {pivot=sizeOfm1/2;}
	     int rSize=sizeOfm1+sizeOfm2;
	     BigNumber w=new BigNumber(false,rSize)
		          ,x=new BigNumber(false,rSize)
				  ,y=new BigNumber(false,rSize)
				  ,z=new BigNumber(false,rSize)
				  ,wy=new BigNumber(false,rSize)
				  ,xz=new BigNumber(false,rSize)
				  ,wAddx=new BigNumber(false,rSize)
				  ,yAddz=new BigNumber(false,rSize)
				  ,wyAddxz= new BigNumber(false,rSize)
				  ,finalResult=new BigNumber(false,rSize)
				  ,temp=new BigNumber(false,rSize)
				  ,temp1=new BigNumber(false,rSize);
	     
	     partition(m1,x,w,pivot);
	     partition(m2,z,y,pivot);
	     wy=multiBigNumSuperR(w,y);
	     xz=multiBigNumSuperR(x,z);//结果不正确？
	     
	    
			
			copyFrom(temp,wy);
		
	   
	     wy=mutliTen(wy,pivot*2);
	     finalResult=addBigN(wy,xz);
	     
	     wyAddxz=addBigN(temp,xz);
	     wAddx=addBigN(w,x);
	     yAddz=addBigN(y,z);
	     temp1=multiBigNumSuperR(wAddx,yAddz);
	     temp=diffBigNum(temp1,wyAddxz);
	     temp=mutliTen(temp,pivot);
	     
	     finalResult=addBigN(finalResult,temp);
	     
         return finalResult;	
	}
	
	/**
	 * Comment for <code>numList</code>
	 */
	//private BigNumber numList[]=new BigNumber[10];
	/**
	 * 用于加法减法及乘法中的进位
	 */
	private static int increment=0;
	/**
	 * Comment for <code>debug</code>
	 */
	private static boolean debug=true;
	public static void main(String[] args) {
		
		if(args.length<2){
			System.out.println("Usage: java Multiplicate m n result");
			System.exit(0);
		}
		int m=0,n=0;
		if(Integer.parseInt(args[0])<0){
			System.out.println("the number of num can't be negative");
			System.exit(0);
		}
		else m=Integer.parseInt(args[0]);
		
		if(Integer.parseInt(args[1])<0){
			System.out.println("the number of num can't be negative");
			System.exit(0);
		}
		else n=Integer.parseInt(args[1]);
		
		//NumsProducer numP=new NumsProducer();
		//numP.produceNums("m.txt",m);
		//numP.produceNums("n.txt",n);
		System.out.println("Get the Big Num m!");
		BigNumber m1=new BigNumber("n.txt",true,n);
		
		m1.print();
		
		System.out.println("Get the Big Num n!");
		BigNumber m2=new BigNumber("m.txt",true,m);
		m2.print();
		BigNumber result=new BigNumber(false,m+n);
		Multiplicate multi=new Multiplicate();
		System.out.println("当位数是"+n+"位与"+m+"位的两个大整数相乘所用时间为：（单位：毫秒）");
		multi.multiBigNum(m1,m2);
		multi.multiBigNumAdvance(m1,m2);
		long beforeTime=System.currentTimeMillis();
		result=multi.multiBigNumSuperR(m1,m2);
		//result.print();
		long afterTime=System.currentTimeMillis();
		long time=afterTime-beforeTime;
		System.out.println("递规算法所用时间:"+time);
		if(args.length==3&&args[2]!=null)result.print(args[2]+".txt");
		//BigNumber m2=new BigNumber(true,50);
		//BigNumber m3=new BigNumber(false,50);
		//m2.print();
		
		//m.addBigN(m1,m2).print();
		//m.diffBigNum(m1,m2).print();
		//m.mutliTenF(m1,3).print();
		//m1.print();
		//m.copyTO(m2,m1);
		//m.partition(m1,m2,m3,1);
		 //m1.print();
		 //m2.print();
		// m3.print();
		/*
		BigNumber m1=new BigNumber(true,50);
		BigNumber m2=new BigNumber(true,500);
		
		Multiplicate multi=new Multiplicate();
		
		multi.multiBigNum(m1,m2).print();
		multi.multiBigNumAdvance(m1,m2).print();
		long beforeTime=System.currentTimeMillis();
		multi.multiBigNumSuperR(m1,m2).print();
		//result.print();
		long afterTime=System.currentTimeMillis();
		long time=afterTime-beforeTime;
		System.out.println("Total Time of Super multi R :"+time);
		
		//m1.print();
        //m2.print();
       // m3.print();
		*/
		
		
	}
}