bigintmutiply.java

大整数乘法的分治法源码

 
import javax.swing.JOptionPane;
 /*import java.math.*;*/
public class Bigintmutiply{
  public static void main(String[] args){
    String sx=JOptionPane.showInputDialog(null,"enter a number",
              "example 2.1 output(int)",JOptionPane.QUESTION_MESSAGE);
    String sy=JOptionPane.showInputDialog(null,"enter a number",
              "example 2.1 output(int)",JOptionPane.QUESTION_MESSAGE);
   /*int x=Integer.parseInt(sx);
    int y=Integer.parseInt(sy);*/
    int xlen=sx.length();
    char[] csx=new char[xlen];
    sx.getChars(0,xlen,csx,0);
   
    int ylen=sy.length();
    char[] csy=new char[ylen];
    sy.getChars(0,ylen,csy,0);
    
    long x=0;
    long y=0;
    for(int i=0,j=xlen-1;i<xlen&&j>=0;i++,j--)
           if(csx[i]=='1') x+=pow(2,j);
    for(int i=0,j=ylen-1;i<ylen&&j>=0;i++,j--)
           if(csy[i]=='1') y+=pow(2,j); 
   /*  System.out.println("x="+x);
    * System.out.println("y="+y);
    System.out.println("x*y="+muti(x,y,xlen));*/
    JOptionPane.showMessageDialog(null,"x="+x+" "+"y="+y+"  "+"x*y="+muti(x,y,xlen,ylen),
            "example 2.1output(int)",JOptionPane.INFORMATION_MESSAGE);
   
    
  }
   public static long muti(long x ,long y ,int m, int n) {
	  if(x==0||y==0) return 0;
	  if(m==1) return y;
	  if(n==1) return x;
	  long a,b,c,d;
	  a=x>>>m/2;
	  b=x-a*pow(2,m/2);
	  c=y>>>n/2;
	  d=y-c*pow(2,n/2);
      System.out.println(" "+a+" "+b+" "+c+" "+d);
	  /*JOptionPane.showMessageDialog(null," "+a+", "+b+" ,"+c+" ,"+d,
	            "example 2.1output(int)",JOptionPane.INFORMATION_MESSAGE);*/
	  return pow(2,(n+m)/2)*muti(a,c,m/2,n/2)+muti(a,d,m/2,n/2)*pow(2,m/2)+muti(b,c,m/2,n/2)*pow(2,n/2)+muti(b,d,m/2,n/2);
   }
   public  static long pow(int i,int j ){
	  long w=1;
	   for(int n=0;n<j;n++)
		    w*=i;
	   return w;
   }
  
}