[[352004]]

在數據加密處理中有很多復雜的加密算法，這些加密算法往往會用到很多超大的整數運算。不過，程序設計語言對數據的大小會有一定的限制，數據太大就會出現數據溢出的情況，這是無法進行大整型數據運算的。本文將和大家一起學習如何實現大整數的數據運算，本文代碼我們使用C++實現。

普通乘數運算

對于乘數運算有一種比較簡單較為容易理解的方法，我們可以利用小學時期學的列豎式的計算方法進行乘法運算。

列豎式乘法運算

參考上圖中的列豎式計算方法，我們進行代碼實現。

#include <iostream> 
#include <string> 
#include <stdlib.h> 
#include <vector> 
#include <cstring> 
#include <algorithm> 
 
std::string multiply(std::string a, std::string b) 
{ 
    std::string result = ""; 
    int row = b.size(); 
    int col = a.size() + 1; 
    int tmp[row][col]; 
    memset(tmp,0, sizeof(int)*row*col); 
     
    reverse(a.begin(),a.end()); 
    reverse(b.begin(),b.end()); 
     
    for(int i = 0; i < b.size(); i++) 
    { 
        for(int j = 0; j < a.size(); j++) 
        { 
            std::string bit_a = std::string(1, a.at(j)); 
            std::string bit_b = std::string(1, b.at(i)); 
             
            tmp[i][j] += std::stoi(bit_a) * std::stoi(bit_b); 
         
            tmp[i][j+1] = tmp[i][j] / 10; 
            tmp[i][j] %= 10; 
 
        } 
 
    } 
 
    int N =  a.size() + b.size(); 
    int sum[N]; 
    memset(sum, 0, sizeof(int)*N); 
     
    for(int n = 0; n < N; n++) 
    { 
        int i = 0; 
        int j = n; 
         
        while (i <= n && j >= 0 ) 
        { 
            if(i < row && j < col) 
            { 
                sum[n] += tmp[i][j]; 
            } 
             
            i++; 
            j--; 
        } 
 
        if( n+1 < N ) 
        { 
            sum[n+1] = sum[n] / 10; 
            sum[n] %= 10; 
        } 
 
    } 
 
    bool zeroStartFlag = true; 
    for (int i = N-1; i >= 0; i--) 
    { 
        if(sum[i]==0 && zeroStartFlag) 
        { 
            continue; 
        } 
         
        zeroStartFlag = false; 
        result.append(std::to_string(sum[i])); 
    } 
     
    return result; 
} 
 
 
int main() 
{ 
    std::string a = "3456"; 
    std::string b = "1234"; 
 
    std::string result = multiply(a, b);     
    std::cout << a << " * " << b << " = " << result <<std::endl; 
     
    return 0; 
} 

為了方便我們先將各個乘數做了翻轉處理，最后需要再將結果翻轉回來。在運算過程中用來存放乘法運算結果的數組，我們沒有進行移位處理同列相加，而是對角線相加，這樣可以減少空間和運算步驟。上面的代碼運行結果如下所示。

運行結果

因為字符串的長度沒有特別的限制，所以上面的算法可以適用大整數運算。

分治算法

雖然上面的列豎式的方法可以很好的解決大整數乘法的問題，但是我們還用一種更加高效的方法可以選擇，這就是分治(Divide and Conquer)算法。它是一種非常重要的算法，可以應用到很多領域，比如快速排序，二分搜索等。從算法的名字我們可以看出它是將大的問題拆分進行細化，由大變小，先將小的問題解決，最終將這個問題解決，所以叫Divide and Conquer。在這里我們可以通過這種方法將大整數進行拆分，拆分成一個個可以通過程序語言直接進行運算的小整進行計算，最后求得到大整數的值。

假設有兩個大整數，我們設為a(大小為n位)和b(大小為m位)，這里我們將使用二分法對數據進行拆分，這兩個整數我們可以分解為：

則,

令，

根據上面公式里，我們可以將a*b分解為四個小的整數的乘法，即z3,z2,z1,z0四個表達式。如果分解出來的乘法數值還是很大，還可以按照同樣的方法進行拆解直到拆解成較小的數值乘法，直到計算機程序語言可以直接運算。

比如，上面的3456和1234相乘，參考下圖通過二分法逐級對整數進行拆分，我們將兩個整數拆分到一位整數進行運算。

3456和1234拆分步驟圖

下面我們看一下分治算法的代碼實現，這里我們使用遞歸的方法。

#include <iostream> 
#include <string> 
#include <stdlib.h> 
#include <vector> 
#include <cstring> 
#include <algorithm> 
#include <cmath> 
 
std::string add(std::string a, std::string b) 
{ 
    int N = std::max(a.size(), b.size()); 
    int sum[N]; 
    memset(sum, 0, sizeof(int)*N); 
     
    reverse(a.begin(),a.end()); 
    reverse(b.begin(),b.end()); 
 
    for(int i = 0; i< N; i++) 
    { 
        int bit_a = 0; 
        int bit_b = 0; 
        if(i < a.size()) bit_a = std::stoi(std::string(1, a.at(i))); 
        if(i < b.size()) bit_b = std::stoi(std::string(1, b.at(i))); 
 
        sum[i] += (bit_a + bit_b); 
 
        if(i < N-1 && sum[i]>9) 
        { 
            sum[i+1] = sum[i] / 10; 
            sum[i] %=10; 
        } 
    } 
 
    std::string result=""; 
    bool zeroStartFlag = true; 
    for (int i = N-1; i >= 0; i--) 
    { 
        if(sum[i]==0 && zeroStartFlag) 
        { 
            continue; 
        } 
         
        zeroStartFlag = false; 
        result.append(std::to_string(sum[i])); 
    } 
 
 
    return result; 
} 
 
std::string divideAndConquer(std::string a, std::string b) 
{ 
    if( a.size() < 2 && b.size() < 2)  
    { 
        return std::to_string(std::stoi(a) * std::stoi(b)); 
    } 
     
    int n = a.size(); 
    int m = b.size(); 
     
    int halfN = n/2; 
    int halfM = m/2; 
 
    std::string a0 = "0"; 
    std::string a1 = "0"; 
    if(a.size() > halfN && halfN > 0) 
    { 
        a1 = a.substr(0, halfN); 
        a0 = a.substr(halfN, a.size() - halfN); 
    } 
    else 
    { 
        a1 = "0"; 
        a0 = a; 
    } 
     
    std::string b0 = "0"; 
    std::string b1 = "0"; 
    if(b.size() > halfM && halfM > 0) 
    { 
        b1 = b.substr(0, halfM); 
        b0 = b.substr(halfM, b.size() - halfM); 
 
    } 
    else 
    { 
        b1 = "0"; 
        b0 = b; 
    } 
 
    std::string a1b1 = divideAndConquer(a1, b1); 
    std::string a0b0 = divideAndConquer(a0, b0); 
    std::string a1b0 = divideAndConquer(a1, b0); 
    std::string a0b1 = divideAndConquer(a0, b1); 
     
    a1b1.append((n - halfN) + (m - halfM), '0'); 
    a1b0.append(n - halfN, '0'); 
    a0b1.append(m - halfM, '0'); 
 
    std::string result = ""; 
    result = add(a1b1, a1b0); 
    result = add(result, a0b1); 
    result = add(result, a0b0); 
 
    return result; 
} 
 
int main() 
{ 
    std::string a = "3456"; 
    std::string b = "1234"; 
 
    std::cout << a << " * " << b << " = " << divideAndConquer(a, b) << std::endl;  
 
    return 0; 
} 

程序的運行結果如下：

分治算法運行結果

本文轉載自微信公眾號「Will的大食堂」，可以通過以下二維碼關注。轉載本文請聯系Will的大食堂公眾號。