作者:李義 2006
關(guān)鍵詞:最快 開平方根 算法 中值定理 開方
整數(shù)平方數(shù)中值定理:
設(shè)a、b、c為順序排列間距為P的3個整數(shù),A、B、C是它們的平方
則有:b2＝(a 2+c2)/2-R,即:B＝(A+C)/2-R
其中:修正值R＝P2
特別地,如果間隔P＝1、2、 4、 8、 16、…2 n (或Pn=2Pn-1)時
則: 修正值R＝1、4、16、64、256、…22n (或Rn＝4Rn-1)
證明:
已知:a＝b+P
c＝b-P
有:a 2＝(b+P)2＝b2+2Pb+P2
c2＝(b-P)2＝b2-2Pb+P2
則:a2+c2＝2b2+2P2
即:b2＝(a2+c2)/2-P2
特別地
當:間隔 P＝2 n＝2*2 n -1＝2 Pn-1時(n為自然數(shù))
則:修正值 R＝P2＝22n＝(2 Pn-1)2＝4(P n-1)2＝4Rn-1
(證明完)
根據(jù)以上定理,可以實現(xiàn)整數(shù)快速開平方根計算:
先構(gòu)建一個長度為N的數(shù)組1:
數(shù)組長 N=Ni+1 1 2 3 4 5 …
間隔 P=2Pi 2 4 8 16 32 …
修正值 R=4Ri 4 16 64 256 1024 …
以及一個對應(yīng)2PN(這里N=4、2PN=32)的典型數(shù)和它的平方數(shù)組2:
按N=4間隔
排列的數(shù) d=di+2PN 32 64 96 128 160 192 224 256 …
該數(shù)的平方 D=d2 1024 4096 9216 16384 25600 36864 50176 65536 …
顯然,N值越大則數(shù)組2越小、程序代碼效率越高、用時(插值次數(shù))越多.
以2字節(jié)整數(shù)開方為例的計算流程如下:
其中,被開方數(shù)D(范圍0~65536),其平方根d(范圍0~256)
注:1、查表可以從任何位置開始,對計算速度影響不大.其中D=0、D=1、D=Di、 D>65280判斷可以省去.
2、此算法完全沒有乘法試算,其1/2、1/4除法運算可由二進制移位簡單實現(xiàn),且為完全補償后的精確插值,所以遞歸速度非常快(這里4次).
3、最后運算已經(jīng)包括了小數(shù)部分的精確4舍5入算法.
4、此算法略加改動,即可實現(xiàn)更長字節(jié)整數(shù)或定長浮點數(shù)平方根精確解,其逆運算也可以實現(xiàn)乘方運算.
一個C語言實例:
// sqrt_2 中值定理法開平方程序(直接查表-插值)
// 輸入D (兩字節(jié)無符號整數(shù))
// 輸出d (一字節(jié)無符號整數(shù))
char a,b,c,p;
int A,B,C,D,R,K;
void main()
{D=11111; // 被開方數(shù)
if(D>50176){A=0; a=0; C=50176;c=224;break;}; // 查表
if(D>36864){A=50176;a=224;C=36864;c=192;break;};
if(D>25600){A=36864;a=192;C=25600;c=160;break;};
if(D>16384){A=25600;a=160;C=16384;c=128;break;};
if(D>9216) {A=16384; a=128;C= 9216; c= 96; break;};
if(D>4096) {A= 9216; a= 96; C= 4096; c= 64; break;};
if(D>1024) {A= 4096; a= 64; C= 1024; c= 32; break;};
A= 1024; a= 32; C= 0; c= 0; break;
p=16;R=256; // 初始化數(shù)據(jù)
do{ b=c+p;B=C;B>>=1; // 插值計算循環(huán)
if(A!=0){K=A;K>>=1;}
else K=0x8000; // 65536>>=1的數(shù)
B+=K;B-=R;
if(D>B){C=B;c=b;}
else{A=B;a=b;}
p>>=1;R>>=2;
}while(p!=1); // 循環(huán)4次結(jié)束
K=A-C;K>>=2;A-=K; C+=K; // 小數(shù)部分四舍五入
if(D
if(D
} //開方結(jié)束
進一步研究表明,由于循環(huán)內(nèi)所有運算都是加、減、位移、比較等簡單運算,所花費的時間很少,可以適當加大循環(huán)次數(shù).
特別地,如果把間隔P加大到128,對應(yīng)修正值R=13684,則循環(huán)次數(shù)N=7,對應(yīng)數(shù)組2就簡化到:
按N=7間隔排列的數(shù) d=di+Pn 0 256 512 …
該數(shù)的平方 Di=d*d 0 65536 262144 …
這時,對于兩字節(jié)數(shù)被開方數(shù)D來講,查表環(huán)節(jié)也可省去,程序代碼大幅減少,計算流程如下:
C語言程序的一個例子:
unsigned char a,b,p=0x80;
unsigned int K,A,B,C,R=0x4000,D=60000;
sqt1(){
do{
b=a-p;B=C;B>>=1;
if(A){K=A;K>>=1;}
else K=0x8000;
B+=K;B-=R;
if(D>B)C=B;
else{A=B;a=b;}
p>>=1;R>>=2;
}while(p!=1); //循環(huán)7次結(jié)束
p=(A-C)>>2;A-=p; C+=p;
b=a;
if(D < A)b--;
if(D < C)b--;
} //輸出方根b
程序里只用了一個特別的數(shù)128(及其它的平方數(shù)16384),就能夠把兩字節(jié)數(shù)0~65535范圍內(nèi)的任意整數(shù)的整數(shù)平方根精確(小數(shù)部分嚴格4舍5入)求解.
程序思想還可以繼續(xù)延伸到更長字節(jié)無符號整數(shù)的開方,只需要修改對應(yīng)的初始值p、R就行了.
結(jié)論 :
本文首先提出并證明了整數(shù)平方數(shù)中值定理,進而提出一種基于此定理的的快速開方算法,并給出了具體的計算流程和C語言程序?qū)嵗?由于全部運算不使用乘法運算或冪運算,只使用加、減、移位、邏輯等簡單運算,只引入極少的初始變量,在經(jīng)過有限次循環(huán)后即可迅速逼近任意有限大整數(shù)的整數(shù)平方根的精確解(小數(shù)部分嚴格4舍5入),從而把整數(shù)開平方運算的迄今最快速度提高了一個數(shù)量級.
此算法對于由沒有集成硬件乘法器的芯片組成的微處理(控制)系統(tǒng)、同時要擔負大量開方運算而時間特別緊張的應(yīng)用——如大型游戲程序、圖形處理系統(tǒng)中兩坐標點的距離計算(方根)、交流電壓有效值等控制計算(均方根)——具有一針見血的效果,對于任何高級程序語言、游戲機乃至計算器、民用或工業(yè)控制系統(tǒng)中的開平方函數(shù)代碼的優(yōu)化具有顯著積極的意義.
