在數(shù)據(jù)加密處理中有很多復(fù)雜的加密算法稽莉，這些加密算法往往會(huì)用到很多超大的整數(shù)運(yùn)算课舍。不過(guò)霹俺，程序設(shè)計(jì)語(yǔ)言對(duì)數(shù)據(jù)的大小會(huì)有一定的限制敬特，數(shù)據(jù)太大就會(huì)出現(xiàn)數(shù)據(jù)溢出的情況掰邢，這是無(wú)法進(jìn)行大整型數(shù)據(jù)運(yùn)算的。本文將和大家一起學(xué)習(xí)如何實(shí)現(xiàn)大整數(shù)的數(shù)據(jù)運(yùn)算伟阔，本文代碼我們使用C++實(shí)現(xiàn)辣之。
普通乘數(shù)運(yùn)算
對(duì)于乘數(shù)運(yùn)算有一種比較簡(jiǎn)單較為容易理解的方法，我們可以利用小學(xué)時(shí)期學(xué)的列豎式的計(jì)算方法進(jìn)行乘法運(yùn)算皱炉。
參考上圖中的列豎式計(jì)算方法怀估，我們進(jìn)行代碼實(shí)現(xiàn)。
#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;
}
為了方便我們先將各個(gè)乘數(shù)做了翻轉(zhuǎn)處理合搅，最后需要再將結(jié)果翻轉(zhuǎn)回來(lái)多搀。在運(yùn)算過(guò)程中用來(lái)存放乘法運(yùn)算結(jié)果的數(shù)組，我們沒(méi)有進(jìn)行移位處理同列相加灾部，而是對(duì)角線相加康铭，這樣可以減少空間和運(yùn)算步驟。上面的代碼運(yùn)行結(jié)果如下所示梳猪。
因?yàn)樽址拈L(zhǎng)度沒(méi)有特別的限制麻削，所以上面的算法可以適用大整數(shù)運(yùn)算。
分治算法
雖然上面的列豎式的方法可以很好的解決大整數(shù)乘法的問(wèn)題春弥，但是我們還用一種更加高效的方法可以選擇，這就是分治（Divide and Conquer）算法叠荠。它是一種非常重要的算法匿沛，可以應(yīng)用到很多領(lǐng)域，比如快速排序榛鼎，二分搜索等逃呼。從算法的名字我們可以看出它是將大的問(wèn)題拆分進(jìn)行細(xì)化，由大變小者娱，先將小的問(wèn)題解決抡笼，最終將這個(gè)問(wèn)題解決，所以叫Divide and Conquer黄鳍。在這里我們可以通過(guò)這種方法將大整數(shù)進(jìn)行拆分推姻，拆分成一個(gè)個(gè)可以通過(guò)程序語(yǔ)言直接進(jìn)行運(yùn)算的小整進(jìn)行計(jì)算，最后求得到大整數(shù)的值框沟。
假設(shè)有兩個(gè)大整數(shù)藏古，我們?cè)O(shè)為a（大小為n位）和b（大小為m位）增炭，這里我們將使用二分法對(duì)數(shù)據(jù)進(jìn)行拆分，這兩個(gè)整數(shù)我們可以分解為：
則,
令拧晕，
根據(jù)上面公式里隙姿，我們可以將a*b分解為四個(gè)小的整數(shù)的乘法，即z3,z2,z1,z0四個(gè)表達(dá)式厂捞。如果分解出來(lái)的乘法數(shù)值還是很大输玷，還可以按照同樣的方法進(jìn)行拆解直到拆解成較小的數(shù)值乘法，直到計(jì)算機(jī)程序語(yǔ)言可以直接運(yùn)算靡馁。
比如饲嗽，上面的3456和1234相乘，參考下圖通過(guò)二分法逐級(jí)對(duì)整數(shù)進(jìn)行拆分奈嘿，我們將兩個(gè)整數(shù)拆分到一位整數(shù)進(jìn)行運(yùn)算貌虾。
下面我們看一下分治算法的代碼實(shí)現(xiàn)，這里我們使用遞歸的方法裙犹。
#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;
}
程序的運(yùn)行結(jié)果如下：
