杜青
（南京工程學(xué)院 計(jì)算機(jī)工程學(xué)院，江蘇 南京 211167）
摘要：本文以C++語(yǔ)言設(shè)計(jì)了大整數(shù)類，在類中以數(shù)組存儲(chǔ)大整數(shù)，同時(shí)借鑒分治算法思想實(shí)現(xiàn)了大整數(shù)的乘法運(yùn)算。算法中將被乘數(shù)與乘數(shù)按照相同位數(shù)進(jìn)行分組，通過(guò)對(duì)每組較小數(shù)值整數(shù)進(jìn)行乘法和加法運(yùn)算而得到大整數(shù)相乘的積。該程序在VC++2015開(kāi)發(fā)平臺(tái)調(diào)試通過(guò)。測(cè)試結(jié)果表明，當(dāng)每個(gè)分組數(shù)據(jù)位數(shù)多時(shí)，運(yùn)算速度顯著提高。
關(guān)鍵詞：大整數(shù)；大整數(shù)相乘；分治算法；類
中圖分類號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：ADOI： 10.19358/j.issn.1674-7720.2017.02.003
引用格式：杜青.基于類的大整數(shù)乘法運(yùn)算的實(shí)現(xiàn)［J］.微型機(jī)與應(yīng)用，2017,36（2）：8-9，13.
0引言
大整數(shù)是指數(shù)值很大、超出計(jì)算機(jī)整數(shù)表達(dá)和處理范圍的非負(fù)整數(shù)。一般計(jì)算機(jī)能夠處理的整數(shù)有三種類型，即2字節(jié)（16 bit）、4字節(jié)（32 bit）和8字節(jié)（64 bit）整數(shù)，其中8字節(jié)整數(shù)取值范圍最大，8字節(jié)無(wú)符號(hào)整數(shù)取值范圍是：0～264-1。當(dāng)整數(shù)值超過(guò)整數(shù)范圍的最大值264-1時(shí)，計(jì)算機(jī)無(wú)法直接處理。
大整數(shù)的乘法運(yùn)算在密碼學(xué)等領(lǐng)域有著廣泛的應(yīng)用。如著名的公鑰加密算法RSA算法，大整數(shù)相乘是其中必不可少的運(yùn)算，由于運(yùn)算中使用的密鑰推薦位數(shù)為1 024位，為了達(dá)到更高安全級(jí)別，密鑰長(zhǎng)度甚至達(dá)到上萬(wàn)位，遠(yuǎn)遠(yuǎn)超出計(jì)算機(jī)所能直接處理的64 bit的整數(shù)范圍。
當(dāng)需要對(duì)大整數(shù)進(jìn)行乘法運(yùn)算時(shí)，面臨的問(wèn)題是：如何存儲(chǔ)大整數(shù)以及如何提高大整數(shù)乘法的運(yùn)算速度。已有的實(shí)現(xiàn)大整數(shù)乘法的程序中，有的采用累加的方式，將被乘數(shù)重復(fù)相加若干次，累加的次數(shù)等于乘數(shù)；有的按照手算的形式，將乘數(shù)逐位與被乘數(shù)相乘，并將結(jié)果做位移運(yùn)算后按位求和［1］。當(dāng)被乘數(shù)與乘數(shù)位數(shù)很多時(shí)，這些方法運(yùn)算時(shí)間長(zhǎng)。
本文以C++語(yǔ)言設(shè)計(jì)了一個(gè)大整數(shù)類，在類中以數(shù)組存儲(chǔ)大整數(shù)，同時(shí)借鑒分治算法的思想［2］，將數(shù)值很大的大整數(shù)分解為若干組數(shù)值較小的整數(shù)，通過(guò)對(duì)每組較小數(shù)值整數(shù)的運(yùn)算得到大整數(shù)相乘的積。程序在VC++2015開(kāi)發(fā)平臺(tái)調(diào)試通過(guò)。
1大整數(shù)的存儲(chǔ)
由于大整數(shù)位數(shù)多，若用字符串形式表示，在做運(yùn)算時(shí)，首先要將表示大整數(shù)的字符串轉(zhuǎn)換成數(shù)值。轉(zhuǎn)換時(shí)考慮到大整數(shù)的數(shù)值一般超出整數(shù)的取值范圍，所以采用整型數(shù)組存儲(chǔ)其值［3］。
以下給出了大整數(shù)類BigInt的聲明，類中的數(shù)據(jù)成員uint64_t 類型數(shù)組array用于存放大整數(shù)，uint64_t是64 bit無(wú)符號(hào)整數(shù)類型。轉(zhuǎn)換時(shí)從大整數(shù)字符串最低位開(kāi)始，每K個(gè)字符為一組，最高位不足K個(gè)字符時(shí)補(bǔ)0，將每組字符轉(zhuǎn)換為一個(gè)數(shù)值較小的整數(shù)，每個(gè)較小整數(shù)存放到整型數(shù)組的一個(gè)元素中。類中數(shù)據(jù)成員n為已存放了數(shù)據(jù)的元素個(gè)數(shù)，即分組數(shù)。類聲明代碼如下：
#define N 10000//數(shù)組大小
#define K 3//每個(gè)分組中包含的字符個(gè)數(shù)
class BigInt
{public:
BigInt();//無(wú)參構(gòu)造函數(shù)，將n置0
BigInt(string str);//轉(zhuǎn)換構(gòu)造函數(shù)
int compare(BigInt num); //比較類對(duì)象大小
friend BigInt operator*(BigInt num1, BigInt num2);//重載乘法運(yùn)算符
friend int operator>(BigInt num1, BigInt num2);
//重載大于運(yùn)算符
private:
uint64_t array［N］;//存放大整數(shù)的數(shù)組
int n;//存放了數(shù)據(jù)的元素個(gè)數(shù)
};
類中的轉(zhuǎn)換構(gòu)造函數(shù)實(shí)現(xiàn)了將大整數(shù)字符串分組，并將各組字符串轉(zhuǎn)換為數(shù)值存放到array數(shù)組中的操作。轉(zhuǎn)換構(gòu)造函數(shù)的代碼如下：
BigInt::BigInt(string str) //將字符串轉(zhuǎn)換為數(shù)值
{int end = str.length() - 1, i;
uint32_ttemp,w;//w代表權(quán)重
n = 0;
i = end;//從最低位開(kāi)始處理
while (i >= 0)
{temp = 0;w = 1;
for (int k =0;k<K;k++) //K個(gè)字符組成1個(gè)數(shù)
{if (str［i］ >= 0&&str［i］ <= 9)
{temp = temp + w*(str［i］ - 0);
w *= 10; i--;
if (i<0)break;
}
}
array［n］ = temp;n++;
}
for (i = n;i<N;i++) array［i］ = 0; //其他元素置0
}
當(dāng)K=3時(shí)，字符串“1234567890”在數(shù)組array中存放的形式如圖1所示。
2大整數(shù)乘法的實(shí)現(xiàn)
2.1大整數(shù)乘法的算法
當(dāng)一個(gè)m位的大整數(shù)X與一個(gè)n位的大整數(shù)Y相乘時(shí)，如按照手算的方式進(jìn)行計(jì)算，需要將Y的每一位與X的每一位相乘，共要做m×n次數(shù)據(jù)相乘。如m、n很大，則數(shù)據(jù)相乘次數(shù)多，從而使整個(gè)乘法運(yùn)算時(shí)間長(zhǎng)。
為了解決這個(gè)問(wèn)題，利用分治法的思想，將X、Y均分解為K位一組的整數(shù)［4］，即X分解為…xi…x2x1x0，共(m+K-1)/K組數(shù)字，Y分解為…yj…y2y1y0，共 (n+K-1)/K組數(shù)字，運(yùn)算時(shí)將由Y分解得到的每一組整數(shù)yj與由X分解得到的每一組整數(shù)xi相乘。
以K=3時(shí)，1234567890與1234567890做乘法運(yùn)算為例，如按手算方式進(jìn)行運(yùn)算，需做10×10共100次數(shù)據(jù)相乘，而若將被乘數(shù)與乘數(shù)分解為3位一組的數(shù)字，即各自分解為4組數(shù)字，如圖2所示，則只需要完成4×4共16次數(shù)據(jù)相乘，數(shù)據(jù)相乘次數(shù)大大減少。在進(jìn)行分組數(shù)據(jù)相乘后，再按組進(jìn)行數(shù)據(jù)相加，從而得到兩個(gè)大整數(shù)乘法運(yùn)算的積。大整數(shù)分組運(yùn)算過(guò)程示意圖如圖2所示。
當(dāng)K較大時(shí)，每組數(shù)據(jù)因位數(shù)增加而數(shù)值變大，分組數(shù)目隨之減少，分組數(shù)據(jù)乘法次數(shù)也減少。但當(dāng)K過(guò)大時(shí)，每組數(shù)據(jù)與其他組數(shù)據(jù)相乘時(shí)得到的中間結(jié)果可能會(huì)超出整型數(shù)據(jù)的最大值而導(dǎo)致數(shù)據(jù)溢出。為了防止溢出情況的出現(xiàn)，K的取值不能太大。由于uint64的最大值是264-1，因此每組數(shù)字的最大值不能超過(guò)232-1，即4 294 967 295，由此推斷，每組數(shù)字不能超過(guò)9位，即K要滿足：1≤K≤9。
2.2大整數(shù)乘法的實(shí)現(xiàn)
m位的大整數(shù)X與n位的大整數(shù)Y進(jìn)行乘法運(yùn)算時(shí)，將yj依次與xi相乘，保留xi*yj%BASE為中間結(jié)果，yj*xi/BASE為進(jìn)位，其中BASE的值等于10K，是運(yùn)算的基［5］。兩個(gè)大整數(shù)相乘后得到的乘積的位數(shù)是m+n或m+n-1［6］。
下面給出了實(shí)現(xiàn)大整數(shù)乘法運(yùn)算的函數(shù)定義，該函數(shù)是乘法運(yùn)算符重載函數(shù)，已在BigInt類中聲明為友元。該函數(shù)代碼如下：
#define BASE 1000 //運(yùn)算的基
BigInt operator*(BigInt num1, BigInt num2)
{BigInt temp1, temp2;
if (num2>num1)//保證被乘數(shù)大于乘數(shù)
{temp1=num1; num1=num2; num2=temp1;}
uint64_t num, c;//num存放中間結(jié)果,c為進(jìn)位
int maxi, mini, i, j;
maxi = num1.n; //被乘數(shù)分組數(shù)
mini = num2.n; //乘數(shù)分組數(shù)
for (i = 0;i<mini;i++)
{c = 0;//進(jìn)位初值為0
for (j = 0;j<maxi;j++)
{num = num1.array［j］ * num2.array［i］ + c;
temp2.array［j+i］+=num%BASE; //做一次
//分組相乘之后做分組加法
c = num / BASE;
if (temp2.array［j + i］ >= BASE)//判斷是
//否超出BASE
{temp2.array［j+i］=temp2.array［j+i］%BASE;
c++;//進(jìn)位加1
}
}
if (c) temp2.array［j + i］ += c; //有進(jìn)位時(shí)
}
temp2.n = maxi + mini - 1;//設(shè)置乘積的分組數(shù)
if (c) temp2.n++; //最后一次運(yùn)算有進(jìn)位時(shí)
return temp2;
}
以上實(shí)現(xiàn)大整數(shù)乘法的函數(shù)中，做一次分組數(shù)據(jù)相乘之后，將得到的中間結(jié)果做分組加法運(yùn)算，并且在做分組加法運(yùn)算時(shí)，要判斷加法運(yùn)算的結(jié)果是否溢出，若溢出，將加法運(yùn)算結(jié)果對(duì)BASE取余數(shù)，同時(shí)進(jìn)位加1。
2.3運(yùn)行測(cè)試
在VC++2015開(kāi)發(fā)平臺(tái)運(yùn)行程序，測(cè)試時(shí)用兩個(gè)4 000位大整數(shù)做乘法，且使該乘法運(yùn)算重復(fù)執(zhí)行1 000次，測(cè)試當(dāng)K取1、2、3、……、9不同值時(shí)所花費(fèi)時(shí)間，得到結(jié)果如表1所示。由表1可以看出，K值增大，大整數(shù)乘法運(yùn)行時(shí)間大大減少。
3結(jié)論
本文以C++類的方式實(shí)現(xiàn)了大整數(shù)的乘法運(yùn)算，算法中根據(jù)分治法思想，將被乘數(shù)與乘數(shù)按照相同位數(shù)進(jìn)行分組，通過(guò)對(duì)每組較小數(shù)值整數(shù)進(jìn)行運(yùn)算，從而得到大整數(shù)相乘的結(jié)果。該程序在VC++2015開(kāi)發(fā)平臺(tái)調(diào)試通過(guò)。實(shí)驗(yàn)結(jié)果表明，當(dāng)每個(gè)分組數(shù)據(jù)位數(shù)多時(shí)，乘法運(yùn)算速度顯著提高。
參考文獻(xiàn)
?。?］ 周健,李順東,薛丹.改進(jìn)的大整數(shù)相乘快速算法［J］.計(jì)算機(jī)工程,2012,38(16):121-123.
［2］ 王曉東. 計(jì)算機(jī)算法設(shè)計(jì)與分析(第3版)［M］. 北京:清華大學(xué)出版社, 2014.
?。?］ 楊燦,桑波.大整數(shù)乘法運(yùn)算的實(shí)現(xiàn)及優(yōu)化［J］.計(jì)算機(jī)工程與科學(xué),2013,35(3):183-190.
?。?］ 王念平,金晨輝.用分治算法求大整數(shù)相乘問(wèn)題的進(jìn)一步分析［J］.電子學(xué)報(bào),2008,36(1):133-135.
?。?］ 李文化,董克家.大整數(shù)精確運(yùn)算的數(shù)據(jù)結(jié)構(gòu)與基選擇［J］.計(jì)算機(jī)工程與應(yīng)用,2006,42(32):24-26.
?。?］ 劉覺(jué)夫,周娟.大整數(shù)運(yùn)算的基選擇［J］.華東交通大學(xué)學(xué)報(bào),2007,24(2):100102.