計算機大數乘法引發的思考 | CSDN 博文精選

201×33×707+484×636321×33×707+484×6363我知道肯定是把數字拆開，配合結合律完成一種 「巧算」 ，之所以稱之為「巧算」，是因為這種算法比通過豎式直接硬算要節省不少步驟。但我一下子想不到怎麼拆解，我也懶得思考，因為我在思考另一件事。原式=67×3×33×707+11×44×9×707=67×3×33×707+11×44×9×707=11×99×707=111×99×7×101=777×9999=7770000−777=7769223通俗來講，一個計算的所有步驟就是一個算法，算法的時間複雜度其實就是計算的規模和步驟數量之間的關係。

以乘法豎式為例，如果我們將一次十進位一位乘法(即99乘法表的乘法)作為一個步驟，那麼兩個n位乘數相乘需要n的二次方個步驟，其時間複雜度就是O(n

2) ，但是如果我們採用某種「巧算」，那麼計算步驟將會大大減少。小學，中學老師教的各種「巧算」技巧，其宗旨都是減少計算量。我們已經承蒙了12年有餘的教誨，現在讓我們進入計算機世界。計算機乘法和我們用豎式計算乘法沒有本質區別。看看加法器，乘法器的門電路就知道了。門電路不是我們要關注的層次，門電路實在是太快了，快到你幾乎無法感知它計算2×3和24890125×98723988的差別。機器是瞬間得到結果的。人背下下來了99乘法表，所以人只能一位一位的計算乘法，但計算機不，計算機依靠自身的硬體門電路可以輕而易舉計算出其內建數據類型乘法，64位的CPU可以輕易計算 0xFFFFFFFFFFFFFFFF 範圍內的任意乘法，就好像我們人類計算99乘法表的乘法一樣(我們早就把這個99乘法表背下來了，深刻在了我們的大腦硬體乘法器裡)。然而，超過計算機內建類型範圍，計算機便無能為力了。32位計算機最多只能處理32位的數字，64位計算機自然只能處理64位數字，計算機處理超過內建數據類型範圍的數字計算的過程稱為 「大數計算」 。以64位為例，當計算機面對超過64位的數字乘法時，就好像我們人類面對超過一位數的乘法一樣，無法 「一下子」 得到結果，必須需要某種步驟來計算結果。這就是說，需要某種算法來進行生成一系列的計算步驟，而 步驟的多少決定了算法的好壞。23567971209865125789034451795247×12345678909988776655443314719047=?我們當然希望設計一種巧算的步驟，但在此之前，我們先設計一種 按部就班的算法，類似我們手算豎式一樣：人就是這麼算的，老老實實地按照十進位99乘法表，一個數字一個數字地進行計算，計算過程中處理進位。手工算豎式人人都會，說這些也無益，上周三下班的班車上，順手擼了一個代碼，感覺還好，發了個朋友圈就想分享出來，本周就休息一天，趕早起來就寫下了這篇文章。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void inline carry_add(char *tmp, char num, int index)
{
    char tmp_num = 0;
    char carry;

    tmp_num = tmp[index] + num;
    if (tmp_num > 9) {
        carry = tmp_num / 10;
        tmp[index] = tmp_num%10;
        carry_add(tmp, carry, index-1); 
        
    } else {
        tmp[index] = tmp_num;
    }
}

int mul(char *mul1, char *mul2, char *result)
{
    int i, j, mid;
    int len1, len2, len, pos = 0;
    char *tmp;

    len1 = strlen(mul1);
    len2 = strlen(mul2);
    len = len1 + len2;

    tmp = (char *)calloc(len, 1);

    for (i = 0; i < len2; i++) {
        for (j = 0; j < len1; j++) {
            int idx = len - j - i - 1;
            mid = (mul2[len2 - i - 1] - '0') * (mul1[len1 - j - 1] - '0');
            
            carry_add(tmp, mid, idx);
        }
        
        
    }

    i = 0;
    while(tmp[i++] == 0) pos++;
    len = len - pos;
    memcpy(result, tmp + pos, len);
    free (tmp);

    for (i = 0; i < len; i++) {
        result[i] += '0';
    }

    return 0;
}

int main(int argc, char **argv)
{
    int len1, len2, i, count;
    char *m1, *m2, *result;

    m1 = argv[1];
    m2 = argv[2];
    count = atoi(argv[3]);

    len1 = strlen(m1);
    len2 = strlen(m2);
    result = calloc(len1 + len2, 1);

    
    for (i = 0; i < count; i++) {
        memset(result, 0, len1 + len2);
        mul(m1, m2, result);
    }

    printf("%s\n", result);
    free(result);

    return 0;
}

[root@localhost ]
290962605116854555936789385617202938185315195749798588574969609

結果對不對開始我也不知道，不過從算法的執行過程上看，以一次簡單乘法計數，這個算法的時間複雜度是O(n2)的，這種算法基本是要被斃掉的，所以必須進行優化。哈哈，看到這裡，可能很多人以為我要接著講 Karatsuba乘法 以及 快速傅立葉變換了吧。並不是，因為我不善於寫教程，而且這方面的資源已經夠多了，我再寫一遍徒增冗餘。我比較善於寫一些思考的過程。所以，我們按照相對常規的思路，循序漸進地來思考如何來優化程序。看看上面的代碼，算法完全模仿人類的手工豎式，按照十進位一位乘法來推進計算過程。但是這裡面有個根本的問題，猜猜看是什麼？一位乘法對於人類而言是可以直接計算的，99乘法表都會背，我們計算4×7的時候，沒有必要擺4排的7，然後數一數一共有多少，而是脫口而出28。對於人類而言，超過一位的數字乘法就屬於大數了，人們不會把12×89這種計算的結果背下來，那就需要某種技巧去拆解多位數字，利用巧算來減少計算步驟了。換句話說， 超過一位的十進位乘法計算，對於人類而言，就需要動用算法了。64位CPU可以直接計算 0xFFFFFFFFFFFFFFFF 範圍內的乘法計算，就像我們計算乘法口訣裡的乘法一樣，脫口而出的那種。這種能力是硬體門電路的可並發操作決定的，簡單點說，64個引腳可以同時發射高電平或者低電平，但我們的人腦貌似只能同時發射一個十進位數字，這決定了計算機計算多位數字和我們對待99乘法表是一致的。對於計算機而言，沒必要一位一位地計算啊，以64位機器而言，每次乘法計算的最大結果限制在 0xFFFFFFFFFFFFFFFF 就可以了。我們可以按照每8位一組來計算，因為保守計算， 99999999×99999999維持在 0xFFFFFFFFFFFFFFF 範圍內。好了，talk is cheap，下面是C代碼( 這個算法很少見，一般人都是直接利用Karatsuba乘法的，幾乎沒有人利用這種思路來展示分治，所以，希望能仔細看看 )：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void inline carry_add(char *tmp, char num, int index)
{
    char tmp_num = 0;
    char carry;

    tmp_num = tmp[index] + num;
    if (tmp_num > 9) {
        carry = tmp_num / 10;
        tmp[index] = tmp_num%10;
        carry_add(tmp, carry, index-1);
    } else {
        tmp[index] = tmp_num;
    }
}


int add(char *s1, int len1, char *s2, int len2, char *result, int *ppos)
{
    int i = 0, j = 0, len;
    char *c;

    len = len1;
    if (len2 > len)
        len = len2;

    for (i = len - 1; i >= 0; i--) {
        unsigned char tmp;
        if (len1 > len2) {
            tmp = s1[i] - '0';
            if (i > len1 - len2 - 1)
                tmp += s2[i - (len1 - len2)] - '0';
        } else {
            tmp = s2[i] - '0';
            if (i > len2 - len1 - 1)
                tmp += s1[i - (len2 - len1)] - '0';
        }
        carry_add(result, tmp, i + 1);
    }

    *ppos = 1;
    if (result[0] != 0) {
        len = len + 1;
        *ppos = 0;
    }

    for (i = 0; i < len + 1; i++) {
        result[i] += '0';
    }

    return len;
}


int zone_mul(char *mul1, char *mul2, int len, char *result, int result_len)
{
    int i, j, n = 0, reslen, totlen, pow1size, pow2size, pos = 0, nblocks = len / 8;
    unsigned long m1, m2, tmp_res;
    char str1[10], str2[10], resstr[20];
    char *pow1, *pow2, *tmp_result;

    tmp_result = calloc(result_len, 1);
    pow1 = calloc(len*2, 1);
    pow2 = calloc(len*2, 1);

    
    for (i = 0; i < nblocks; i++) {
        memcpy(str1, mul1 + len - i*8 - 8, 8);
        m1 = atoi(str1);

        for (j = 0; j < nblocks; j++) {
            memcpy(str2, mul2 + len - j*8 - 8, 8);
            m2 = atoi(str2);

            tmp_res = m1*m2;

            
            pow1size = i*8;
            pow2size = j*8;

            totlen = reslen = sprintf(resstr, "%lu", tmp_res);

            totlen += pow2size;
            memset(pow2, '0', totlen);
            memcpy(pow2, resstr, reslen);

            reslen = totlen;
            totlen += pow1size;
            memset(pow1, '0', totlen);
            memcpy(pow1, pow2, reslen);

            memset(result, 0, n + pos);

            
            n = add(pow1, totlen, tmp_result, n, result, &pos);
            memcpy(tmp_result, result + pos, n);
        }
    }
    memset(result, 0, n + pos);
    memcpy(result, tmp_result, n);
    free(tmp_result);
    free(pow1);
    free(pow2);
}

int main(int argc, char **argv)
{
    int len1, len2, i = 0, count;
    char *m1, *m2, *result;

    m1 = argv[1];
    m2 = argv[2];
    count = atoi(argv[3]);

    len1 = strlen(m1);
    len2 = strlen(m2);
    result = calloc(len1 + len2, 1);

    for (i = 0; i < count; i++) {
        memset(result, 0, len1 + len2);
        zone_mul(m1, m2, len1, result, len1 + len2);
    }

    printf("%s\n", result);
    free(result);

    return 0;
}

我們來比試一下效果，計算5000次同一個大數乘法：

[root@localhost ]# time ./mul 119334567890334449388883313579158334567098134455 667908995633221198765432134678040000123411113456 50000
79704631383957730438879843848804741889926116047138197998269353980447530720116354515911947726480

real    0m1.891s
user    0m1.889s
sys    0m0.001s
[root@localhost ]# time ./mul2 119334567890334449388883313579158334567098134455 667908995633221198765432134678040000123411113456 50000
79704631383957730438879843848804741889926116047138197998269353980447530720116354515912427726480

real    0m1.475s
user    0m1.472s
sys    0m0.001s
[root@localhost ]# 

對於計算機而言， 用計算機力所能及的多位乘法代替人腦的一位乘法 會減少很多的計算步驟，多位乘法對於計算機而言並不苛刻，只要在它的內建支持範圍內。就像我們計算99乘法一樣，你不會覺得9×9 9\times 99×9比1×1 1\times 11×1更難。但這個優化只是動用了計算機和人腦之間的能力差異，我們發明計算機就是讓它來做計算的，這註定使得它不可能用人類的一位計算方式去做豎式。我的算法保守採用了8位十進位來計算，但這只是最基本的常識，並不算優化。再想想如何來解題。誠然，任何人都知道需要巧算而不是硬算，所謂的巧算就是利用一些初等數學知識，比如將201分解成67和3的乘積或200和1的加和。
計算機能不能通過類似因式分解，拆項，結合律來優化計算步驟呢？很遺憾，計算機沒有智能，目前計算機的所有智能需要程式設計師來灌入。在將一些策略灌入計算機之前，程式設計師需要自己先把結果算出來，然後編程唄…我們知道，多項式有很多性質，如果我們能把一個任意數字表示成多項式，我們就可以利用這些性質了。這個時候才是引出 Karatsuba算法 的最好時機。任意兩個數字x，y我們可以任意取數字m，然後將其表示為：計算機教科書上針對Karatsuba算法的常規描述是使用遞歸實現，遞歸的退出條件是乘數稱為一位十進位數，這是大錯特錯！根本沒有必要讓乘數稱為一位數時才退出遞歸，64位機器上兩個乘數均是8位數字以內時就可以直接相乘而退出遞歸，讓計算機去計算自己力所能及的最大計算量，豈不是最好？Karatsuba乘法 沒什麼大不了的，無非就是利用人類的成果而已。這非常類似於一元二次方程的求解，人類去算的話，可以直接套用公式，而純讓計算機去解，只能一個一個數字去枚舉嘗試。如果仔細觀察一個多位數字的多項式表示，我們可以利用的性質還有很多，即便是快速傅立葉變換，也不過是其中之一。這就是現代數學成果的展示和利用。但是要知道，即便可以編程實現快速傅立葉變換來計算大數乘法，也只是利用了人類推導的結果，換句話說就是套公式，你並沒有利用計算機的優勢，而計算機的優勢就是可以非常快速地一個一個試。 那麼你就能利用一切關於多項式的直接結論去求解類似大數相乘的問題。這就好比說，讓你求一個方程的解：你可以利用計算機的快速計算能力一個一個數字的枚舉，你也可以直接利用韋達定理，求根公式，但是要記住，這不是計算機的能力，這只是電腦程式表達公式的能力。總而言之， 面對一個大數計算，手算情況下你覺得怎麼操作方便，就把這種操作編程實現，這就是優化。我們真的是細思極恐，我們的所謂現代密碼學原來完全建立在 「現代計算機不是建立在2048位的基礎之上的」 。RSA密鑰長度2048位已經被證明相當安全了，但是數學上可以證明的所謂難題如果面對真正的2048位計算機會怎麼樣…如果真的有2048位計算機，破解RSA還會很難嗎？內建2048位的門電路引腳可以同時發射2048位的電平信號，可以預期可以瞬間分解2048位的密鑰，這是多麼恐怖的事情。然而對於此類夢想，2048位計算機難呢，還是量子計算機難呢？經理說，篳路藍縷，以啟山林。並不是說有了2048位字長的計算機就可以暴力破解RSA了，而是說有了2048位字長的計算機之後，大數乘法的開銷就被壓縮了，按照nlogn倍壓縮掉了。遍歷2048位解空間的開銷絲毫不受影響，受影響的只是拆解，計算2048位大數(2048位字長的計算機中不叫大數了…)的開銷。換句話說，RSA暴破難題包括兩部分，一部分是數學上的，這是由數學決定的，另一部分是實現上的計算開銷，這個開銷受計算機結構，字長，時鐘頻率，算法等一系列因素影響，如果實現了2048位字長的計算機，這些開銷將會大大降低，如果是量子計算機，2048位解空間可以並行開解，那就更快了，但是也絲毫沒有動搖RSA算法的數學基礎。突然有人問我一個關於快速排序為什麼快的問題，搜到之前自己的文章，有點想法。有人問我在同樣O(nlogn) 的時間複雜度情況下，為什麼快速排序比歸併排序快，我沒有辦法證明，但是事實上的原因卻是非常顯然的：不知為不知–資訊理論和最大熵原則 ：https://blog.csdn.net/dog250/article/details/78944526版權聲明：本文為CSDN博主「dog250」的原創文章。

 熱 文 推 薦 

☞國際頂級學界和工業界大咖雲集、AIoT 實訓營，你不可錯過的嵌入式 AI 盛會！

☞2019 年度最佳開源軟體出爐，TensorFlow 上榜！

☞【只有光頭才能變強，文末有xx】分享一波Lambda表達式

☞如何解決多機房、多網絡下的物聯網部署方案？

☞從4個維度深度剖析閃電網絡現狀，在CKB上實現閃電網絡的理由 | 博文精選

☞太雞凍了！我用Python偷偷查到暗戀女生的名字

☞一文了解超級帳本DLT、庫、開發工具有哪些, Hyperledger家族成員你認識幾個？

點擊閱讀原文，查看博主原文。