單片機(jī)開(kāi)平方的快速算法

因?yàn)楣ぷ鞯男枰趩纹瑱C(jī)上實(shí)現(xiàn)開(kāi)根號(hào)的操作。目前開(kāi)平方的方法大部分是用牛頓迭代法。我在查了一些資料以后找到了一個(gè)比牛頓迭代法更加快速的方法。不敢獨(dú)享，介紹給大家，希望會(huì)有些幫助。

1.原理

因?yàn)榕虐娴脑颍胮ow（X，Y）表示X的Y次冪，用B［0］，B［1］，。..，B［m-1］表示一個(gè)序列，

其中［x］為下標(biāo)。

假設(shè)：

B［x］，b［x］都是二進(jìn)制序列，取值0或1。

M = B［m-1］*pow（2，m-1） + B［m-2］*pow（2，m-2） + 。.. + B［1］*pow（2，1） + B［0］*pow

（2，0）

N = b［n-1］*pow（2，n-1） + b［n-2］*pow（2，n-2） + 。.. + b［1］*pow（2，1） + n［0］*pow

（2，0）

pow（N，2） = M

（1） N的最高位b［n-1］可以根據(jù)M的最高位B［m-1］直接求得。

設(shè) m 已知，因?yàn)?pow（2， m-1） 《= M 《= pow（2， m），所以 pow（2， （m-1）/2） 《= N 《=

pow（2， m/2）

如果 m 是奇數(shù)，設(shè)m=2*k+1，

那么 pow（2，k） 《= N 《 pow（2， 1/2+k） 《 pow（2， k+1），

n-1=k， n=k+1=（m+1）/2

如果 m 是偶數(shù)，設(shè)m=2k，

那么 pow（2，k） 》 N 》= pow（2， k-1/2） 》 pow（2， k-1），

n-1=k-1，n=k=m/2

所以b［n-1］完全由B［m-1］決定。

余數(shù) M［1］ = M - b［n-1］*pow（2， 2*n-2）

（2） N的次高位b［n-2］可以采用試探法來(lái)確定。

因?yàn)閎［n-1］=1，假設(shè)b［n-2］=1，則 pow（b［n-1］*pow（2，n-1） + b［n-1］*pow（2，n-2），

2） = b［n-1］*pow（2，2*n-2） + （b［n-1］*pow（2，2*n-2） + b［n-2］*pow（2，2*n-4）），

然后比較余數(shù)M［1］是否大于等于 （pow（2，2）*b［n-1］ + b［n-2］） * pow（2，2*n-4）。這種

比較只須根據(jù)B［m-1］、B［m-2］、。..、B［2*n-4］便可做出判斷，其余低位不做比較。

若 M［1］ 》= （pow（2，2）*b［n-1］ + b［n-2］） * pow（2，2*n-4）， 則假設(shè)有效，b［n-2］ =

1；

余數(shù) M［2］ = M［1］ - pow（pow（2，n-1）*b［n-1］ + pow（2，n-2）*b［n-2］， 2） = M［1］ -

（pow（2，2）+1）*pow（2，2*n-4）；

若 M［1］ 《 （pow（2，2）*b［n-1］ + b［n-2］） * pow（2，2*n-4）， 則假設(shè)無(wú)效，b［n-2］ =

0；余數(shù) M［2］ = M［1］。

（3） 同理，可以從高位到低位逐位求出M的平方根N的各位。

使用這種算法計(jì)算32位數(shù)的平方根時(shí)最多只須比較16次，而且每次比較時(shí)不必把M的各位逐

一比較，尤其是開(kāi)始時(shí)比較的位數(shù)很少，所以消耗的時(shí)間遠(yuǎn)低于牛頓迭代法。

2. 流程圖

（制作中，稍候再上）

3. 實(shí)現(xiàn)代碼

這里給出實(shí)現(xiàn)32位無(wú)符號(hào)整數(shù)開(kāi)方得到16位無(wú)符號(hào)整數(shù)的C語(yǔ)言代碼。

-------------------------------------------------------------------------------

-

/****************************************/

/*Function： 開(kāi)根號(hào)處理 */

/*入口參數(shù)：被開(kāi)方數(shù)，長(zhǎng)整型 */

/*出口參數(shù)：開(kāi)方結(jié)果，整型 */

/****************************************/

unsigned int sqrt_16（unsigned long M）

{

unsigned int N， i;

unsigned long tmp， ttp; // 結(jié)果、循環(huán)計(jì)數(shù)

if （M == 0） // 被開(kāi)方數(shù)，開(kāi)方結(jié)果也為0

return 0;

N = 0;

tmp = （M 》》 30）; // 獲取最高位：B［m-1］

M 《《= 2;

if （tmp 》 1） // 最高位為1

{

N ++; // 結(jié)果當(dāng)前位為1，否則為默認(rèn)的0

tmp -= N;

}

for （i=15; i》0; i--） // 求剩余的15位

{

N 《《= 1; // 左移一位

tmp 《《= 2;

tmp += （M 》》 30）; // 假設(shè)

ttp = N;

ttp = （ttp《《1）+1;

M 《《= 2;

if （tmp 》= ttp） // 假設(shè)成立

{

tmp -= ttp;

N ++;

}

}

return N;

}
責(zé)任編輯 LK