重慶建設(shè)中學(xué) 楊宏偉

　　我們知道計(jì)算機(jī)的計(jì)算精度不是無限大的，甚至是十分有限的。CPU的字長和操作系統(tǒng)的處理能力直接制約著運(yùn)算精度和運(yùn)算能力。隨著計(jì)算機(jī)應(yīng)用的深入，人們對計(jì)算能力的需求，尤其是精度的需求，越來越高。雖然目前32位CPU及操作系統(tǒng)提供的計(jì)算精度，較之從前已有很大的提高，而且精度更高的64位CPU及操作系統(tǒng)正在普及，但是，對許多計(jì)算機(jī)應(yīng)用課題來說，能不能具有不直接依賴硬件條件的高精度、高性能計(jì)算能力仍是至關(guān)重要的。為此，設(shè)計(jì)高精度計(jì)算的軟件包，用軟件方法實(shí)現(xiàn)高精度計(jì)算，是一件有實(shí)用價值的工作。例如，目前在電子商務(wù)應(yīng)用中，密碼的校驗(yàn)及計(jì)算就是對高精度計(jì)算的典型需求。

分析問題

由于C語言具有執(zhí)行效率高、支持動態(tài)存儲分配等特點(diǎn)，我們選用C語言編寫了一套工具函數(shù)，供高精度計(jì)算使用。乘法運(yùn)算在計(jì)算機(jī)運(yùn)算中是一種基本運(yùn)算，它的計(jì)算過程對整個計(jì)算效率有舉足輕重的影響。仔細(xì)研究乘法運(yùn)算對高精度計(jì)算十分必要。

為了實(shí)現(xiàn)高精度計(jì)算，首先要建立高精度的數(shù)據(jù)表示方法。我們采用將整數(shù)和小數(shù)分開，組成兩個隊(duì)列的方法存儲數(shù)據(jù)。這種方法不僅節(jié)約存儲空間，而且有利于確保整數(shù)運(yùn)算的精度。

描述運(yùn)算對象的數(shù)據(jù)結(jié)構(gòu)如下：

struct VARARRAY {

char cDigit; //保存數(shù)據(jù)位

//指向下一個數(shù)據(jù)位

struct VARARRAY ＊ spNext;

};

　

struct SUPERNUMBER

{

//指向最低位整數(shù)

struct VARARRAY ＊ spIntPart;

　

//指向最低位小數(shù)

struct VARARRAY ＊ spDecPart;

　

//指向最高位整數(shù)

struct VARARRAY ＊ spIntLast;

　

//指向最高位小數(shù)

struct VARARRAY ＊ spDecLast;

　

int iNumberInt; //整數(shù)位數(shù)

int iNumberDec; //小數(shù)位數(shù)

char cSign;

}; //符號位

在用SUPERNUMBER結(jié)構(gòu)描述運(yùn)算對象的基礎(chǔ)上，我們定義了一套函數(shù)，全面實(shí)現(xiàn)SUPERNUMBER型數(shù)據(jù)的輸入、輸出、賦值、比較、加、減、乘、除、整除等運(yùn)算功能。本文重點(diǎn)介紹無精度損失的乘法計(jì)算方法及主要函數(shù)的設(shè)計(jì)。

乘法算法

為了不損失計(jì)算精度，我們將乘法轉(zhuǎn)換為加法實(shí)現(xiàn)，基本算法如下：

1．將數(shù)符較多的數(shù)據(jù)表示為X，作為加數(shù)，數(shù)符較少的數(shù)據(jù)表示為Y，控制加法次數(shù)；

2．如果Y含有小數(shù)部分，將Y轉(zhuǎn)變?yōu)榧冋麛?shù)YDEC，并記錄小數(shù)點(diǎn)的右移位數(shù)I；

3．初始化返回值T為0，取得Y的位數(shù)WIDTH，設(shè)計(jì)數(shù)器COUNT為0；

4．取Y右側(cè)第COUNT＋1位，以此數(shù)為次數(shù)加X，再左移COUNT位，加到T中；

5．把COUNT加1；

6．若COUNT等于WIDTH，轉(zhuǎn)下一步，否則轉(zhuǎn)第4步；

7．將T中的小數(shù)點(diǎn)左移I位；

8．返回T，得到乘法結(jié)果。

本算法的特點(diǎn)是加法次數(shù)少，若Y的寬度為W，最多進(jìn)行9×W次加法及W次移位即可。

乘法函數(shù)

乘法函數(shù)通過把兩個SUPERNUMBER型的數(shù)據(jù)相加實(shí)現(xiàn)運(yùn)算目的，其結(jié)果通過指針返回。

struct SUPERNUMBER ＊ su_mu(

struct SUPERNUMBER ＊ spSourceOne,

struct SUPERNUMBER ＊ spSourceTwo)

{

struct SUPERNUMBER ＊ spNew;

struct SUPERNUMBER ＊ spYDec;

struct SUPERNUMBER ＊ spX，＊ spY，＊ spC，＊ spT;

struct VARARRAY ＊ spTem;

int iYDec,iWidth,iDigit,iC1,iC2;

spNew=su_as(“0”);

if (spSourceOne－>iNumberInt＋spSourceOne－>iNumberDec>=spSourceTwo－>iNumberInt＋

spSourceTwo－>iNumberDec){

spX=su_co(spSourceOne);

spY=su_co(spSourceTwo);

}

else{

spY=su_co(spSourceOne);

spX=su_co(spSourceTwo);

}

iYDec=spY－>iNumberDec;

spYDec=su_mo(spY,iYDec);

iWidth=spYDec－>iNumberInt;

spTem=spYDec－>spIntPart;

for(iC1=0;iC1<iWidth;iC1＋＋)

{

iDigit=(int)(spTem－>cDigit－‘0’);

spTem=spTem－>spNext;

spC=su_as(“0”);

for(iC2=0;iC2<iDigit;iC2＋＋)

{

spT=su_ad(spC,spX);

su_fr(spC);

spC=su_co(spT);

su_fr(spT);

　

}

spT=su_mo(spC,iC1);

su_fr(spC);

spC=su_ad(spNew,spT);

su_fr(spNew);su_fr(spT);

spNew=su_co(spC);

su_fr(spC);

}

spT=su_mo(spNew,－iYDec);

su_fr(spNew);

spNew=su_co(spT);

su_fr(spT);

su_fr(spYDec);

su_fr(spX);

su_fr(spY);

return spNew;

}

在此函數(shù)中，我們使用了在高精度計(jì)算軟件包中定義的其他函數(shù)（本文省略其實(shí)現(xiàn)代碼），主要有：

1．將字符串轉(zhuǎn)化為SUPERNUMBER類型：

struct SUPERNUMBER ＊ su_as(char＊zpSource);

2．將一個SUPERNUMBER復(fù)制到另一個SUPERNUMBER中：

struct SUPERNUMBER ＊ su_co(struct SUPERNUMBER ＊ spSource);

3．兩個SUPERNUMBER的“等于”關(guān)系運(yùn)算，若相等，返回1：

int su_ee(struct SUPERNUMBER ＊ spSource, struct SUPERNUMBER ＊ spDesti);

4．兩個SUPERNUMBER數(shù)的加法運(yùn)算：

struct SUPERNUMBER ＊ su_ad(struct

SUPERNUMBER ＊ spSource,struct SUPERNUMBER ＊ spDestination);

5．SUPERNUMBER與用整數(shù)表示的數(shù)據(jù)的加法運(yùn)算：

struct SUPERNUMBER ＊ su_si(

struct

SUPERNUMBER ＊ spSource, int iDesti);

6．移動小數(shù)點(diǎn)：

struct SUPERNUMBER ＊ su_mo(struct

SUPERNUMBER ＊ spSource, int iNum);

7．釋放SUPERNUMBER數(shù)據(jù)的存儲空間：

void su_fr(struct SUPERNUMBER ＊ spSource)；

應(yīng)用實(shí)例

當(dāng)我們計(jì)算16的階乘時，常規(guī)的方法難于直接得到正確的結(jié)果，即使定義長整型(long int)數(shù)據(jù)，在計(jì)算出11的階乘39916800之后，也開始出現(xiàn)數(shù)據(jù)錯誤。但是利用本文介紹的方法，可精確地計(jì)算出從1到16的階乘值。代碼如下：

FILE ＊ fp;

struct SUPERNUMBER ＊ spX;

struct SUPERNUMBER ＊ spY;

struct SUPERNUMBER ＊ spZ;

struct SUPERNUMBER ＊ spSum;

fp=fopen(“abcd.txt”,“a＋”);

if (fp==NULL) MessageBox(hWndMain,“file error”,“”,MB_OK);

//初始化變量

spX=su_as(“0”);

spY=su_as(“30”);

spSum=su_as(“1”);

//計(jì)算從1到16的階乘值

lp: spZ=su_si(spX,1);

su_fr(spX);

spX=su_co(spZ);

su_fr(spZ); spZ=su_mu(spSum,spX);

su_fr(spSum);

spSum=su_co(spZ);

su_fr(spZ);

su_os(spSum);

su_of(spX,fp);

su_of(spSum,fp);

if (!su_ee(spY,spX)) goto lp;

　

fclose(fp);

運(yùn)算結(jié)果為：

1 ! 1 2! 2

3 ! 6 4! 24

…

13 ! 6227020800 14! 87178291200

15 ! 1307674368000 16! 20922789888000