大数相乘

大数相乘

大整数乘法，就是乘法的两个乘数比较大，最后结果超过了整形甚至长整形的最大范围，此时如果需要得到精确地结果，常规的乘法就不能得到正确的结果了。此时需要算法思想了，对，就是分治算法，将乘数“分割“，将大整数计算转换为小整数计算。

咱先来个小点的数乘法，然后逐步找出大数乘法的解法：

1、 一位乘法就是乘法口诀，没什么可说的。

2、 说说2位乘法??? 12*23 = 408 分割成一位乘法，满1位也就是到10就进位

1??????2

? ?X ?3?? 4

????? 4?? 8

??3?? 6???

? 4?? 0?? 81

? 接下来就是找规律，1*3（1*4+2*3）2*4 = 3(10)8，可以发现，括号中的10已满10，需要进1，而3加1，正好为4，所以最后结果为：408；

换句话说AB*CD = AC(AD + BC)BD . 注意括号两边是拼接起来，不是相乘

3、 接下来验证4位乘法

1??????2? 3? 4

? 5? 6?7? 8

?????? 9?? 8?7? 2

???? 8? 6?3? 8

? 7? 4?0? 4

6? 1? 7? 0??????????

7? 0? 0?6? 6? 5? 2

?

A=12,B=34,C=56,D=78?????

AC(AD + BC)BD

AC = 672,AD + BC = 2840,BD = 2652

4位分割后变成2位数乘法，所以满2位需要进位，也就是到100就进位。

从低位开始BD满两位进位，低位为52，进位26,? 2840+26=2866， 2866剩下66需要进位28， 672+28=700.? 所以最终结果拼接起来就是7006652

?

规律出来了AB*CD =AC(AD + BC)BD

接下来就是利用分治思想，利用递归算法进行计算实现、

大致思路分为如下：

a、 如果两个整数的位数小于等于4位，可以计算出结果

b、 如果X、Y两个数位数不用，以最长的为准，短的前面补0，使位数相同都为n

c、? 将大数X、Y分割为位数是n/2的数，分别为A、B、C、D

d、 将A、B、C、D递归调用第一步，直到分割为可以计算的4位数，从而得到结果

(高位)AC,(中位)AD,(中位)BC,(低位)BD

e、 判断BD是否有进位bd,保留位为BD’,?如果有则AD+BC+bd为中位abcd,判断abcd是否有进位abcd‘、保留位是ABCD’，如果有则高位为AC+abcd’.

f、?? 最后将结果拼接起来就是AC+abcd’+ABCD’+BD’。

?? 下面附上Java代码：

?

import java.io.BufferedInputStream;

import java.util.Scanner;

import java.util.regex.Matcher;

import java.util.regex.Pattern;

?

public classMain {

?

??? public static void main(String[] args) {

?

??????? // 正则表达式：不以0开头的数字串

??????? Stringpat = "^[1-9]d*$";

??????? Patternp = Pattern.compile(pat);

?

??????? System.out.println("请输入大数A(不以0开头的正整数)");

??????? Scannerscanner = newScanner(newBufferedInputStream(System.in));

??????? StringA = scanner.nextLine();

??????? Matcherm = p.matcher(A);

??????? if (!m.matches()) {

??????????? System.out.println("输入不合法");

??????????? return;

??????? }

?

??????? System.out.println("请输入大数B(不以0开头的正整数)");

??????? scanner= newScanner(newBufferedInputStream(System.in));

??????? StringB = scanner.nextLine();

??????? m= p.matcher(B);

??????? if (!m.matches()) {

??????????? System.out.println("输入不合法");

??????????? return;

??????? }

?

??????? System.out.println(A + "*" + B + "="

??????????????? +bigIntMultiply(A,B,Math.max(A.length(),B.length())));

?

??? }

?

??? /**

??? ?* @param A

??? ?*???????????大数A

??? ?* @param B

??? ?*???????????大数B

??? ?* @param len

??? ?*???????????要保证len是A,B长度的最大值

??? ?* @return最终相乘结果

??? ?*/

??? private static StringbigIntMultiply(String X,String Y,int len) {

?

??????? // 最终返回结果

??????? String str = "";

???????

??????? // 保证A,B长度为最长一个的长度，短的前面补0

??????? X= formateNumber(X,len);

??????? Y= formateNumber(Y,len);

?

??????? // 如果长度小于4位，直接计算

??????? if (len <= 4) {

??????????? return "" + (Integer.parseInt(X)* Integer.parseInt(Y));

??????? }

?

??????? // 分割X,Y

??????? int len1 = len / 2;

??????? int len2 = len - len1;

??????? StringA = X.substring(0,len1);

??????? StringB = X.substring(len1);

??????? StringC = Y.substring(0,len1);

??????? StringD = Y.substring(len1);

?

??????? // 递归，逐步分割

??????? int lenM = Math.max(len1,len2);

??????? StringAC = bigIntMultiply(A,C,len1);

??????? StringAD = bigIntMultiply(A,D,lenM);

??????? StringBC = bigIntMultiply(B,lenM);

??????? StringBD = bigIntMultiply(B,len2);

?

??????? // AC(AD+BC)BD公式

??????? // 先看BD结果，以及是否有进位，用String[0]数组保存原位，String[1]保存进位

??????? StringsBD[] = dealString(BD,len2);

?

??????? // 计算(AD+BC)的结果

??????? StringADBC = addition(AD,BC);

????????

??????? //（AD+BC）加上BD的进位

??????? if (!"0".equals(sBD[1])){

??????????? ADBC= addition(ADBC,sBD[1]);

??????? }

???????

??????? // 得到ADBC的进位

??????? String[] sADBC = dealString(ADBC,lenM);

?

??????? // AC加上ADBC的进位

??????? AC = addition(AC,sADBC[1]);

?

??????? // 最终结果

??????? str = AC + sADBC[0] + sBD[0];

?

??????? return str;

??? }

?

??? private static String addition(Stringad,String bc) {

??????? Stringstr = "";

??????? // 两个字符串长度要相同

??????? int lenM = Math.max(ad.length(),bc.length());

??????? ad= formateNumber(ad,lenM);

??????? bc= formateNumber(bc,lenM);

?

??????? // 安位加，进位保存在flag中

??????? int flag = 0;

?

??????? for (int i = lenM - 1; i >=0; i--) {

??????????? int t = flag + Integer.parseInt(ad.substring(i,i + 1))

?????????????????? +Integer.parseInt(bc.substring(i,i + 1));

?

??????????? if (t > 9) {

??????????????? flag= 1;

??????????????? t= t - 10;

??????????? }else{

??????????????? flag= 0;

??????????? }

?

??????????? str= str + t + "";

??????? }

?

??????? if (flag != 0) {

??????????? str= ""+ flag + str;

??????? }

??????? return str;

??? }

?

??? private static String[]dealString(String ac,int len) {

??????? // 默认不进位，str[1]进位上面赋值为0

??????? Stringstr[] = { ac,"0"};

?

??????? if (ac.length() <= len){

??????????? ac= formateNumber(ac,len);

??????????? str[0]= ac;

??????? }else{

??????????? int lenPre = ac.length() -len;

??????????? str[0]= ac.substring(lenPre);

??????????? str[1]= ac.substring(0,lenPre);

??????? }

?

??????? return str;

??? }

?

??? private static StringformateNumber(String x,int len) {

??????? while (x.length() < len) {

??????????? x= "0"+ x;

??????? }

??????? return x;

??? }

?

}