1.问题描述
求两个大数A、B乘积的准确结果
其中A和B均为100位以上的十进制整数
A和B的位数可以不相等
2.问题分析
(1)
100位以上的整数，用整数变量直接存储装不下
所以，中间运算时，牵扯到大数肯定当做字符串来存储
(2)
A和B直接乘操作肯定是操作不了，必须是分开来处理
可以二分法，将AB转换
A=A1*10^(n1/2) +A0 ----- n1为a的位数
B=B1*10^(n2/2)+B0 -----n2为b的位数
那么 AB={A110(n1/2)+A0}*{B1*10(n2/2)+B0}
化简得
A*B=
(A1*B1)*10^[(n1+n2)/2]
+(A1*B0)*10^(n1/2)
+(A0*B1)*10^(n2/2)
+(A0*B0)
那么就把
n1位的整数与n2位的整数相乘的问题转化为
1.四个`n1/2`位的整数和`n2/2`位的整数相乘
2.三次移位
3.四次“大数”加法
3.问题解决
(1)n1/2位的整数和n2/2位的大整数相乘
问题又回到了
原点——大整数相乘问题
问题的解决需要调用自身来解决——递归
(2)移位
移位相当于是在后边
补0
那么就在要移位的数（字符串）后面添加一定量的
0即可
(3)“大数”加法
因为中间操作的都是比较大的数，因此即使是中间值的相加，也是比较大的数，故要采用大数相加
大数相加 问题 参见 大数相加
4.代码实现
import java.math.BigInteger;
import java.util.Scanner;
import org.stone.stack.MyBigAdd;
/**
* @ClassName_MyBigIntegerMutiply
* @author_Stone6762
* @CreationTime_2016年10月22日 下午3:39:57
* @Description_ 大整数乘法A x B AB可以为不同的位数
* 采用的是： 分治的思想，二分
*/
public class MyBigIntegerMutiply1 {
/**
* @Description:未优化的大数相乘
* @param a
* @param b
* @return a*b={a1*10^(n1/2)+a0}*{b1*10^(n2/2)+b0}
*/
public static String Mutiply1(String a, String b)// 用字符串读入2个大整数
{
String result = "";
if (a.length() == 1 || b.length() == 1)// 递归结束的条件
//其中一个长度为1，另一个不一定
result = "" + Long.valueOf(a) * Long.valueOf(b);
else// 如果2个字符串的长度都 >= 2
{
//1.分割成 a1 a0 b1 b0
int lengthA0 = a.length() / 2;
int lengthA1=a.length()-lengthA0;
String a1 = a.substring(0, lengthA1); // 截取前一半的字符串(较短的一半)
String a0 = a.substring(lengthA1, a.length()); // 截取后一半的字符串
int lengthB0 = b.length() / 2;
int lengthB1=b.length()-lengthB0;
String b1 = b.substring(0, lengthB1);
String b0 = b.substring(lengthB1, b.length());
// * a*b=
// * (a1*b1)* 10^[(n1+n2)/2 ]
// * +(a1*b0)*10^(n1/2)
// * +(a0*b1)*10^(n2/2)
// * +(a0*b0)
//2.计算展开式中的乘法
String a1b1 = Mutiply1(a1, b1);
String a1b0 = Mutiply1(a1, b0);
String a0b1 = Mutiply1(a0, b1);
String a0b0 = Mutiply1(a0, b0);
//3.模拟移位
String resulta1b1 = a1b1;
for (int i = 0; i < lengthA0+lengthB0; i++) {
resulta1b1 += "0";
}
String resulta1b0 = a1b0;
for (int i = 0; i <lengthA0; i++) {
resulta1b0 += "0";
}
String resulta0b1 = a0b1;
for (int i = 0; i < lengthB0; i++) {
resulta0b1 += "0";
}
//4.大数相加
result = MyBigAdd.add(resulta1b1, resulta1b0);
result = MyBigAdd.add(result, resulta0b1);
result = MyBigAdd.add(result, a0b0);
}
return result;
}
/**
* @Description拿BigInteger自身大数相乘来判断自身算法的正确与否
* @param args
*/
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while (scan.hasNext()) {
String aString=scan.next();
String bString=scan.next();
BigInteger aBigInteger=new BigInteger(aString);
BigInteger bBigInteger=new BigInteger(bString);
String reslut1=aBigInteger.multiply(bBigInteger).toString();
String result2=Mutiply1(aString, bString);
System.out.println("标准答案： "+reslut1);
System.out.println("计算结果： "+result2);
System.out.println("结果是否正确： "+reslut1.equals(result2));
}
}
}
5.缺点
1. A和B的位数可以不相同
但是相差不能太大，不能超过long的范围
2.时间复杂度和空间复杂度比较高，没有优化
6.更简单大数相乘与大数相加
java 类库自带 BigInteger和BigDecimal可以处理大整数和大浮点数
其中有处理相加和相乘的函数
如果仅仅是为了处理大数的相加和相乘，而不是为了研究，可以直接调用其封装好的函数即可
（1）调用java类库的大数相加
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while (scan.hasNext()) {
String aString=scan.next();
String bString=scan.next();
BigInteger aBigInteger=new BigInteger(aString);
BigInteger bBigInteger=new BigInteger(bString);
String resultString=aBigInteger.add(bBigInteger).toString();
System.out.println("a加上b等于 "+resultString);
}
}
（2）调用java类库的大数相乘
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while (scan.hasNext()) {
String aString=scan.next();
String bString=scan.next();
BigInteger aBigInteger=new BigInteger(aString);
BigInteger bBigInteger=new BigInteger(bString);
String reslut1=aBigInteger.multiply(bBigInteger).toString();
System.out.println("a乘以b等于 "+reslut1);
}
}
欢迎一起讨论大数相乘的优化问题
网友评论