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

首先在这里声明,请原谅我,各位伙计,我的大整数乘法并不是真正意义的大整数乘法,因为采用了int保存,并且对位数还有限制,必须实2的幂(2位4位能正常计算)。没有

实现负数的运算。本程序采用Java语言实现(比较好处理字符串),如果想要实现负数的话可以先将符号位提取,判断结果是正还是负,最后在连接两个正数相乘的结果。我

将提取正负号的代码注释了。

原理如下,时间复杂度为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 license header, choose License Headers in Project Properties.
 * 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
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞