Java实现大整数乘法

1 问题描述

计算两个大整数相乘的结果。

2 解决方案

2.1 蛮力法

package com.liuzhen.chapter5;

import java.math.BigInteger;

public class BigNumber {

    /*

     * 参数A:进行乘法运算的大整数A，用字符串形式表示

     * 参数B：进行乘法运算的另一个大整数B，用字符串形式表示

     * 函数功能：以字符串形式返回A*B的结果

     */

    public String getMultiBigNumber(String A,String B){

        if(A.length() > B.length()){       //当B字符串长度小于Ａ时，在Ｂ字符串前补０，使得两个字符串长度一致

            char[] temp = new char[A.length()-B.length()];

            for(int i = 0;i < A.length() - B.length();i++)

                temp[i] = '0';

            B = String.valueOf(temp) + B;

        }

        if(A.length() < B.length()){      //当A字符串长度小于B时，在A字符串前补０，使得两字符串长度一致

            char[] temp = new char[B.length()-A.length()];

            for(int i = 0;i < B.length() - A.length();i++)

                temp[i] = '0';

            A = String.valueOf(temp) + A;

        }

        int len = A.length() + B.length();

        char[] arrayA = A.toCharArray();

        char[] arrayB = B.toCharArray();

        for(int i = 0;i < arrayA.length;i++)     //检查字符串A中是否有非数字的字符

            if(arrayA[i] < '0' || arrayA[i] > '9')

                return null;

        for(int i = 0;i < arrayB.length;i++)    //检查字符串B中是否有非数字的字符

            if(arrayB[i] < '0' || arrayB[i] > '9')

                return null;

        char[] result = new char[len];    //用于存放最终乘法运算结果，长度len表示A*B的最长长度

        for(int i = 0;i < len;i++)         //初始化字符数组result，各个元素均为'0'

            result[i] = '0';

        int countI = 0;       //用于计算当前B中已经和A中每个字符进行完乘法运算的字符个数

        for(int i = arrayB.length-1;i >= 0;i--){

            int tempB = arrayB[i] - '0';

            int countJ = 0;   //用于计算当前A中正在进行乘法运算的字符个数

            for(int j = arrayA.length - 1;j >= 0;j--,countJ++){

                int tempA = arrayA[j] - '0';

                int tempRe = (tempB * tempA) % 10;  //用于计算当前位置的数

                int tempResult = result[(len-1-countJ)-countI] - '0';  //当前位置已包含的结果

                tempResult += tempRe;

                //count--表示当前A字符串中进行乘法运算的字符位置，countI表示当前B字符串中进行乘法运算的字符位置

                //(count--)-countI则表示当前进行乘法运算两个数字结果的最低位的位置

                result[(len-1-countJ)-countI] = (char) (tempResult%10 + 48); //当前位置数最终结果

                int tempDi = tempB * tempA / 10 + tempResult / 10;       //用于计算进位

                for(int k = 1;tempDi > 0;k++){   //处理进位操作

                     //当前下第k个位置包含的结果

                    int tempResultK = result[(len-1-countJ)-countI-k] - '0';

                    tempResultK += tempDi;

                    result[(len-1-countJ)-countI-k] = (char) (tempResultK%10 + 48);

                    tempDi = tempResultK / 10;

                }

            }

            countI++;

        }

        return getNoneZeroString(result);

    }

    //去掉字符串前面的0

    public String getNoneZeroString(char[] result){

        int count = 0;

        for(int i = 0;i < result.length;i++){

            if(result[i] == '0')

                count++;

            else

                break;

        }

        char[] A = new char[result.length-count];

        for(int i = 0;i < result.length-count;i++)

            A[i] = result[count+i];

        return String.valueOf(A);

    }

    public static void main(String[] args){

        long t1 = System.currentTimeMillis();

        BigNumber test = new BigNumber();

        String A = "123456789123232342432423441345342523452534235443253254";

        String B = "987654322234242424332423414324532542354325235345435435";

        System.out.println("大整数A*B的结果："+test.getMultiBigNumber(A, B));

        BigInteger bigInteger1 = new BigInteger("123456789123232342432423441345342523452534235443253254");

        BigInteger bigInteger2 = new BigInteger("987654322234242424332423414324532542354325235345435435");

        bigInteger2 = bigInteger2.multiply(bigInteger1);

        System.out.println("验证后A*B的结果："+bigInteger2);

        long t2 = System.currentTimeMillis();

        System.out.println("耗时："+(t2-t1)+" 毫秒");

    }

}

运行结果：

大整数A*B的结果：121932631386721831198089710747298668585104317165230580938992491445929653074852215402191571860797295610655490

验证后A*B的结果：121932631386721831198089710747298668585104317165230580938992491445929653074852215402191571860797295610655490

耗时：4 毫秒