大整数的乘法

             通常，在分析算法的计算负责性时，都将加法和乘法运算当做基本运算来处理，即将执行一次加法或乘法运算所需的计算时间，当做一个仅取决于计算机硬件处理速度的常数。这个假定仅在参加运算的整数能在计算机硬件对整数的表示范围内直接处理时，才是合理的，然而，在某些情况下，要处理很大的整数，它无法再计算机硬件能直接表示的整数范围内进行处理，若用浮点数表示它，则只能近似地表示它的大小，计算结果中的有效数字也受到限制。若要精确地表示大整数并在计算结果中要求精确地到所有位数上的数字，就必须用软件的方法来实现大整数的算术运算。

             设X和Y都是n位的二进制整数，现在要计算它们的乘积XY。可以用小学所学的方法来设计计算乘积XY的算法，但是这样做计算的步骤太多，效率较低。如果将每2个1位数的乘法或加法看做一步运算，那么这种方法要进行O(n∧2)步运算才能计算出乘积XY。下面用分治法来设计更有效地大整数乘积算法。

             将n位二进制整数X和Y都分为2段，每段的长为n/2位(为简单起见，假设n是2的幂)

                         

                                 n/2位  n/2位                             n/2位   n/2位 

                           X=      A       B                         Y=     C         D

            

           由此，x=A2∧n/2+B=C2∧n/2+D,X和Y的乘积为

                 XY=(A2∧n/2+B)(C2∧n/2+D)=AC2∧n+(AD+BC)2∧n/2+BD

           如果按此式计算XY，则必须进行4次n/2位整数的乘法(AC,AD,BC和BD)，以及3次不超过2n为的整数的加法(分别对应于式中的加号)，此外还要进行2次移位(分别对应于式中乘2∧n和乘2∧n/2)。所有这些加法和移位共用O(n)步运算，设T(n)是2个n位数相乘所需的运算总数，则有

 

                                 O(1)                       n=1

                    T(n) =   4T(n/2)+O(n)          n>1

           由此可得T(n)=O(n∧2).因此，直接用此式来计算X和Y的乘积并不比小学生的方法有效。要想改进算法的计算复杂性，必须减小乘法次数，下面把XY写成另一种形式

                     XY=AC2∧n+((A-B)(D-C)+AC+BD)2∧n/2+BD

           此式看起来似乎更复杂，但它需要3次n/2位整数的乘法(AC,BD和(A-B)(D-C))，6次加，减法和2次移位，由此可得

                                O(1)                        n=1

                    T(n) =   3T(n/2)+O(n)          n>1

           容易求得其解为T(n)=O(n∧log3)=O(n∧1.59)。这是一个较大的改进。 

 

Demo

 

 

package Recursive;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

public class Large_integer_multiplication extends JFrame
{
	 /*
	 * 大整数的乘法
	 */
	private static final long serialVersionUID = 1494093793012534795L;
	private JTextField inputField1, inputField2;
	 private JTextArea resultArea;
	 private JLabel inputLabel1, inputLabel2, resultLabel;
	 private JButton EnterButton, resetButton;

	 public long firstNum;
	 public long secondNum;
	 public long result;
	 
	 public String firstStr;
	 public String secondStr;
	 
	 public int firstLen;
	 public int secondLen;

public Large_integer_multiplication()
{
	  super("Big Integer Multiply!");
	  
	  Container container = getContentPane();
	  
	  container.setLayout(new FlowLayout());
	  
	  inputLabel1 = new JLabel("Enter the first Number :");
	  container.add(inputLabel1);
	  
	  inputField1 = new JTextField(20);
	  container.add(inputField1);
	  
	  inputLabel2 = new JLabel("Enter the second Number :");
	  container.add(inputLabel2);
	  
	  inputField2 = new JTextField(20);
	  container.add(inputField2);
	  
	   
	  EnterButton = new JButton("Enter    To    Get    Result   ");
	  container.add(EnterButton); 
	  EnterButton.addActionListener(
	  new ActionListener(){
	  public void actionPerformed(ActionEvent e){
	  bigIntMulResult();
	    }
	    }
	    );
	  
	  resetButton = new JButton("Reset    All    Text    Content   ");
	  container.add(resetButton);
	  resetButton.addActionListener(
	  new ActionListener(){
	  public void actionPerformed(ActionEvent e){
	  resetApplication();
	    }
	    }
	    );
	  
	  resultLabel = new JLabel("The result is :");
	  container.add(resultLabel);
	  
	  resultArea = new JTextArea(5,30);
	  resultArea.setEditable(false);
	  container.add(new JScrollPane(resultArea));
	  
	  setSize(450,300);
	  setVisible(true);
	  
	  
	 }
	 
	 /**
	  * Large_integer_multiplication() is to get the result an display the result in 
	  * the interface.
	  *
	  */
	 public void bigIntMulResult(){
	  firstStr = inputField1.getText();
	  firstLen = firstStr.length();
	  
	  secondStr = inputField2.getText();
	  secondLen = secondStr.length();
	  
	  firstNum = Long.parseLong(firstStr);
	  secondNum = Long.parseLong(secondStr);
	  
	  long firNumPart1 , secNumPart1 , firNumPart2, secNumPart2;
	  int tag = 0;
	  
	  if(firstNum != Math.abs(firstNum)){
	   firstNum = Math.abs(firstNum);
	   tag += 1;
	  }
	  if(secondNum != Math.abs(secondNum)){
	   secondNum = Math.abs(secondNum);
	   tag += 1;
	  }
	  
	  firNumPart1 = firstNum / power(firstLen/ 2);
	  firNumPart2 = firstNum % power(firstLen/ 2); 
	  
	  secNumPart1 = secondNum / power(secondLen/ 2);
	  secNumPart2 = secondNum % power(secondLen/ 2);
	  
	  long part1, part2 , part3;
	  long part4, part5;
	  
	  part1 = firNumPart1 * secNumPart1;
	  
	  part2 = firNumPart2 * secNumPart2;
	  
	  part3 = (firNumPart1 - firNumPart2) * (secNumPart2 - secNumPart1) + part1 + part2 ;
	  
	  part4 = firNumPart1 * secNumPart2;
	  
	  part5 = firNumPart2 * secNumPart1;
	  
	  if((firstLen + secondLen) > 18){
	   resultArea.setText("the result is : \n" + part1 + "multiply 10 power " + (firstLen /2 + secondLen/ 2) + "\n ADD " + part4  + " multiply 10 power " + 
	     (firstLen/ 2) +"\n ADD " + part5 + " multiply 10 power " + (secondLen/ 2) + "\n ADD " + part2);
	  }
	  else if(firstLen == secondLen){
	   result = part1 * power(secondLen) + part2 + part3 * power(secondLen/ 2);
	   if(tag % 2 == 1){
	    result = 0 - result;
	   }
	   resultArea.setText(""+ result );
	  }
	  else{
	   result = part1 * power(firstLen /2 + secondLen/ 2) + part2 + part4 * power(firstLen/ 2) + part5 *power(secondLen/ 2);
	   if(tag % 2 == 1){
	    result = 0 - result;
	   }
	   resultArea.setText(""+ result );
	  }
	  result = firstNum * secondNum;
	  
	 }

	 /**
	  * power() is to get the result of 10 multiply 10 for n times
	  * @param n
	  * @return powerN
	  */
	 
	 public long power( int n){
	  long powerN = 1;
	  for(int i = 0; i < n; i++)
	   powerN *= 10;
	  return powerN;
	 } 
	 
	 /**
	  * reset the interface text field.
	  *
	  */
	 
	 public void resetApplication(){
	  inputField1.setText("");
	  inputField2.setText("");
	  resultArea.setText("");
	  
	 }
	 
	 /**
	  * application entrance.  
	  * * @param args
	  */
	 
	 public static void main(String args[]){
	 Large_integer_multiplication application = new Large_integer_multiplication();
     application.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
	 	}
	}