java实现大数相乘的2种方式

按位运算–时间效率O(n^2)

import java.util.LinkedList; import java.util.List; public class first { public static List<Integer> bigNumberMultiply2(int[] num1, int[] num2){ // 分配一个空间，用来存储运算的结果，num1长的数 * num2长的数，结果不会超过num1+num2长 LinkedList<Integer>result = new LinkedList<>(); // 先不考虑进位问题，根据竖式的乘法运算，num1的第i位与num2的第j位相乘，结果应该存放在结果的第i+j位上 for (int i = 0; i < num1.length; i++){ for (int j = 0; j < num2.length; j++){ if(result.size()-1<i+j) result.add(0); result.set( i+j, result.get(i+j)+(num1[i] * num2[j])%10); // 需要进位 if((num1[i] * num2[j])/10>0) { if(result.size()-1<i+j+1) result.add(0); result.set(i + j + 1, result.get(i + j + 1) + (num1[i] * num2[j]) / 10); } } } return result; } public static void main(String[]args){ List<Integer>res = bigNumberMultiply2(new int[]{3,2},new int[]{3}); for(int i:res) System.out.print(i); } }

分治乘法–Karatsuba算法

参考资料：https://blog.csdn.net/u010983881/article/details/77503519 每个字符串分成2个片段

import java.math.BigInteger; public class first { static String add(String a, String b) { if (a.length() <= 8 && b.length() <= 8) return Integer.parseInt(a) + Integer.parseInt(b) + ""; String a1 = "0"; String a2 = a; if (a.length() > 8) { a1 = a.substring(0, a.length() - 8); a2 = a.substring(a.length() - 8); } String b1 = "0"; String b2 = b; if (b.length() > 8) { b1 = b.substring(0, b.length() - 8); b2 = b.substring(b.length() - 8); } String t = add(a2, b2); while (t.length() < 8) t = "0" + t; if (t.length() > 8) return add(add(a1, b1), "1") + t.substring(1); return add(a1, b1) + t; } static String multi(String a, String b) { if (a.length() <= 4 && b.length() <= 4) return Integer.parseInt(a) * Integer.parseInt(b) + ""; if (a.length() > 4) { int k = a.length() / 2; String a1 = a.substring(0, k); String a2 = a.substring(k); String tmp = multi(a1, b) + zero(a2.length()); String tmp1 = multi(a2, b); return add(tmp,tmp1 ); } return multi(b, a); } static String zero(int n) { if (n == 0) return ""; if (n == 1) return "0"; String s = zero(n / 2); return s + s + zero(n % 2); } public static void main(String[] args) { System.out.println(multi("123456789","987654321")); System.out.println(new BigInteger("123456789").multiply(new BigInteger("987654321"))); } }

或

/** * Karatsuba乘法 */ public static long karatsuba(long num1, long num2){ //递归终止条件 if(num1 < 10 || num2 < 10) return num1 * num2; // 计算拆分长度 int size1 = String.valueOf(num1).length(); int size2 = String.valueOf(num2).length(); int halfN = Math.max(size1, size2) / 2; /* 拆分为a, b, c, d */ long a = Long.valueOf(String.valueOf(num1).substring(0, size1 - halfN)); long b = Long.valueOf(String.valueOf(num1).substring(size1 - halfN)); long c = Long.valueOf(String.valueOf(num2).substring(0, size2 - halfN)); long d = Long.valueOf(String.valueOf(num2).substring(size2 - halfN)); // 计算z2, z0, z1, 此处的乘法使用递归 long z2 = karatsuba(a, c); long z0 = karatsuba(b, d); long z1 = karatsuba((a + b), (c + d)) - z0 - z2; return (long)(z2 * Math.pow(10, (2*halfN)) + z1 * Math.pow(10, halfN) + z0); }