1、整數(shù)平方數(shù)中值定理：設(shè)a、b、c為順序排列間距為P的3個(gè)整數(shù)，A、B、C是它們的平方則有：b2（a2c2）2R，即：B（AC）2R其中：修正值RP2特別地，如果間隔P1、2、 4、 8、 16、2 n (或Pn=2Pn-1）時(shí)則： 修正值R1、4、16、64、256、22n (或Rn4Rn-1）證明：已知：abPcbP有：a2(bP)2b22PbP2c2（bP）2b22PbP2則：a2c22b22P2即：b2（a2c2）2P2特別地當(dāng)：間隔 P2 n2*2 n -12 Pn-1時(shí)（n為自然數(shù)）則：修正值 RP222n（2 Pn-1）24（P n-1）24Rn-1（證明完）根據(jù)以上定理，可以實(shí)現(xiàn)

2、整數(shù)快速開平方根計(jì)算：先構(gòu)建一個(gè)長度為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 以及一個(gè)對(duì)應(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í)（插值次數(shù)）越多。以2字節(jié)整數(shù)開方為例的計(jì)算流程如下：其中，被開方數(shù)D（范圍06

3、5536），其平方根d（范圍0256）注：1、查表可以從任何位置開始，對(duì)計(jì)算速度影響不大。其中D=0、D=1、D=Di、 D65280判斷可以省去。2、此算法完全沒有乘法試算，其1/2、1/4除法運(yùn)算可由二進(jìn)制移位簡單實(shí)現(xiàn)，且為完全補(bǔ)償后的精確插值，所以遞歸速度非常快（這里4次）。3、最后運(yùn)算已經(jīng)包括了小數(shù)部分的精確4舍5入算法。4、此算法略加改動(dòng)，即可實(shí)現(xiàn)更長字節(jié)整數(shù)或定長浮點(diǎn)數(shù)平方根精確解.一個(gè)C語言實(shí)例：/ sqrt_2 中值定理法開平方程序(直接查表-插值)/ 輸入D (兩字節(jié)無符號(hào)整數(shù))/ 輸出d (一字節(jié)無符號(hào)整數(shù))char a,b,c,p;int A,B,C,D,R,K; voi

4、d main() D=11111; / 被開方數(shù) if(D50176)A=0； a=0; C=50176;c=224;break; / 查表 if(D36864)A=50176;a=224;C=36864;c=192;break; if(D25600)A=36864;a=192;C=25600;c=160;break; if(D16384)A=25600;a=160;C=16384;c=128;break; if(D9216) A=16384; a=128;C= 9216; c= 96; break; if(D4096) A= 9216; a= 96; C= 4096; c= 64; brea

5、k; if(D1024) 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; / 插值計(jì)算循環(huán) if(A!=0)K=A;K=1; else K=0x8000; / 65536=1的數(shù) B+=K;B-=R; if(DB)C=B;c=b; elseA=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(DC)b=c; else if(D

6、=1; if(A)K=A;K=1; else K=0x8000; B+=K;B-=R; if(DB)C=B; elseA=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(DA)b-; if(DC)b-; /輸出方根b程序里只用了一個(gè)特別的數(shù)128（及其它的平方數(shù)16384），就能夠把兩字節(jié)數(shù)065535范圍內(nèi)的任意整數(shù)的整數(shù)平方根精確（小數(shù)部分嚴(yán)格4舍5入）求解。程序思想還可以繼續(xù)延伸到更長字節(jié)無符號(hào)整數(shù)的開方，只需要修改對(duì)應(yīng)的初始值p、R就行了。 結(jié)論 ：本文首先提出并證明了整數(shù)平方數(shù)中值定理，進(jìn)而提出一種基于

7、此定理的的快速開方算法，并給出了具體的計(jì)算流程和C語言程序?qū)嵗Ｓ捎谌窟\(yùn)算不使用乘法運(yùn)算或冪運(yùn)算，只使用加、減、移位、邏輯等簡單運(yùn)算，只引入極少的初始變量，在經(jīng)過有限次循環(huán)后即可迅速逼近任意有限大整數(shù)的整數(shù)平方根的精確解（小數(shù)部分嚴(yán)格4舍5入。 以下是大明輪王點(diǎn)評(píng):說自己最快是要證明的:) 否定他只要舉出一個(gè)更快的，更簡單的。中國古代就有地道的開方術(shù)，原理是一位一位的嘗試，寫出來就是程序sqrt_1，很容易理解，但是用了乘法。通過二項(xiàng)式定理進(jìn)行一系列優(yōu)化，可以得到程序sqrt_5,只用了加減和移位，對(duì)結(jié)果四舍五入，供你參考比較! (程序是我摘錄的，非原創(chuàng)) 如果需要軟件實(shí)現(xiàn)的浮點(diǎn)庫, 開源的Softfloat很好。 #define N_BITS 32#define MAX_BIT (N_BITS + 1) / 2 - 1) unsigned long sqrt_1(unsigned long x)register int i; register unsigned long m, r, root; root = 0; m = 1 = 0; i-) r = root + m; if (r * r = 1; return root; unsigned long sqrt_5(unsigned lon