大整数相乘java_大整数乘法—java实现

大整数相乘

参考博客：

https://blog.csdn.net/oh_maxy/article/details/10903929

https://blog.csdn.net/u010867294/article/details/77482306

大整数相乘，对于计算机来说，由于整数的范围存在限制，如果数值太大，则两个较大整数及其结果在表示时就将可能产生溢出。因此，对于两个大整数的乘法我们就需要将其转化为字符串来进行求解。

分治法实现大整数相乘—算法思想：

当我们输入两个大整数num1,num2,长度分别为n，m，计算机无法直接计算其结果，采用分而治之的思想，我们可以分别将两个数均分为四个部分，记作A，B，C，D，其中：

A为num1的前n/2,

B为num1的后n/2,

C为num2的前m/2

D为num2的后m/2

至此，我们有：

num1 * num2 = (A * 10^(n/2) + B) * (C * 10^(m/2) + D)= AC * 10实现代码：

import java.util.*;

import static java.util.Collections.reverse;

/**

* @author

* @date 2020/10/1 – 20:55

*/

public class DivideMultiply {

public static void main(String[] args) {

int aLen, bLen;

Scanner scanner = new Scanner(System.in);

System.out.println(“请输入一个长整数x:”);

String as = scanner.nextLine();

System.out.println(“请输入另一个长整数y:”);

String bs = scanner.nextLine();

aLen = as.length();

bLen = bs.length();

List an = new ArrayList<>();

List bn = new ArrayList<>();

List cn;

//数字存入集合

for (int i = 0; i < aLen; i++) {

an.add(as.charAt(i) – ‘0’);

}

for (int i = 0; i < bLen; i++) {

bn.add(bs.charAt(i) – ‘0’);

}

cn = divideMultiply(an, bn, 0, 0);

//求得结果显示

for (Integer i : cn) {

System.out.print(i);

}

}

//求大整数相乘

public static List divideMultiply(List an, List bn, int x, int y) {

int al = an.size();

int bl = bn.size();

int ax = x;

int by = y;

if (al == 1) { //当递归到存在数据长度为1的值时进行乘法运算，结束递归

return multiply(bn, an, x, y);

}

if (bl == 1) {

return multiply(an, bn, x, y);

}

x = x + al – al / 2;

y = y + bl – bl / 2;

List a = getList(an, 0, al / 2); //将大整数分为四个小整数

List b = getList(an, al / 2, al);

List c = getList(bn, 0, bl / 2);

List d = getList(bn, bl / 2, bl);

List ac = divideMultiply(a, c, x, y); //递归求得ac,ad,bc,cd的值

List ad = divideMultiply(a, d, x, by);

d = getList(bn, bl / 2, bl);

List bc = divideMultiply(b, c, ax, y);

b = getList(an, al / 2, al);

List bd = divideMultiply(b, d, ax, by);

return add(ac, ad, bc, bd);

}

//分治后两数相乘

public static List multiply(List an, List bn, int x, int y) {

List result = new ArrayList<>();

int len;

reverse(an);

for (int i = 0; i <= an.size(); i++) { //首先将相乘结果全部置零

result.add(0);

}

for (int i = 0; i < an.size(); i++) {

result.set(i, result.get(i) + an.get(i) * bn.get(0)); //将相乘的值存入返回值

result.set(i + 1, result.get(i + 1) + result.get(i) / 10); //若相乘的值大于10，则进位

result.set(i, result.get(i) % 10); //进位后留余

}

len = result.size(); //如果返回结果后面还剩余0，则将零去掉

while (result.get(len – 1) == 0 && len > 1) {

result.remove(len – 1);

len–;

}

reverse(result); //将所得解逆置即为乘法所得

int l = x + y; //由于两数相乘时可能有10的幂，所以在结果后补0

while (l > 0) {

result.add(0);

l–;

}

return result;

}

//相乘的结果相加

public static List add(List ac, List ad, List bc, List bd) {

Collections.reverse(ac);

Collections.reverse(ad);

Collections.reverse(bc);

Collections.reverse(bd);

List result = new ArrayList<>();

int len = ac.size() + bc.size() + ad.size() + bd.size();

for (int i = 0; i <= len; i++) {

result.add(0);

}

for (int i = 0; i < ac.size(); i++) {

result.set(i, ac.get(i));

}

for (int i = 0; i < ad.size(); i++) {

result.set(i, result.get(i) + ad.get(i));

}

for (int i = 0; i < bc.size(); i++) {

result.set(i, result.get(i) + bc.get(i));

}

for (int i = 0; i < bd.size(); i++) {

result.set(i, result.get(i) + bd.get(i));

}

for (int i = 0; i < len; i++) {

result.set(i + 1, result.get(i + 1) + result.get(i) / 10);

result.set(i, result.get(i) % 10);

}

while (result.get(len) == 0 && len > 1) {

result.remove(len);

len–;

}

Collections.reverse(result);

return result;

}

//获取集合中的某一部分

public static List getList(List list, int x, int y) {

List list1 = new ArrayList<>();

for (int i = x; i < y; i++) {

list1.add(list.get(i));

}

return list1;

}

}

时间复杂度分析：

该问题类似的将两个大的数相乘转化为了四个小的数相乘，由此可以得出公式，其中字符串转化位集合时间复杂度为n,字符串实现乘法时间复杂度为n,字符串相加，时间复杂度为n,得：

T(n) = 4T(n/2)+3n

由Master定理可得：

a=4,b=2,f(n)=3n,n(logb(a))=O(n2)

因为f(n)=3n=O(n^(logb(a)-c)),得c=1,

所以T(n) = O(n(logb(a)))=O(n2),

(m+n)/2 ↩︎