大數乘方　趣味編程

[摘要]針對計算機精度位數的限制，編程制作乘方計算器工具，可以精確計算底數在10100以內，指數在108以內，結果在101000以內非負整數的乘方。

[關鍵詞]大數乘方 編程

中圖分類號：TP3文獻標識碼：A文章編號：1671－7597（2009）0220068－01

在歷屆的數學競賽里，總會出現一些較大數字的乘方運算，比如22005-22004。雖然這些題目都有巧妙的方法可以很快的得到答案，但無法把這些乘方運算化為準確的數字。競賽后想用家用電腦驗證，卻因為數字太大超出計算范圍而無法計算。

算法：用初值1逐次乘輸入的底數，一共乘指數次，就是得數。

因為電腦算多位數之間的乘法是很慢的，而且如果得數很大還會受位數限制，所以我就把底數按位分成很多一位數，把每次做乘法后的結果也按位分成很多一位數，然后將這些一位數兩兩相乘，加到結果中相應的各位上，然后如果某一位超過9，就留下它的個位并把十位及以后的數字加到后一位去（進位）。

比如16*16，6*6=36，1*6=6，6*1=6，1*1=1，結果為1，（6+6=）12，36。個位進3，結果變為1，15，6。十位進1，得到2，5，6。

256*16，6*6=36，5*6=30，6*1=6，5*1=5，2*6=12，2*1=2，結果為2，（12+5=）17，（30+6=）36，36，個位進3，結果變成2，17，39，6。十位進3，變成2，20，9，6，百位進2，變成4，0，9，6。

比如算22008，輸入2-2008，回車后不到1秒鐘就會打印出結果：

29，392，145，799，020，915，820，360，529，950，148，658，790，971，333，173，470，597，132，227，654，062，739，616，291，644，680，034，730，482，849，702，560，509，912，216，694，758，079，047，000，246，245，398，094，216，484，503，842，717，866，321，546，017，277，221，199，943，680，176，327，461，949，451，487，085，805，309，456，252，478，664，093，558，693，475，421，170，513，158，666，359，386，616，551，679，118，889，574，095，089，825，179，039，567，782，281，258，040，824，405，166，424，107，240，700，021，377，434，209，148，110，825，999，078，639，302，784，109，824，695，476，896，212，613，634，081，852，488，010，690，884，578，129，204，889，342，821，483，040，517，575，643，751，434，792，922，414，912，394，467，695，078，935，531，662，069，192，598，956，042，024，980，981，047，457，429，185，377，388，949，433，859，975，257，289，323，374，605，954，282，310，600，673，952，044，911，495，373，010，647，749，329，399，156，163，119，321，894，151，520，256。

另外的一些數字也經過驗證得到了正確答案，比如

甚至可以算出23000，時間都在一兩秒之內。

這樣，以后考試時能夠用簡便的計算來求解，考試后也能用家用電腦進行窮舉驗證，算出答數了。

附程序（已在VC環境下調試驗證通過）：

#include＜stdio.h＞

#include＜string.h＞

int main(){

/**********定義，計算結果在1000位以下**********/

long int a[1000]，b[100]，c，a1[1000]，i，j，k，s，m；

char ch；

FILE *in；

in=fopen("POW.txt"，"w")；

/**********輸入底數，不超過100位**********/

for(s=0；；s++){

ch=getchar()；

b[s]=ch-48；

if(!(b[s]＞-1&&b[s]＜10)){

b[s]=0；

break；

}

}

/**********輸入指數，不超過8位**********/

scanf("%ld"，&c)；

/**********將結果初始化為1**********/

a[0]=1；

for(i=1；i＜1000；i++)a[i]=0；

/**********共乘指數次**********/

for(i=0；i＜c；i++){

/**********預備**********/

for(j=0；j＜1000；j++){

a1[j]=a[j]；

}

for(j=0；j＜1000；j++){

a[j]=0；

}

/**********將分解開來的一位數兩兩相乘，加到結果的各位上**********/

for(j=0；j＜1000；j++){

for(k=s-1；k＞-1；k--){

a[j+s-1-k]=a[j+s-1-k]+a1[j]*b[k]；

}

}

/**********進位**********/

m=0；

for(j=0；j＜1000；j++){

a[j]+=m；

m=(a[j]-a[j]%10)/10；

a[j]-=m*10；

}

}

/**********因為s接下來要充當分隔符，重置**********/

s=1；

/**********打印在屏幕上**********/

k=0；

for(i=999；i＞0；i--){

J=a[i]；

if(a[i]!=0&&k==0){k=1；s=2-(i%3)；}

if(k==1){printf("%d"，(int)j)；s++；}

if(s%3==0)printf("，")；

}

Printf("%d"，a[0])； printf(" ")；

/*如果想將結果打印在文件里，可以把這段改為：for(i=999；i＞0；i--){

j=a[i]；

If(a[i]!=0&&k==0){k=1；s=2-(i%3)；}

if(k==1){fprintf(in，"%d"，(int)j)；s++；}

if(s%3==0)fprintf(in，"，")；

}fprintf(in，"%d"，a[0])；

Fprintf(in，" ")； */

fclose(in)；

return(0)；

}

參考文獻：

[1]《聰明在于勤奮 天才在于積累》，華羅庚著，中國少年兒童出版社，P118-119.

[2]《C程序設計》，譚浩強著，清華大學出版社.

作者簡介：

郭天魁，男，漢，浙江杭州，杭州建蘭中學，主要研究方向：程序綜合設計與數學證明。