漫画：如何实现大整数相乘？（下）
戳藍字“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 之間的差距看似不大，但是當整數長度非常大的時候，兩種方法的性能將是天壤之別。
下面展示一下實現代碼。我們的代碼非常復雜，在這里只作為參考，最重要的還是解決問題的思路：
/**
* 大整數乘法
* @param bigNumberA ?大整數A
* @param bigNumberB ?大整數B
*/
public static String bigNumberMultiply(String bigNumberA, String bigNumberB) {
? ?boolean isNegative = false;
? ?if ((bigNumberA.startsWith("-") && bigNumberB.startsWith("-"))
? ? ? ? ? ?|| (!bigNumberA.startsWith("-") && !bigNumberB.startsWith("-"))) {
? ? ? ?// 兩數同符號的情況
? ? ? ?bigNumberA = bigNumberA.replaceAll("-", "");
? ? ? ?bigNumberB = bigNumberB.replaceAll("-", "");
? ?} else if ((bigNumberA.startsWith("-") && !bigNumberB.startsWith("-"))
? ? ? ? ? ?|| (!bigNumberA.startsWith("-") && bigNumberB.startsWith("-"))) {
? ? ? ?// 兩數不同符號的情況
? ? ? ?bigNumberA = bigNumberA.replace("-", "");
? ? ? ?bigNumberB = bigNumberB.replace("-", "");
? ? ? ?isNegative = true;
? ?}
? ?// 如果兩數長度之和小于10，直接相乘返回
? ?if (bigNumberA.length() + bigNumberB.length() < 10) {
? ? ? ?// 計算乘積
? ? ? ?int tmp = (Integer.parseInt(bigNumberA) * Integer.parseInt(bigNumberB));
? ? ? ?if (tmp == 0) {
? ? ? ? ? ?return "0";
? ? ? ?}
? ? ? ?String value = String.valueOf(tmp);
? ? ? ?if(isNegative){
? ? ? ? ? ?value = "-" + value;
? ? ? ?}
? ? ? ?return value;
? ?}
? ?// 公式 AC * 10^n+((A-B)(D-C)+AC+BD) * 10^(n/2)+BD當中的a,b,c,d
? ?String a, b, c, d;
? ?if (bigNumberA.length() == 1) {
? ? ? ?a = "0";
? ? ? ?b = bigNumberA;
? ?} else {
? ? ? ?if (bigNumberA.length() % 2 != 0) {
? ? ? ? ? ?bigNumberA = "0" + bigNumberA;
? ? ? ?}
? ? ? ?a = bigNumberA.substring(0, bigNumberA.length() / 2);
? ? ? ?b = bigNumberA.substring(bigNumberA.length() / 2);
? ?}
? ?if (bigNumberB.length() == 1) {
? ? ? ?c = "0";
? ? ? ?d = bigNumberB;
? ?} else {
? ? ? ?if (bigNumberB.length() % 2 != 0) {
? ? ? ? ? ?bigNumberB = "0" + bigNumberB;
? ? ? ?}
? ? ? ?c = bigNumberB.substring(0, bigNumberB.length() / 2);
? ? ? ?d = bigNumberB.substring(bigNumberB.length() / 2);
? ?}
? ?// 按最大位數取值，以確定補零數目
? ?int n = bigNumberA.length() >= bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();
? ?//t1,t2為中間運算結果，t3為乘法運算完畢的結果
? ?String t1, t2, t3;
? ?String ac = bigNumberMultiply(a, c);
? ?String bd = bigNumberMultiply(b, d);
? ?//t1=(A-B)(D-C)
? ?t1 = bigNumberMultiply(bigNumberSubtract(a, b), bigNumberSubtract(d, c));
? ?//t2=(A-B)(D-C)+AC+BD
? ?t2 = bigNumberSum(bigNumberSum(t1, ac), bd);
? ?//t3= AC * 10^n+((A-B)(D-C)+AC+BD) * 10^(n/2)+BD
? ?t3 = bigNumberSum(bigNumberSum(Power10(ac, n), Power10(t2, n/2)), bd).replaceAll("^0+", "");
? ?if (t3 == "")
? ? ? ?return "0";
? ?if(isNegative){
? ? ? ?return "-" + t3;
? ?}
? ?return t3;
}
/**
* 大整數加法
* @param bigNumberA ?大整數A
* @param bigNumberB ?大整數B
*/
public static String bigNumberSum(String bigNumberA, String bigNumberB) {
? ?if (bigNumberA.startsWith("-") && !bigNumberB.startsWith("-")) {
? ? ? ?return bigNumberSubtract(bigNumberB, bigNumberA.replaceAll("^-", ""));
? ?} else if (!bigNumberA.startsWith("-") && bigNumberB.startsWith("-")) {
? ? ? ?return bigNumberSubtract(bigNumberA, bigNumberB.replaceAll("^-", ""));
? ?} else if (bigNumberA.startsWith("-") && bigNumberB.startsWith("-")) {
? ? ? ?return "-" + bigNumberSum(bigNumberA.replaceAll("^-", ""), bigNumberB.replaceAll("^-", ""));
? ?}
? ?//1.把兩個大整數用數組逆序存儲，數組長度等于較大整數位數+1
? ?int maxLength = bigNumberA.length() > bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();
? ?int[] arrayA = new int[maxLength+1];
? ?for(int i=0; i< bigNumberA.length(); i++){
? ? ? ?arrayA[i] = bigNumberA.charAt(bigNumberA.length()-1-i) - '0';
? ?}
? ?int[] arrayB = new int[maxLength+1];
? ?for(int i=0; i< bigNumberB.length(); i++){
? ? ? ?arrayB[i] = bigNumberB.charAt(bigNumberB.length()-1-i) - '0';
? ?}
? ?//2.構建result數組，數組長度等于較大整數位數+1
? ?int[] result = new int[maxLength+1];
? ?//3.遍歷數組，按位相加
? ?for(int i=0; i<result.length; i++){
? ? ? ?int temp = result[i];
? ? ? ?temp += arrayA[i];
? ? ? ?temp += arrayB[i];
? ? ? ?//判斷是否進位
? ? ? ?if(temp >= 10){
? ? ? ? ? ?temp -= 10;
? ? ? ? ? ?result[i+1] = 1;
? ? ? ?}
? ? ? ?result[i] = temp;
? ?}
? ?//4.把result數組再次逆序并轉成String
? ?StringBuilder sb = new StringBuilder();
? ?//是否找到大整數的最高有效位
? ?boolean findFirst = false;
? ?for (int i = result.length - 1; i >= 0; i--) {
? ? ? ?if(!findFirst){
? ? ? ? ? ?if(result[i] == 0){
? ? ? ? ? ? ? ?continue;
? ? ? ? ? ?}
? ? ? ? ? ?findFirst = true;
? ? ? ?}
? ? ? ?sb.append(result[i]);
? ?}
? ?return sb.toString();
}
/**
* 大整數減法
* @param bigNumberA ?大整數A
* @param bigNumberB ?大整數B
*/
public static String bigNumberSubtract(String bigNumberA, String bigNumberB) {
? ?int compareResult = compare(bigNumberA, bigNumberB);
? ?if (compareResult == 0) {
? ? ? ?return "0";
? ?}
? ?boolean isNegative = false;
? ?if (compareResult == -1) {
? ? ? ?String tmp = bigNumberB;
? ? ? ?bigNumberB = bigNumberA;
? ? ? ?bigNumberA = tmp;
? ? ? ?isNegative = true;
? ?}
? ?//1.把兩個大整數用數組逆序存儲，數組長度等于較大整數位數+1
? ?int maxLength = bigNumberA.length() > bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();
? ?int[] arrayA = new int[maxLength+1];
? ?for(int i=0; i< bigNumberA.length(); i++){
? ? ? ?arrayA[i] = bigNumberA.charAt(bigNumberA.length()-1-i) - '0';
? ?}
? ?int[] arrayB = new int[maxLength+1];
? ?for(int i=0; i< bigNumberB.length(); i++){
? ? ? ?arrayB[i] = bigNumberB.charAt(bigNumberB.length()-1-i) - '0';
? ?}
? ?//2.構建result數組，數組長度等于較大整數位數+1
? ?int[] result = new int[maxLength+1];
? ?//3.遍歷數組，按位相加
? ?for(int i=0; i<result.length; i++){
? ? ? ?int temp = result[i];
? ? ? ?temp += arrayA[i];
? ? ? ?temp -= arrayB[i];
? ? ? ?//判斷是否進位
? ? ? ?if(temp < 0){
? ? ? ? ? ?temp += 10;
? ? ? ? ? ?result[i+1] = -1;
? ? ? ?}
? ? ? ?result[i] = temp;
? ?}
? ?//4.把result數組再次逆序并轉成String
? ?StringBuilder sb = new StringBuilder();
? ?//是否找到大整數的最高有效位
? ?boolean findFirst = false;
? ?for (int i = result.length - 1; i >= 0; i--) {
? ? ? ?if(!findFirst){
? ? ? ? ? ?if(result[i] == 0){
? ? ? ? ? ? ? ?continue;
? ? ? ? ? ?}
? ? ? ? ? ?findFirst = true;
? ? ? ?}
? ? ? ?sb.append(result[i]);
? ?}
? ?String value = sb.toString();
? ?if (isNegative) {
? ? ? ?value = "-" + value;
? ?}
? ?return value;
}
// 比較大小
private static int compare(String x, String y) {
? ?if (x.length() > y.length()) {
? ? ? ?return 1;
? ?} else if (x.length() < y.length()) {
? ? ? ?return -1;
? ?} else {
? ? ? ?for (int i = 0; i < x.length(); i++) {
? ? ? ? ? ?if (x.charAt(i) > y.charAt(i)) {
? ? ? ? ? ? ? ?return 1;
? ? ? ? ? ?} else if (x.charAt(i) < y.charAt(i)) {
? ? ? ? ? ? ? ?return -1;
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?return 0;
? ?}
}
// 擴大10的n次方倍
public static String Power10(String num, int n) {
? ?for (int i = 0; i < n; i++) {
? ? ? ?num += "0";
? ?}
? ?return num;
}
public static void main(String[] args) {
? ?String x = "1513143";
? ?String y = "9345963";
? ?System.out.println(bigNumberMultiply(x, y));
}
需要注意的是，這段實現代碼只適用于兩個大整數長度相等的情況。如果想求解長度不等的整數相乘，只需要對代碼做微小的改動，有興趣的小伙伴沒有試一試。
文章轉自程序員小灰
1.微信群：
添加小編微信：color_ld，備注“進群+姓名+公司職位”即可，加入【云計算學習交流群】，和志同道合的朋友們共同打卡學習！
2.征稿：
投稿郵箱：liudan@csdn.net；微信號：color_ld。請備注投稿+姓名+公司職位。
推薦閱讀
下一次 IT 變革：邊緣計算（Edge computing）
為什么 ofo 徹底涼了？| 暢言
AI in 美團：吃喝玩樂背后的黑科技
無業務不技術：那些誓用區塊鏈重塑的行業，發展怎么樣了？
Windows 成“棄子”，Linux 終上位？
突發！12306 脫庫 410 萬用戶數據究竟從何泄漏？
可替代Android的6大開源移動操作系統
程序員求助：被領導強行要求寫Bug該怎么辦？網友的回答讓我笑翻
程序員搶票姿勢 ↓交朋友還能搶票？
為交流學習，請備注+姓名+公司職位（學校專業）
點擊“閱讀原文”，打開 CSDN App 閱讀更貼心！
總結
以上是生活随笔為你收集整理的漫画：如何实现大整数相乘？（下）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 我军军校和美国军校有交流吗
- 下一篇： 男兵跟女兵搏斗特战行动第几集？