單片機(jī)C語(yǔ)言求平方根

1、在單片機(jī)中要開(kāi)平方.可以用到下面算法:算法1:本算法只采用移位、加減法、判斷和循環(huán)實(shí)現(xiàn),因?yàn)樗恍枰↑c(diǎn)運(yùn)算,也不需要乘除運(yùn)算,因此可以很方便地運(yùn)用到各種芯片上去。我們先來(lái)看看10進(jìn)制下是如何手工計(jì)算開(kāi)方的。先看下面兩個(gè)算式,x = 10*p + q (1公式(1左右平方之后得:x2 = 100*p2 + 20pq + q2 (2現(xiàn)在假設(shè)我們知道x2和p,希望求出q來(lái),求出了q也就求出了x2的開(kāi)方x了。我們把公式(2改寫(xiě)為如下格式:q = (x2 - 100*p2/(20*p+q (3這個(gè)算式左右都有q,因此無(wú)法直接計(jì)算出q來(lái),因此手工的開(kāi)方算法和手工除法算法一樣有一步需要猜值。我們來(lái)一個(gè)手工

2、計(jì)算的例子:計(jì)算1234567890的開(kāi)方首先我們把這個(gè)數(shù)兩位兩位一組分開(kāi),計(jì)算出最高位為3。也就是(3中的p,最下面一行的334為余數(shù),也就是公式(3中的(x2 - 100*p2近似值3 - | 12 34 56 78 90 9 - | 3 34下面我們要找到一個(gè)0-9的數(shù)q使它最接近滿(mǎn)足公式(3。我們先把p乘以20寫(xiě)在334左邊:3 q - | 12 34 56 78 90 9 - 6q| 3 34我們看到q為5時(shí)(60+q*q的值最接近334,而且不超過(guò)334。于是我們得到:3 5 - | 12 34 56 78 90 9 - 65| 3 34 | 325 - 9 56接下來(lái)就是重復(fù)上面

3、的步驟了,這里就不再啰嗦了。這個(gè)手工算法其實(shí)和10進(jìn)制關(guān)系不大,因此我們可以很容易的把它改為二進(jìn)制,改為二進(jìn)制之后,公式(3就變成了:q = (x2 - 4*p2/(4*p+q (4我們來(lái)看一個(gè)例子,計(jì)算100(二進(jìn)制1100100的開(kāi)方:1 0 1 0 - | 1 10 01 00 1 - 100| 0 10 | 000 - | 10 011001| 10 01 - 0 00這里每一步不再是把p乘以20了,而是把p乘以4,也就是把p右移兩位,而由于q的值只能為0或者1,所以我們只需要判斷余數(shù)(x2 - 4*p2和(4*p+1的大小關(guān)系,如果余數(shù)大于等于(4*p+q那么該上一個(gè)1,否則該上一個(gè)

4、0。下面給出完成的C語(yǔ)言程序,其中root表示p,rem表示每步計(jì)算之后的余數(shù),divisor表示(4*p+1,通過(guò)a>>30取a的最高2位,通過(guò)a<<=2將計(jì)算后的最高2位剔除。其中root的兩次<<1相當(dāng)于4*p。程序完全是按照手工計(jì)算改寫(xiě)的,應(yīng)該不難理解。unsigned short sqrt(unsigned long aunsigned long rem = 0;unsigned long root = 0;unsigned long divisor = 0;for(int i=0; i<16; i+root <<= 1;rem

5、= (rem << 2 + (a >> 30;a <<= 2;divisor = (root<<1 + 1;if(divisor <= remrem -= divisor;root+;return (unsigned short(root;算法2 :單片機(jī)開(kāi)平方的快速算法因?yàn)楣ぷ鞯男枰?要在單片機(jī)上實(shí)現(xiàn)開(kāi)根號(hào)的操作。目前開(kāi)平方的方法大部分是用牛頓迭代法。我在查了一些資料以后找到了一個(gè)比牛頓迭代法更加快速的方法。不敢獨(dú)享,介紹給大家,希望會(huì)有些幫助。1.原理因?yàn)榕虐娴脑?用pow(X,Y表示X的Y次冪,用B0,B1,.,Bm-1表示一個(gè)序列

6、,其中x為下標(biāo)。假設(shè):Bx,bx都是二進(jìn)制序列,取值0或1。M = Bm-1*pow(2,m-1 + Bm-2*pow(2,m-2 + . + B1*pow(2,1 + B0*pow(2,0N = bn-1*pow(2,n-1 + bn-2*pow(2,n-2 + . + b1*pow(2,1 + n0*pow(2,0pow(N,2 = M(1 N的最高位bn-1可以根據(jù)M的最高位Bm-1直接求得。設(shè)m 已知,因?yàn)閜ow(2, m-1 <= M <= pow(2, m,所以pow(2, (m-1/2 <= N <=pow(2, m/2如果m 是奇數(shù),設(shè)m=2*k+1,那

7、么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所以bn-1完全由Bm-1決定。余數(shù)M1 = M - bn-1*pow(2, 2*n-2(2 N的次高位bn-2可以采用試探法來(lái)確定。因?yàn)閎n-1=1,假設(shè)bn-2=1,則pow(bn-1*pow(2,n-1 + bn-1*pow(2,n-2,2 = bn-1*pow(2,2*n-2 + (bn-

8、1*pow(2,2*n-2 + bn-2*pow(2,2*n-4,然后比較余數(shù)M1是否大于等于(pow(2,2*bn-1 + bn-2 * pow(2,2*n-4。這種比較只須根據(jù)Bm-1、Bm-2、.、B2*n-4便可做出判斷,其余低位不做比較。若M1 >= (pow(2,2*bn-1 + bn-2 * pow(2,2*n-4, 則假設(shè)有效,bn-2 =1;余數(shù)M2 = M1 - pow(pow(2,n-1*bn-1 + pow(2,n-2*bn-2, 2 = M1 -(pow(2,2+1*pow(2,2*n-4;若M1 < (pow(2,2*bn-1 + bn-2 * pow(

9、2,2*n-4, 則假設(shè)無(wú)效,bn-2 =0;余數(shù)M2 = M1。(3 同理,可以從高位到低位逐位求出M的平方根N的各位。使用這種算法計(jì)算32位數(shù)的平方根時(shí)最多只須比較16次,而且每次比較時(shí)不必把M的各位逐一比較,尤其是開(kāi)始時(shí)比較的位數(shù)很少,所以消耗的時(shí)間遠(yuǎn)低于牛頓迭代法。2. 實(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 Munsigned int N, i;unsigned long tmp, ttp; / 結(jié)果、循環(huán)計(jì)數(shù)if (M = 0 / 被開(kāi)方數(shù),開(kāi)方結(jié)果也為0return 0;N = 0;tmp = (M >> 30; / 獲取最高位:Bm-1M <<= 2;if (tmp > 1 / 最高位為1N +; / 結(jié)果當(dāng)前位為1,否則為默認(rèn)的0 tmp -= N;for (i=15; i>0; i- / 求剩余的15位N &l