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

戳蓝字“CSDN云计算”关注我们哦！

如何用程序实现大整数相乘呢？

在上一篇文章  漫画：如何实现大整数相乘？（上） 修订版 当中，我们介绍了两种思路：

1.像列竖式一样，把两整数按位依次相乘

这个思路的时间复杂度是O（n^2）。

2.利用分治法，把每个大整数分成高位和低位两部分，转化成四个较小的乘积。

这个思路的时间复杂度同样是O（n^2）。

那么，有什么样的优化方案，可以使时间复杂度优于O（n^2）呢？我们今天一起来研究下。

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

这样一来，原本的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();

57.    //t1,t2为中间运算结果，t3为乘法运算完毕的结果

58.    String t1, t2, t3;

59.    String ac = bigNumberMultiply(a, c);

60.    String bd = bigNumberMultiply(b, d);

61.    //t1=(A-B)(D-C)

62.    t1 = bigNumberMultiply(bigNumberSubtract(a, b), bigNumberSubtract(d, c));

63.    //t2=(A-B)(D-C)+AC+BD

64.    t2 = bigNumberSum(bigNumberSum(t1, ac), bd);

65.    //t3= AC * 10^n+((A-B)(D-C)+AC+BD) * 10^(n/2)+BD

66.    t3 = bigNumberSum(bigNumberSum(Power10(ac, n), Power10(t2, n/2)), bd).replaceAll("^0+", "");

67.    if (t3 == "")

68.        return "0";

69.    if(isNegative){

70.        return "-" + t3;

71.    }

72.    return t3;

73. }
    

74. /**

75. * 大整数加法

76. * @param bigNumberA  大整数A

77. * @param bigNumberB  大整数B

78. */

79. public static String bigNumberSum(String bigNumberA, String bigNumberB) {

80.    if (bigNumberA.startsWith("-") && !bigNumberB.startsWith("-")) {

81.        return bigNumberSubtract(bigNumberB, bigNumberA.replaceAll("^-", ""));

82.    } else if (!bigNumberA.startsWith("-") && bigNumberB.startsWith("-")) {

83.        return bigNumberSubtract(bigNumberA, bigNumberB.replaceAll("^-", ""));

84.    } else if (bigNumberA.startsWith("-") && bigNumberB.startsWith("-")) {

85.        return "-" + bigNumberSum(bigNumberA.replaceAll("^-", ""), bigNumberB.replaceAll("^-", ""));

86.    }

87.    //1.把两个大整数用数组逆序存储，数组长度等于较大整数位数+1

88.    int maxLength = bigNumberA.length() > bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();

89.    int[] arrayA = new int[maxLength+1];

90.    for(int i=0; i< bigNumberA.length(); i++){

91.        arrayA[i] = bigNumberA.charAt(bigNumberA.length()-1-i) - '0';

92.    }

93.    int[] arrayB = new int[maxLength+1];

94.    for(int i=0; i< bigNumberB.length(); i++){

95.        arrayB[i] = bigNumberB.charAt(bigNumberB.length()-1-i) - '0';

96.    }

97.    //2.构建result数组，数组长度等于较大整数位数+1

98.    int[] result = new int[maxLength+1];

99.    //3.遍历数组，按位相加

100.    for(int i=0; i<result.length; i++){

101.        int temp = result[i];

102.        temp += arrayA[i];

103.        temp += arrayB[i];

104.        //判断是否进位

105.        if(temp >= 10){

106.            temp -= 10;

107.            result[i+1] = 1;

108.        }

109.        result[i] = temp;

110.    }

111.    //4.把result数组再次逆序并转成String

112.    StringBuilder sb = new StringBuilder();

113.    //是否找到大整数的最高有效位

114.    boolean findFirst = false;

115.    for (int i = result.length - 1; i >= 0; i--) {

116.        if(!findFirst){

117.            if(result[i] == 0){

118.                continue;

119.            }

120.            findFirst = true;

121.        }

122.        sb.append(result[i]);

123.    }

124.    return sb.toString();

125. }
     

126. /**

127. * 大整数减法

128. * @param bigNumberA  大整数A

129. * @param bigNumberB  大整数B

130. */

131. public static String bigNumberSubtract(String bigNumberA, String bigNumberB) {

132.    int compareResult = compare(bigNumberA, bigNumberB);

133.    if (compareResult == 0) {

134.        return "0";

135.    }

136.    boolean isNegative = false;

137.    if (compareResult == -1) {

138.        String tmp = bigNumberB;

139.        bigNumberB = bigNumberA;

140.        bigNumberA = tmp;

141.        isNegative = true;

142.    }

143.    //1.把两个大整数用数组逆序存储，数组长度等于较大整数位数+1

144.    int maxLength = bigNumberA.length() > bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();

145.    int[] arrayA = new int[maxLength+1];

146.    for(int i=0; i< bigNumberA.length(); i++){

147.        arrayA[i] = bigNumberA.charAt(bigNumberA.length()-1-i) - '0';

148.    }

149.    int[] arrayB = new int[maxLength+1];

150.    for(int i=0; i< bigNumberB.length(); i++){

151.        arrayB[i] = bigNumberB.charAt(bigNumberB.length()-1-i) - '0';

152.    }

153.    //2.构建result数组，数组长度等于较大整数位数+1

154.    int[] result = new int[maxLength+1];

155.    //3.遍历数组，按位相加

156.    for(int i=0; i<result.length; i++){

157.        int temp = result[i];

158.        temp += arrayA[i];

159.        temp -= arrayB[i];

160.        //判断是否进位

161.        if(temp < 0){

162.            temp += 10;

163.            result[i+1] = -1;

164.        }

165.        result[i] = temp;

166.    }

167.    //4.把result数组再次逆序并转成String

168.    StringBuilder sb = new StringBuilder();

169.    //是否找到大整数的最高有效位

170.    boolean findFirst = false;

171.    for (int i = result.length - 1; i >= 0; i--) {

172.        if(!findFirst){

173.            if(result[i] == 0){

174.                continue;

175.            }

176.            findFirst = true;

177.        }

178.        sb.append(result[i]);

179.    }

180.    String value = sb.toString();

181.    if (isNegative) {

182.        value = "-" + value;

183.    }

184.    return value;

185. }
     

186. // 比较大小

187. private static int compare(String x, String y) {

188.    if (x.length() > y.length()) {

189.        return 1;

190.    } else if (x.length() < y.length()) {

191.        return -1;

192.    } else {

193.        for (int i = 0; i < x.length(); i++) {

194.            if (x.charAt(i) > y.charAt(i)) {

195.                return 1;

196.            } else if (x.charAt(i) < y.charAt(i)) {

197.                return -1;

198.            }

199.        }

200.        return 0;

201.    }

202. }
     

203. // 扩大10的n次方倍

204. public static String Power10(String num, int n) {

205.    for (int i = 0; i < n; i++) {

206.        num += "0";

207.    }

208.    return num;

209. }
     

210. public static void main(String[] args) {

211.    String x = "1513143";

212.    String y = "9345963";

213.    System.out.println(bigNumberMultiply(x, y));

214. }

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

文章转自程序员小灰

1.微信群：

添加小编微信：color_ld，备注“进群+姓名+公司职位”即可，加入【云计算学习交流群】，和志同道合的朋友们共同打卡学习！

2.征稿：

投稿邮箱：[e-mail]；微信号：color_ld。请备注投稿+姓名+公司职位。

推荐阅读

程序员抢票姿势 ↓交朋友还能抢票？

为交流学习，请备注+姓名+公司职位（学校专业）

点击“阅读原文”，打开 CSDN App 阅读更贴心！