漫画：如何实现大整数相乘？

前一段时间，小灰发布了一篇有关大整数相加的漫画，没看过的小伙伴可以先看一看：

漫画：如何实现大整数相加？（修订版）

那么，大整数相乘又是如何实现的呢？

起初，小灰认为只要按照大整数相加的思路稍微做一下变形，就可以轻松实现大整数相乘。但是随着深入的学习，小灰才发现事情并没有那么简单……

————— 第二天 —————

怎样列出这个乘法竖式呢？以 93281 X 2034 为例，竖式如下：

在程序中，我们可以利用int型数组，把两个大整数按位进行存储，再把数组中的元素像小学竖式那样逐个进行计算。

这个乘法竖式的计算过程可以大体分为两步：

1.整数B的每一个数位和整数A所有数位依次相乘，得到中间结果。

2.所有中间结果相加，得到最终结果。

1. /**
2. * 大整数求乘积
3. * @param bigNumberA 大整数A
4. * @param bigNumberB 大整数B
5. */
6. public static String multiply(String bigNumberA, String bigNumberB) {
7. //1.把两个大整数用数组逆序存储，数组长度等于两整数长度之和
8. int lengthA = bigNumberA.length();
9. int lengthB = bigNumberB.length();
10. int[] arrayA = new int[lengthA];
11. for(int i=0; i< lengthA; i++){
12. arrayA[i] = bigNumberA.charAt(lengthA-1-i) - '0';
13. }
14. int[] arrayB = new int[lengthB];
15. for(int i=0; i< lengthB; i++){
16. arrayB[i] = bigNumberB.charAt(lengthB-1-i) - '0';
17. }
18. //2.构建result数组，数组长度等于两整数长度之和
19. int[] result = new int[lengthA+lengthB];
20. //3.嵌套循环，整数B的每一位依次和整数A的所有数位相乘，并把结果累加
21. for(int i=0;i<lengthB;i++) {
22. for(int j=0;j<lengthA;j++) {
23. //整数B的某一位和整数A的某一位相乘
24. result[i+j] += arrayB[i]*arrayA[j];
25. //如果result某一位大于10，则进位，进位数量是该位除以10的商
26. if(result[i+j] >= 10){
27. result[i+j+1] += result[i+j]/10;
28. result[i+j] = result[i+j]%10;
29. }
30. }
31. }
32. //4.把result数组再次逆序并转成String
33. StringBuilder sb = new StringBuilder();
34. //是否找到大整数的最高有效位
35. boolean findFirst = false;
36. for (int i = result.length - 1; i >= 0; i--) {
37. if(!findFirst){
38. if(result[i] == 0){
39. continue;
40. }
41. findFirst = true;
42. }
43. sb.append(result[i]);
44. }
45. return sb.toString();
46. }
48. public static void main(String[] args) {
49. String x = "3338429042340042304302404";
50. String y = "12303231";
51. System.out.println(multiply(x, y));
52. }

————————————

下面，我们的推导会有一些烧脑，请大家坐稳扶好~~

大整数从高位到低位，被平分成了两部分。设整数1的高位部分是A，低位部分是B；整数2的高位部分是C，低位部分是D，那么有如下等式：

如果把大整数的长度抽象为n，那么：

因此，整数1与整数2 的乘积可以写成下面的形式：

如此一来，原本长度为**n的大整数的1次乘积，被转化成了长度为n/2的大整数的4次**乘积（AC，AD，BC，BD）。

什么是master定理呢？

master定理的英语名称是master theorem，它为许多由分治法得到的递推关系式提供了渐进时间复杂度分析。

设常数a >= 1，b > 1，如果一个算法的整体计算规模 T(n) = a T(n / b) + f(n)，那么则有如下规律：

假设两个长度为n的大整数相乘，整体运算规模是T(n) 。

根据刚才得到的结论，两个大整数相乘被拆分成四个较小的乘积：

所以在第一次分治时，T(n)和T(n/2)有如下关系：

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

其中f(n)是4个乘积结果相加的运算规模，f(n)的渐进时间复杂度很明显是O(n)。

把这个关系带入到master定理的公式 T(n) = a T(n / b) + f(n) 当中，

此时 a=4， b=2。

此时，把a和b的值，以及f(n)的时间复杂度带入到master定理的第一个规律，也就是下面的规律：

发现正好符合条件。

怎么符合呢？推导过程如下：

所以我们的平均时间复杂度是：

如何做调整呢？其实很简单，连小学生都会：

这样一来，原本的4次乘法和3次加法，转变成了3次乘法和6次加法。

这样一来，时间复杂度是多少呢？

假设两个长度为n的大整数相乘，整体运算规模是T(n) 。

刚才我们说过，两个大整数相乘可以被拆分成三个较小的乘积，

所以在第一次分治时，T(n)和T(n/2)有如下关系：

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

其中f(n)是6次加法的运算规模，f(n)的渐进时间复杂度很明显是O(n)。

此时让我们回顾一下master定理：

设常数a >= 1，b > 1，如果一个算法的整体计算规模 T(n) = a T(n / b) + f(n)，那么则有如下规律：

对于T(n) = 3T(n/2) + f(n)这个关系式来说， a=3， b=2。

把a和b的值，以及f(n)的时间复杂度带入到master定理的第一个规律，也就是下面的规律：

发现正好符合条件。

怎么符合条件呢？推导过程如下：

所以我们的平均时间复杂度是：

2 和 1.59 之间的差距看似不大，但是当整数长度非常大的时候，两种方法的性能将是天壤之别。

下面展示一下实现代码。我们的代码非常复杂，在这里只作为参考，最重要的还是解决问题的思路：

1. /**
2. * 大整数乘法
3. * @param bigNumberA 大整数A
4. * @param bigNumberB 大整数B
5. */
6. public static String bigNumberMultiply(String bigNumberA, String bigNumberB) {
7. boolean isNegative = false;
8. if ((bigNumberA.startsWith("-") && bigNumberB.startsWith("-"))
9. || (!bigNumberA.startsWith("-") && !bigNumberB.startsWith("-"))) {
10. // 两数同符号的情况
11. bigNumberA = bigNumberA.replaceAll("-", "");
12. bigNumberB = bigNumberB.replaceAll("-", "");
13. } else if ((bigNumberA.startsWith("-") && !bigNumberB.startsWith("-"))
14. || (!bigNumberA.startsWith("-") && bigNumberB.startsWith("-"))) {
15. // 两数不同符号的情况
16. bigNumberA = bigNumberA.replace("-", "");
17. bigNumberB = bigNumberB.replace("-", "");
18. isNegative = true;
19. }
20. // 如果两数长度之和小于10，直接相乘返回
21. if (bigNumberA.length() + bigNumberB.length() < 10) {
22. // 计算乘积
23. int tmp = (Integer.parseInt(bigNumberA) * Integer.parseInt(bigNumberB));
24. if (tmp == 0) {
25. return "0";
26. }
27. String value = String.valueOf(tmp);
28. if(isNegative){
29. value = "-" + value;
30. }
31. return value;
32. }
33. // 公式 AC * 10^n+((A-B)(D-C)+AC+BD) * 10^(n/2)+BD当中的a,b,c,d
34. String a, b, c, d;
35. if (bigNumberA.length() == 1) {
36. a = "0";
37. b = bigNumberA;
38. } else {
39. if (bigNumberA.length() % 2 != 0) {
40. bigNumberA = "0" + bigNumberA;
41. }
42. a = bigNumberA.substring(0, bigNumberA.length() / 2);
43. b = bigNumberA.substring(bigNumberA.length() / 2);
44. }
45. if (bigNumberB.length() == 1) {
46. c = "0";
47. d = bigNumberB;
48. } else {
49. if (bigNumberB.length() % 2 != 0) {
50. bigNumberB = "0" + bigNumberB;
51. }
52. c = bigNumberB.substring(0, bigNumberB.length() / 2);
53. d = bigNumberB.substring(bigNumberB.length() / 2);
54. }
55. // 按最大位数取值，以确定补零数目
56. int n = bigNumberA.length() >= bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();
58. //t1,t2为中间运算结果，t3为乘法运算完毕的结果
59. String t1, t2, t3;
60. String ac = bigNumberMultiply(a, c);
61. String bd = bigNumberMultiply(b, d);
63. //t1=(A-B)(D-C)
64. t1 = bigNumberMultiply(bigNumberSubtract(a, b), bigNumberSubtract(d, c));
65. //t2=(A-B)(D-C)+AC+BD
66. t2 = bigNumberSum(bigNumberSum(t1, ac), bd);
67. //t3= AC * 10^n+((A-B)(D-C)+AC+BD) * 10^(n/2)+BD
68. t3 = bigNumberSum(bigNumberSum(Power10(ac, n), Power10(t2, n/2)), bd).replaceAll("^0+", "");
69. if (t3 == "")
70. return "0";
71. if(isNegative){
72. return "-" + t3;
73. }
74. return t3;
75. }
79. /**
80. * 大整数加法
81. * @param bigNumberA 大整数A
82. * @param bigNumberB 大整数B
83. */
84. public static String bigNumberSum(String bigNumberA, String bigNumberB) {
86. if (bigNumberA.startsWith("-") && !bigNumberB.startsWith("-")) {
87. return bigNumberSubtract(bigNumberB, bigNumberA.replaceAll("^-", ""));
88. } else if (!bigNumberA.startsWith("-") && bigNumberB.startsWith("-")) {
89. return bigNumberSubtract(bigNumberA, bigNumberB.replaceAll("^-", ""));
90. } else if (bigNumberA.startsWith("-") && bigNumberB.startsWith("-")) {
91. return "-" + bigNumberSum(bigNumberA.replaceAll("^-", ""), bigNumberB.replaceAll("^-", ""));
92. }
94. //1.把两个大整数用数组逆序存储，数组长度等于较大整数位数+1
95. int maxLength = bigNumberA.length() > bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();
96. int[] arrayA = new int[maxLength+1];
97. for(int i=0; i< bigNumberA.length(); i++){
98. arrayA[i] = bigNumberA.charAt(bigNumberA.length()-1-i) - '0';
99. }
100. int[] arrayB = new int[maxLength+1];
101. for(int i=0; i< bigNumberB.length(); i++){
102. arrayB[i] = bigNumberB.charAt(bigNumberB.length()-1-i) - '0';
103. }
104. //2.构建result数组，数组长度等于较大整数位数+1
105. int[] result = new int[maxLength+1];
106. //3.遍历数组，按位相加
107. for(int i=0; i<result.length; i++){
108. int temp = result[i];
109. temp += arrayA[i];
110. temp += arrayB[i];
111. //判断是否进位
112. if(temp >= 10){
113. temp -= 10;
114. result[i+1] = 1;
115. }
116. result[i] = temp;
117. }
118. //4.把result数组再次逆序并转成String
119. StringBuilder sb = new StringBuilder();
120. //是否找到大整数的最高有效位
121. boolean findFirst = false;
122. for (int i = result.length - 1; i >= 0; i--) {
123. if(!findFirst){
124. if(result[i] == 0){
125. continue;
126. }
127. findFirst = true;
128. }
129. sb.append(result[i]);
130. }
131. return sb.toString();
132. }
135. /**
136. * 大整数减法
137. * @param bigNumberA 大整数A
138. * @param bigNumberB 大整数B
139. */
140. public static String bigNumberSubtract(String bigNumberA, String bigNumberB) {
141. int compareResult = compare(bigNumberA, bigNumberB);
142. if (compareResult == 0) {
143. return "0";
144. }
145. boolean isNegative = false;
146. if (compareResult == -1) {
147. String tmp = bigNumberB;
148. bigNumberB = bigNumberA;
149. bigNumberA = tmp;
150. isNegative = true;
151. }
152. //1.把两个大整数用数组逆序存储，数组长度等于较大整数位数+1
153. int maxLength = bigNumberA.length() > bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();
154. int[] arrayA = new int[maxLength+1];
155. for(int i=0; i< bigNumberA.length(); i++){
156. arrayA[i] = bigNumberA.charAt(bigNumberA.length()-1-i) - '0';
157. }
158. int[] arrayB = new int[maxLength+1];
159. for(int i=0; i< bigNumberB.length(); i++){
160. arrayB[i] = bigNumberB.charAt(bigNumberB.length()-1-i) - '0';
161. }
162. //2.构建result数组，数组长度等于较大整数位数+1
163. int[] result = new int[maxLength+1];
164. //3.遍历数组，按位相加
165. for(int i=0; i<result.length; i++){
166. int temp = result[i];
167. temp += arrayA[i];
168. temp -= arrayB[i];
169. //判断是否进位
170. if(temp < 0){
171. temp += 10;
172. result[i+1] = -1;
173. }
174. result[i] = temp;
175. }
176. //4.把result数组再次逆序并转成String
177. StringBuilder sb = new StringBuilder();
178. //是否找到大整数的最高有效位
179. boolean findFirst = false;
180. for (int i = result.length - 1; i >= 0; i--) {
181. if(!findFirst){
182. if(result[i] == 0){
183. continue;
184. }
185. findFirst = true;
186. }
187. sb.append(result[i]);
188. }
189. String value = sb.toString();
190. if (isNegative) {
191. value = "-" + value;
192. }
193. return value;
194. }
197. // 比较大小
198. private static int compare(String x, String y) {
199. if (x.length() > y.length()) {
200. return 1;
201. } else if (x.length() < y.length()) {
202. return -1;
203. } else {
204. for (int i = 0; i < x.length(); i++) {
205. if (x.charAt(i) > y.charAt(i)) {
206. return 1;
207. } else if (x.charAt(i) < y.charAt(i)) {
208. return -1;
209. }
210. }
211. return 0;
212. }
213. }
216. // 扩大10的n次方倍
217. public static String Power10(String num, int n) {
218. for (int i = 0; i < n; i++) {
219. num += "0";
220. }
221. return num;
222. }
225. public static void main(String[] args) {
226. String x = "1513143";
227. String y = "9345963";
228. System.out.println(bigNumberMultiply(x, y));
229. }

需要注意的是，这段实现代码只适用于两个大整数长度相等的情况。如果想求解长度不等的整数相乘，只需要对代码做微小的改动，有兴趣的小伙伴没有试一试。

几点补充：

1. 文章最后的代码，经由网上技术博客的代码改动而来，仅做参考。

2. 关于快速傅里叶变换，有兴趣深入研究的小伙伴们可以参考《算法导论》第30章的内容。