copy.java

大整数相乘

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

/**
 * @author Shenjun
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
public class copy {
	/*
	/**
	 * @param b
	 * @param n
	 * @return
	 */
	public BigNumber multiN(BigNumber b,int n) {
		long beforeTime = System.currentTimeMillis();
		if (n > 10 || n < 0)
			return null;
		BigNumber result = new BigNumber(false);
		int i, s;
		increment = 0;
		int size=b.getSize();
		for (i = 0; i < size; i++) {
			s = (b.get(i) * n + increment) % 10;
			result.addToTail(s);
			//result.addToTail((byte) s);
			increment = (b.get(i) * n + increment) / 10;
		}

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

	}
	
	
	
	/**
	 * @param b1
	 * @param b2
	 * @return
	 */
	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 m1
	 * @param m2
	 * @return
	 */
	public BigNumber multiBigNumAdvance(BigNumber m1,BigNumber m2){
		long beforeTime = System.currentTimeMillis();
		numList[0]=new BigNumber(false);
		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();
			}
		BigNumber result=new BigNumber(false);
		BigNumber tempResult=new BigNumber(false);
		int tempSize=m2.getSize();
		for(int i=0;i<tempSize;i++){
			try {
				tempResult=(BigNumber) numList[m2.get(i)].clone();
			} catch (CloneNotSupportedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			for(int j=0;j<i;j++)
				//tempResult.addToHead(0);
				tempResult.addToHead((byte) 0);
			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("Total Time of advance multi:"+time);
	return result;
	}
	
	/**
	 * @param m1
	 * @param m2
	 * @return
	 */
	public BigNumber multiBigNum(BigNumber m1,BigNumber m2){
		long beforeTime=System.currentTimeMillis();
		
		
		BigNumber result=new BigNumber(false);
		BigNumber tempResult=new BigNumber(false);
		int tempSize=m2.getSize();
		for(int i=0;i<tempSize;i++){
			tempResult=multiN(m1,m2.get(i));
			for(int j=0;j<i;j++)
			tempResult.addToHead(0);
				//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("Total Time of norman multi  :"+time);debug=false;}
	return result;
	}
	
	/**
	 * @param b1
	 * @param b2
	 * @return
	 */
	public BigNumber diffBigNum(BigNumber b1,BigNumber b2)
	{
		long beforeTime = System.currentTimeMillis();
		BigNumber diff = new BigNumber(false);
		
		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 i, min;
		int s;
		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++) {
			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.addToTail(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.addToTail(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.addToTail(s);
			}
			
		}

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

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

	
	}
	
	/**
	 * @param m1
	 * @param m2
	 * @return
	 */
	public BigNumber multiBigNumSuper(BigNumber m1,BigNumber m2)
	{
	     int sizeOfm1=m1.getSize(),sizeOfm2=m2.getSize();
	     //if(sizeOfm1<=100&&sizeOfm2<=100)return multiBigNum(m1,m2);
	     long beforeTime=System.currentTimeMillis();
	     BigNumber w=new BigNumber(false)
		          ,x=new BigNumber(false)
				  ,y=new BigNumber(false)
				  ,z=new BigNumber(false)
				  ,wy=new BigNumber(false)
				  ,xz=new BigNumber(false)
				  ,wAddx=new BigNumber(false)
				  ,yAddz=new BigNumber(false)
				  ,wyAddxz= new BigNumber(false)
				  ,finalResult=new BigNumber(false)
				  ,temp=new BigNumber(false)
				  ,temp1=new BigNumber(false);
	     int pivot;
	     if(sizeOfm1>=sizeOfm2)pivot=sizeOfm2/2;
	     else pivot=sizeOfm1/2;
	     partition(m1,x,w,pivot);
	     partition(m2,z,y,pivot);
	     wy=multiBigNum(w,y);
	     xz=multiBigNum(x,z);//结果不正确？
	     
	     try {
			temp=(BigNumber) wy.clone();
			
		} catch (CloneNotSupportedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	   
	     mutliTen(wy,pivot*2);
	     finalResult=addBigN(wy,xz);
	     
	     wyAddxz=addBigN(temp,xz);
	     wAddx=addBigN(w,x);
	     yAddz=addBigN(y,z);
	     temp1=multiBigNum(wAddx,yAddz);
	     temp=diffBigNum(temp1,wyAddxz);
	     mutliTen(temp,pivot);
	     
	     finalResult=addBigN(finalResult,temp);
	     long afterTime=System.currentTimeMillis();
			long time=afterTime-beforeTime;
			 if(debug){debug=true;System.out.println("Total Time of super multi  :"+time);}
         return finalResult;	
	}
	
	
	/**
	 * @param m1
	 * @param m2
	 * @return
	 */
	public BigNumber multiBigNumSuperR(BigNumber m1,BigNumber m2)
	{
	     int sizeOfm1=m1.getSize(),sizeOfm2=m2.getSize();
	     if(sizeOfm1<=75||sizeOfm2<=75)return multiBigNumSuper(m1,m2);
	   
	     BigNumber w=new BigNumber(false)
		          ,x=new BigNumber(false)
				  ,y=new BigNumber(false)
				  ,z=new BigNumber(false)
				  ,wy=new BigNumber(false)
				  ,xz=new BigNumber(false)
				  ,wAddx=new BigNumber(false)
				  ,yAddz=new BigNumber(false)
				  ,wyAddxz= new BigNumber(false)
				  ,finalResult=new BigNumber(false)
				  ,temp=new BigNumber(false)
				  ,temp1=new BigNumber(false);
	     int pivot;
	     if(sizeOfm1>=sizeOfm2)pivot=sizeOfm2/2;
	     else pivot=sizeOfm1/2;
	     partition(m1,x,w,pivot);
	     partition(m2,z,y,pivot);
	     wy=multiBigNumSuperR(w,y);
	     xz=multiBigNumSuperR(x,z);//结果不正确？
	     
	     try {
			temp=(BigNumber) wy.clone();
			
		} catch (CloneNotSupportedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	   
	     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);
	     mutliTen(temp,pivot);
	     
	     finalResult=addBigN(finalResult,temp);
	     
         return finalResult;	
	}
	
	/**
	 * @param m
	 * @param n
	 */
	public void  mutliTen(BigNumber m,int n)
	{
		for(int i=1;i<=n;i++)
		m.addToHead(0);
	}
	public void partition(BigNumber m1,BigNumber firstHalf ,BigNumber secondHalf,int pivot)
	{
		int size=m1.getSize();
		if(size<=pivot||pivot==1)return;
		int i=0;
		
		for(;i<pivot;i++)
			firstHalf.addToTail(m1.get(i));
	    for(;i<size;i++)
	    	secondHalf.addToTail(m1.get(i));
	
	
	}
	public static void main(String[] args) {
	}
}