# 用分治算法编程实现两个n位十进制大整数的乘法运算

`原理如下，时间复杂度为O(nlog3) = O(n1.59)`
```MULT(X，Y，n); //X和Y为2个小于2n的整数，返回结果为X和Y的乘积XY
S=SIGN(X)*SIGN(Y); {S为X和Y的符号乘积}
X=ABS(X);
Y=ABS(Y); {X和Y分别取绝对值}
if (n==1) {
if (X=1)and(Y=1) ```
```          return(S)
else ```
```          return(0)
}
else {
A:=X的左边n/2位;
B:=X的右边n/2位;
C:=Y的左边n/2位;
D:=Y的右边n/2位;
ml:=MULT(A,C,n/2);
m2:=MULT(A-B,D-C,n/2);
m3:=MULT(B,D,n/2);
S:=S*(m1*2n+(m1+m2+m3)*2n/2+m3);
return(S);
}```
`代码如下`
``````<pre name="code" class="html">/*
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package arithmetic.practice.one;

import java.util.Scanner;

/**
*
* @author WL-PC
*/
public class BigNumber {

String bigNumber1;
String bigNumber2;
String n;
//输入值
public void printf(){
Scanner scanner = new Scanner(System.in);
System.out.println("请输入位数");
n = scanner.nextLine();
System.out.println("请输入大整数1：");
bigNumber1 = scanner.nextLine();
System.out.println("请输入大整数2：");
bigNumber2 = scanner.nextLine();
//判断正负
//        if(bigNumber1.charAt(0) == '-' || bigNumber1.charAt(0) == '+'){
//            System.out.println("符号位   "+bigNumber1.charAt(0));
//            bigNumber1 = bigNumber1.substring(1);
//        }
//        if(bigNumber2.charAt(0) == '-' || bigNumber2.charAt(0) == '+'){
//            System.out.println("符号位   "+bigNumber2.charAt(0));
//            bigNumber2 = bigNumber2.substring(1);
//        }
//        System.out.println("大整数1取整   "+bigNumber1+" 大整数2取整  "+bigNumber1);
System.out.println("结果   "+bigNumber1+" * "+bigNumber2 +" = "+MULT(bigNumber1,bigNumber2,Integer.parseInt(n)));
}

//对大整数进行运算
public int MULT(String num1,String num2,int n){
int s = SIGN(num1)*SIGN(num2);
num1 = ABS(num1);
num2 = ABS(num2);
if(n == 1){
if(Integer.parseInt(num1) == 1 && Integer.parseInt(num2) == 1){
return (s);
}else {
return s*(Integer.parseInt(num1)*Integer.parseInt(num2));
}
}else{
String A = num1.substring(0, n/2);
String B = num1.substring(n/2);
String C = num2.substring(0, n/2);
String D = num2.substring(n/2);

int m1 = MULT(A,C,n/2);
int m2 = MULT(String.valueOf(Integer.parseInt(A)-Integer.parseInt(B)),String.valueOf(Integer.parseInt(D)-Integer.parseInt(C)),n/2);
int m3 = MULT(B,D,n/2);
s = (int) (s*(m1*Math.pow(10, n)+(m1+m2+m3)*Math.pow(10, n/2)+m3));

}
return s;
}

//去符号
public int SIGN(String num){
return num.charAt(0)=='-'?-1:1;
}

//返回绝对值
public String ABS(String num){
return num.charAt(0)=='-'?num.substring(1):num;
}

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
new BigNumber().printf();
}

}
``` 希望能对伙计们有用。谢谢，如果你有更好的建议，请提给我，共同进步。```
原文作者：文宇
原文地址: https://blog.csdn.net/u012577528/article/details/45078763
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。