大數(shù)乘法的算法

大數(shù)乘法的關(guān)鍵在于如何用字符串來模擬大數(shù)乘法。方法有如下幾種：模擬普通的手算乘法、利用代數(shù)方法優(yōu)化的乘法、快速傅立葉變換FFT葛超。

各算法的優(yōu)點(diǎn)

• 模擬普通手算乘法：算法簡單、空間復(fù)雜度小延塑。時間復(fù)雜度為O(n^2)绣张。
• 利用代數(shù)方法優(yōu)化的乘法：使用遞歸求解，空間復(fù)雜度較大关带。算法復(fù)雜侥涵，需要定義大數(shù)加法，大數(shù)減法宋雏。時間復(fù)雜度降低到O(n^1.5)芜飘。
• 快速傅立葉變換FFT：基于FFT的大數(shù)乘法時間復(fù)雜度O(nlogn)∧プ埽快速傅立葉變換據(jù)數(shù)值分析老師說是本世紀(jì)最為偉大的算法嗦明。

下邊主要對利用代數(shù)方法優(yōu)化的乘法進(jìn)行介紹。

分析

代數(shù)優(yōu)化

• 假設(shè)大數(shù)P蚪燕、Q的長度為m和n娶牌，P = (A * 10^k + B)，Q = (C * 10^k + D)馆纳。
• k = min(m / 2, n / 2)诗良。
• PQ = (A * 10^k + B)(C * 10^k + D) = AC * 10 ^2k + (AD + BC) * 10^k + BD。
• 以乘法操作作為主要操作鲁驶，采用master定理可知鉴裹，時間復(fù)雜度為O(n^2)。此時與普通的手算乘法并沒有不同钥弯。
• 用于減少時間復(fù)雜度的關(guān)鍵壹罚，(A - B)(C - D) = AC - AD - BC + BD
• 帶入后得，AC * 10 ^2k + (AC + BD - (A-B)(C-D)) * 10^k + BD寿羞。
• 由于我們以乘法操作作為主要操作，因此每一層遞歸中只需要3次乘法赂蠢。因此時間復(fù)雜度減少為O(n^1.5)绪穆。

大數(shù)加法

string add(string num1, string num2) {
    string answer;
    bool need = false;
    for (int i = num1.length() - 1, j = num2.length() - 1; i >= 0 || j >= 0; --i, --j) {
        int n1 = i >= 0 ? charToInt(num1[i]) : 0, n2 = j >= 0 ? charToInt(num2[j]) : 0;
        int r = 0;
        if (need) {
            r += 1;
            need = false;
        }
        r += n1 + n2;
        if (r >= 10) {
            need = true;
            answer.push_back(intToChar(r - 10));
        } else {
            need = false;
            answer.push_back(intToChar(r));
        }
    }
    if (need) {
        answer.push_back('1');
    }
    reverse(answer.begin(), answer.end());
    return answer;
}

• 采用need作為進(jìn)位標(biāo)志。
• 注意循環(huán)結(jié)束后need為true時需要再進(jìn)位。
• 最后需要給answer做reverse操作玖院。

大數(shù)減法

string minus(string num1, string num2, bool& isPositive) {
    if (num1.length() > num2.length()) {
        isPositive = true;
    } else if (num1.length() < num2.length()) {
        isPositive = false;
    } else {
        for (int i = 0; i != num1.length(); ++i) {
            int n1 = charToInt(num1[i]), n2 = charToInt(num2[i]);
            if (n1 > n2) {
                isPositive = true;
                break;
            } else if (n1 < n2) {
                isPositive = false;
                break;
            } else {
                continue;
            }
        }
    }

    if (!isPositive) {
        string tp(num2);
        num2 = num1;
        num1 = tp;
    }

    bool need = false;
    string answer;
    int i, j;
    for (i = num1.length() - 1, j = num2.length() - 1; i >= 0; --i, --j) {
        int n1 = charToInt(num1[i]), n2 = j >= 0 ? charToInt(num2[j]) : 0;
        if (need) {
            n1 -= 1;
            need = false;
        }
        if (n1 >= n2) {
            answer.push_back(intToChar(n1 - n2));
        } else {
            need = true;
            answer.push_back(intToChar(n1 + 10 - n2));
        }
    }

    for (int i = answer.length() - 1; i >= 0; --i) {
        if (answer[i] == '0') {
            answer.erase(answer.end() - 1);
        } else {
            break;
        }
    }

    if (answer.empty()) {
        answer.push_back('0');
    }

    reverse(answer.begin(), answer.end());
    return answer;
}

• 大數(shù)減法最麻煩的是需要判斷減后的正負(fù)情況菠红。因此需要一個引用的isPositive來保存正負(fù)情況。
• 預(yù)處理判斷兩個字符串?dāng)?shù)字的大小难菌，并將計(jì)算的正負(fù)結(jié)果保存到isPositive中试溯。
• 同樣用need作為借位標(biāo)志，模擬手算減法郊酒。
• 應(yīng)注意遇绞，減后高位可能有0存在，需要處理燎窘。
• 最后同樣需要對answer做reverse操作摹闽。

AC代碼

class Solution {
public:
    string multiply(string num1, string num2) {
        return multiplyNumbers(num1, num2);
    }
private:
    void preprocessing(string& str) {
        while (str.begin() != str.end() && *str.begin() == '0') {
            str.erase(str.begin());
        }
        if (str.empty()) {
            str.push_back('0');
        }
    }
    string multiplyNumbers(string num1, string num2) {
        if (num1.length() == 1) {
            return mulitplySingleNumber(num2, num1);
        }
        if (num2.length() == 1) {
            return mulitplySingleNumber(num1, num2);
        }
        int halfLen = min(num1.length() / 2, num2.length() / 2);
        string front1(num1, 0, num1.length() - halfLen), rear1(num1, num1.length() - halfLen, halfLen);
        string front2(num2, 0, num2.length() - halfLen), rear2(num2, num2.length() - halfLen, halfLen);
        preprocessing(front1); preprocessing(front2); preprocessing(rear1); preprocessing(rear2);
        string AC = multiplyNumbers(front1, front2);
        string BD = multiplyNumbers(rear1, rear2);
        bool isPositive1, isPositive2;
        isPositive1 = isPositive2 = true;
        string AmB = minus(front1, rear1, isPositive1), CmD = minus(front2, rear2, isPositive2);
        string AmBmCmD = multiplyNumbers(AmB, CmD);
        string answer = addAll(AC, BD, AmBmCmD, halfLen, isPositive1 && isPositive2 || !isPositive1 && !isPositive2);
        return answer;
    }
    string mulitplySingleNumber(string number, string single) {
        int t = charToInt(single[0]);
        if (t == 0) {
            return string ("0");
        }
        int need = 0;
        string answer;
        for (int i = number.length() - 1; i >= 0; --i) {
            int cur = charToInt(number[i]);
            int tp = cur * t + need;
            answer.push_back(intToChar(tp % 10));
            need = tp / 10;
        }
        if (need) {
            answer.push_back(intToChar(need));
        }
        reverse(answer.begin(), answer.end());
        return answer;
    }
    string minus(string num1, string num2, bool& isPositive) {
        if (num1.length() > num2.length()) {
            isPositive = true;
        } else if (num1.length() < num2.length()) {
            isPositive = false;
        } else {
            for (int i = 0; i != num1.length(); ++i) {
                int n1 = charToInt(num1[i]), n2 = charToInt(num2[i]);
                if (n1 > n2) {
                    isPositive = true;
                    break;
                } else if (n1 < n2) {
                    isPositive = false;
                    break;
                } else {
                    continue;
                }
            }
        }

        if (!isPositive) {
            string tp(num2);
            num2 = num1;
            num1 = tp;
        }

        bool need = false;
        string answer;
        int i, j;
        for (i = num1.length() - 1, j = num2.length() - 1; i >= 0; --i, --j) {
            int n1 = charToInt(num1[i]), n2 = j >= 0 ? charToInt(num2[j]) : 0;
            if (need) {
                n1 -= 1;
                need = false;
            }
            if (n1 >= n2) {
                answer.push_back(intToChar(n1 - n2));
            } else {
                need = true;
                answer.push_back(intToChar(n1 + 10 - n2));
            }
        }

        for (int i = answer.length() - 1; i >= 0; --i) {
            if (answer[i] == '0') {
                answer.erase(answer.end() - 1);
            } else {
                break;
            }
        }

        if (answer.empty()) {
            answer.push_back('0');
        }

        reverse(answer.begin(), answer.end());
        return answer;
    }
    string addAll(string AC, string BD, string AmBmCmD, int len, bool isPositive) {
        string mid = add(AC, BD);
        if (isPositive) {
            mid = minus(mid, AmBmCmD, isPositive);
        } else {
            mid = add(mid, AmBmCmD);
        }

        for (int i = 0; i != len; ++i) {
            AC += "00";
            mid.push_back('0');
        }

        string answer;
        answer = add(AC, mid);
        answer = add(answer, BD);
        return answer;
    }
    string add(string num1, string num2) {
        string answer;
        bool need = false;
        for (int i = num1.length() - 1, j = num2.length() - 1; i >= 0 || j >= 0; --i, --j) {
            int n1 = i >= 0 ? charToInt(num1[i]) : 0, n2 = j >= 0 ? charToInt(num2[j]) : 0;
            int r = 0;
            if (need) {
                r += 1;
                need = false;
            }
            r += n1 + n2;
            if (r >= 10) {
                need = true;
                answer.push_back(intToChar(r - 10));
            } else {
                need = false;
                answer.push_back(intToChar(r));
            }
        }
        if (need) {
            answer.push_back('1');
        }
        reverse(answer.begin(), answer.end());
        return answer;
    }
    int charToInt(char ch) {
        return static_cast<int> (ch - '0');
    }
    char intToChar(int ix) {
        return static_cast<char> ('0' + ix);
    }
};
//(A * 10^k + B)(C * 10^k + D) = AC * 10 ^2k + (AD + BC) * 10^k + BD = AC * 10 ^2k + (AC + BD - (A-B)(C-D)) * 10^k + BD

缺陷

• 應(yīng)在大數(shù)乘法之初，將string類型的數(shù)字轉(zhuǎn)換為vector<int>形式的數(shù)字褐健，每個元素代表一位數(shù)字付鹿。這樣避免了計(jì)算中的char和int轉(zhuǎn)換。
• 注意蚜迅，遞歸過程中截取的子串也可能在高位包含0舵匾，因此需要處理，代碼中用preprocessing方法做預(yù)處理谁不。