C語言中文網 目錄

C語言除法算法和取模運算的實現(多種算法,多種思路)

對計算機來說,除法與求模是整數算術運算中最復雜的運算。相對其他運算(如加法與減法)來說,這兩種算法的執行速度非常慢。例如,ARM 硬件上不支持除法指令,編譯器調用 C 庫函數來實現除法運算。直接利用 C 庫函數中的標準整數除法程序要花費 20~100 個周期,消耗較多資源。

在非嵌入式領域,因為 CPU 運算速度快、存儲器容量大,所以執行除法運算和求模運算消耗的這些資源對計算機來說不算什么。但是在嵌入式領域,消耗大量資源帶來的影響不言而喻。因此,從理論上講,我們應該在程序表達式中盡量減少對除法運算與求模運算的使用,盡量使用其他方法來代替除法與求模運算。例如,對于下面的示例代碼:
if (x/y>z)
{
    // ...
}
我們可以將其修改成如下形式:
if (((y>0)&&(x>y*z))||((y<0)&&(x<y*z)))
{
    // ...
}
這樣就簡單地避免了一些除法運算。同時,也可以在表達式中通過合并除法的方式來減少除法運算,下面通過示例來講解。對于如下代碼:
double x=a/b/c;
double y=a/b+c/b;
根據數學結合原則,上面的代碼可以通過合并的方式減少代碼中的除法運算,修改后的代碼如下:
double x=a/(b*c);
double y=(a+c)/b;
同樣,對于求模運算,也可以采用相應的方法來代替,如下面的示例代碼:

a=a%8;

可以修改為:

a=a&7;

對于下面的表達式:

x=(x+y)%z;

可以通過如下方式來避免使用模操作符:
x+=y;
while(x>=z)
{
    x-=z;
}
通過上面的闡述,相信大家對如何減少使用除法與模運算有了初步了解。下面將詳細討論如何優化除法運算與求模運算。

用倒數相乘來實現除法運算

何為倒數相乘?其實很簡單,它的核心思想就是利用乘法來代替實現除法運算。例如,在 IA-32 處理器中,乘法指令的運算速度比除法指令要快 4~6 倍。因此,在某些情況下盡量使用乘法指令來代替除法指令。

那么,我們該如何利用乘法來代替實現除法運算呢?原理就是被除數乘以除數的倒數,用公式表現為:

x/y=x*(1/y)

例如,計算 10/5,可以根據公式 x/y=x*(1/y) 這樣來計算:

10/5=10*(1/5)=10*0.2=2

在實際應用中,一些編譯器也正是基于這個原理才得以將除法運算轉換為乘法運算的。現在我們來看一個除法運算示例:
#include <stdio.h>
int main(void)
{
    int x = 3/2;
    float y = 3.0/2.0;
    printf("3/2 = %d\r\n3.0/2.0 = %1.1f\n",x,y);
    return 0;
}
運算結果為:
3/2 = 1
3.0/2.0 = 1.5

通過該除法運算示例可以看出,很明顯沒能充分考慮到浮點類型。另外,在 C 語言中,一般情況下 1 除以任何數其結果皆為 0。那么怎樣才能解決這個問題呢?編譯器采用了一種稱為“定點運算”(fixed-point arithmetic)的方法。

那么何為定點運算,定點運算有什么特點呢?

前面已經闡述過,由于計算機表示實數時為了在固定位數內能表示盡量精確的實數值,分配給表示小數部分的位數并不是固定的,也就是說“小數點是浮動的”,因此計算機表示的實數數據類型也稱為浮點數。

相對于“小數點是浮動的”來講,定點運算根據字面意思來理解就是“小數點是固定的”。有了定點運算,表示小數時不再用階碼(exponent component,即小數點在浮點數據類型中的位置),而是要保持小數點的位置固定不變。這和硬件浮點數機制截然不同,硬件浮點數機制是由硬件負責向整數部分和小數部分分配可用的位數。有了這種機制,浮點數就可以表示很大范圍的數——從極小的數(在 0~1 的實數)到極大的數(在小數點前有數十個 0)。這種小數的定點表示法有很多優點,尤其能極大地提高效率。當然,作為代價,同樣也必須承受隨之而來的精度上的損失。

對于定點數表示法(fixed-point),相信大家并不陌生。所謂定點格式,即約定機器中所有數據的小數點位置是固定不變的。在計算機中通常采用兩種簡單的約定:將小數點的位置固定在數據的最高位之前(即定點小數),或者固定在最低位之后(即定點整數)。

其中,定點小數是純小數,約定的小數點位置在符號位之后、有效數值部分的最高位之前。若數據 x 的形式為 x=x0x1x2…xn(其中 x0 為符號位,x1,…,xn 是數值的有效部分,也稱為尾數,x1 為最高有效位),則在計算機中的表示形式為:


一般說來,如果最末位 xn=1,前面各位都為 0,則數的絕對值最小,即 |x|min=2-n;如果各位均為 1,則數的絕對值最大,即 |x|max=1-2-n。因此定點小數的表示范圍是:


定點整數是純整數,約定的小數點位置在有效數值部分最低位之后。若數據 x 的形式為 x=x0x1x2…xn(其中 x0 為符號位,x1,…,xn 是尾數,xn 為最低有效位),則在計算機中的表示形式為:



由此可知,定點整數的表示范圍是:


當數據小于定點數能表示的最小值時,計算機將它作 0 處理,稱為下溢;當數據大于定點數能表示的最大值時,計算機將無法表示,稱為上溢,上溢和下溢統稱為溢出

當計算機采用定點數表示時,對于既有整數又有小數的原始數據,需要設定一個比例因子,數據按該比例縮小成定點小數或擴大成定點整數再參加運算。在運算結果中,根據比例因子,將數據還原成實際數值。若比例因子選擇不當,往往會使運算結果產生溢出或降低數據的有效精度。

使用牛頓迭代法求除數的倒數

在上一小節,我們闡述了如何使用倒數相乘(x/y=x*(1/y))的方法來實現除法運算。然而,對于如何能夠快速有效地取倒數,牛頓迭代法(Newton’s method)是最佳方案。

對于牛頓迭代法,相信學過高等數學的讀者并不陌生,它又稱為牛頓-拉夫遜方法(Newton-Raphson method),是牛頓在 17 世紀提出的一種在實數域和復數域上近似求解方程的方法,它將非線性方程線性化,從而得到迭代序列的一種方法。

對于方程 f(x)=0,設 x0 為它的一個近似根,則函數 f(x) 在 x0 附近截斷高次項可用一階泰勒多項式展開為如下形式:


這樣,由式(1)我們可以將 f(x)=0 轉化為如下形式:


 
在這里,我們設 f′(x)≠0,則有:


 
取 x 作為原方程新的近似根 x1,再代入方程,如此反復,于是就產生了迭代公式:


 
有了迭代公式(4)之后,現在我們繼續來看如何用牛頓迭代公式來求倒數,即求除數 a 的倒數 1/a。

這里我們設:


 
式中 x 為 a 的倒數,方程 f(x)=0 為一非線性方程。現在把 f(x)=0 代入牛頓迭代序列式(4)中,就可以得出求倒數的公式,如下所示:


 
在式(5)中,xn 為第 n 次迭代的近似根。

如式(5)所示,用牛頓迭代法求倒數,每次迭代需要一次減法與兩次乘法,所用的迭代次數決定最終的計算速度和精度。迭代次數越多,則精度越高。但迭代次數越多,速度也越慢,因此實際運用時應綜合考慮速度和精度兩方面的因素,選擇合適的迭代次數。

其實,牛頓迭代法在程序中應用得非常廣泛,如最常用的開方、開方求倒數等。在 QuakeⅢ 源碼中,在 game/code/q_math.c 文件中就有一個函數 Q_rsqrt,它的作用是將一個數開平方后取倒,其運行效率也非常高。其函數實現為:
float Q_rsqrt(float number)
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;
    x2 = number * 0.5F;
    y  = number;
    i  = * (long * ) &y;
    i  = 0x5f3759df - (i >> 1);
    y  = * ( float * ) &i;
    // 第一次迭代
    y  = y * ( threehalfs - ( x2 * y * y ));
    // 第二迭代
    // y  = y * ( threehalfs - ( x2 * y * y ) );
    return y;
}
從代碼中可以看出,程序首先猜測出一個接近 1.0/sqrt(number) 的近似值,然后兩次使用牛頓迭代法進行迭代(實際只需要使用一次)。這里需要特別注意的是 0x5f3759df 這個值,因為通過執行語句“0x5f3759df-(i>>1)”,得出的值出人意料地接近 1/sqrt(number) 的值,因此,我們只需要一次迭代就可以求得近似解,或許這就是數學的神奇。

用減法運算來實現整數除法運算

我們知道,減法運算比除法運算要快得多。因此,對整數除法運算來說,如果知道被除數是除數很小的倍數,那么可以使用減法運算來代替除法運算。例如,對于下面的示例代碼:
unsigned int x=300;
unsigned int y=100;
unsigned int z=x/y;
我們可以將“z=x/y”表達式修改成如下形式:
unsigned int x=300;
unsigned int y=100;
unsigned int z=0;
while (x>=y)
{
    x-=y;
    ++z;
}
這里使用減法來代替除法運算,雖然代碼看起來不是很直觀,但是在運行效率上確實要快許多。當然,具體效率也要取決于被除數與除數的倍數。如果倍數比較大,那么相應的循環次數就會增多,采取這種方法就得不償失了。

用移位運算實現乘除法運算

用移位運算來實現乘除法運算的方法,相信大家并不陌生,實際上有很多 C 編譯器都能夠自動地做好這個優化。通常,如果需要乘以或除以 2n,都可以用移位的方法代替。例如:
a=a*2;
b=b/2;
可以修改為如下形式:
a=a<<1;
b=b>>1;
其中,除以 2 等價于右移 1 位,乘以 2 等價于左移 1 位。同理,除以 4 等價于右移 2 位,乘以 4 等價于左移 2 位;除以 8 等價于右移 3 位,乘以 8 等價于左移 3 位,以此類推。

其實,利用上面的原理,只要是乘以或除以一個整數,均可以用移位運算的方法來得到結果,例如:
a=a*5;
可以將其分解為 a*(4+1),即 a*4+a*1。由此,我們就可以很簡單地得到下面的程序表達式:

a=(a<<2)+a

盡量將浮點除法轉化為相應的整數除法運算

有時候,如果不能夠在代碼中避免除法運算,那么盡量使除數和被除數是無符號類型的整數。實際上,有符號的除法運算執行起來比無符號的除法運算更加慢,因為有符號的除法運算要先取得除數和被除數的絕對值,再調用無符號除法運算,最后再確定結果的符號。

同時,對于浮點除法運算,可以先將浮點除法運算轉化為相應的整數除法運算,最后對結果進行相應處理。例如,可以將浮點除法運算的分子和分母同時放大相同的倍數,就可以將浮點除法運算轉換成相同功能的整數除法運算。

精美而實用的網站,提供C語言C++STLLinuxShellJavaGo語言等教程,以及socketGCCviSwing設計模式JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo