在計(jì)算一個(gè)浮點(diǎn)數(shù)（雙精度或單精度）的整數(shù)次方時(shí)，一般的，我們會(huì)直接使用 C++ 本身所提供的 pow 函數(shù)，事實(shí)上也推薦直接使用 pow 函數(shù)（為了稱呼簡便，后面稱該 pow 函數(shù)為系統(tǒng) pow 函數(shù)）。
但是，當(dāng)我們準(zhǔn)備寫一個(gè)自己的 pow 時(shí)，我們又會(huì)怎么寫呢？一般的，我們會(huì)寫上一個(gè) for 循環(huán)來循環(huán)冪的指數(shù)次，而且每次循環(huán)都會(huì)去執(zhí)行一次浮點(diǎn)數(shù)的乘法操作。但是，當(dāng)我們拿這個(gè) pow 函數(shù)來跟系統(tǒng) pow 函數(shù)作一運(yùn)行比較時(shí)，就會(huì)發(fā)現(xiàn)，我們的 pow 實(shí)在是太低效了。那么怎么樣才能使我們自己寫的 pow 也能有系統(tǒng)函數(shù)那樣的時(shí)間效率呢？
仔細(xì)分析，我們用的那個(gè)求冪值的循環(huán)過程，就能發(fā)現(xiàn)，其實(shí)我們還是做了很多不必要的浮點(diǎn)數(shù)乘法炒作。整個(gè)計(jì)算過程太過按步就班了。譬如說在計(jì)算 val（待傳入pow 函數(shù)求冪的浮點(diǎn)數(shù)，下同） 的4次方，我們總是先計(jì)算出3次方的值，然后再根據(jù)3次方的值和原始值來求4次方的值；然而，我們其實(shí)本可以在計(jì)算出2次方值后，平方2次方值來得到4次方的值的。接下來，就是探索算法，以減少浮點(diǎn)數(shù)乘法的事了。
通過所學(xué)的指數(shù)函數(shù)的知識(shí)，我們知道指數(shù)函數(shù)有著這樣的性質(zhì)：
另外，對(duì)于整數(shù)，有如下性質(zhì)：
-
2n = (1 << n) ;這里 << 是向左移位的操作符。
-
C++中的任何一個(gè)正整數(shù)（負(fù)整數(shù)同，但須處理好符合位）都可以表示為以下形式：
n = 2a1 + 2a2 + ... + 2ak
(其中，a1, a2, ... , ak 為閉區(qū)間 [0, 30] 上的整數(shù)值，且互不相同。)
由此，我們就可以事先依次計(jì)算出 val, val2, val4, ... , val30 預(yù)存?zhèn)溆茫缓笤俑鶕?jù) val 相應(yīng) bit 上是 1 還是 0，來選取相應(yīng)的預(yù)存數(shù)據(jù)進(jìn)行相乘，從而得到最終的結(jié)果。當(dāng)然，合理設(shè)計(jì)邏輯，還可以減少所需的預(yù)存數(shù)據(jù)。下面是我的Pow 代碼，歡迎點(diǎn)評(píng)。
#define INTBITS_WITHOUT_SIGN 31 // the bit-size of type int with the sign bit being excluded.
bool IsZero(double val, double precision /**//*= DEFAULT_PRECISION*/)
{
if (precision >= 0) {
return (-precision <= val) && (val <= precision);
} else {
return (precision <= val) && (val <= -precision);
}
}
double Pow(double val, int exponent)
{
if (IsZero(val)) {
return 0.0;
}
if (0 == exponent) {
return 1.0;
}
bool bIsExponentMinus = false;
if (exponent < 0) {
exponent = -exponent;
bIsExponentMinus = true;
}
double tempVal[INTBITS_WITHOUT_SIGN];
memset(tempVal, 0, INTBITS_WITHOUT_SIGN);
tempVal[0] = val;
double result = 1.0;
int index = 0;
while (exponent != 0) {
if ((exponent & 1) != 0) {
result *= tempVal[index];
}
exponent >>= 1;
if (exponent != 0) {
tempVal[index + 1] = tempVal[index] * tempVal[index];
++index;
}
}
if (bIsExponentMinus) {
result = 1.0 / result;
}
return result;
}
【補(bǔ)充】：
1. 在指數(shù)中，0的負(fù)數(shù)次方和0的0次方，都是沒有意義的，所以對(duì)“if (IsZero(val))”分支內(nèi)的處理如果能加上一些異常的輸出就更好了，如：
在Widows下，可通過 SetLastError(...) 來設(shè)置錯(cuò)誤碼。
2. Pow中的 “double tempVal[INTBITS_WITHOUT_SIGN];” 一句，改寫為
double * pTempVal = new double[sizeof(int) * 8 - 1];
(當(dāng)然，后面代碼中的tempVal 也都要改為相應(yīng)的 pTempVal，同時(shí)須記得在return 前把delete [] pTempVal)
就可以使代碼也能夠適應(yīng)于64位系統(tǒng)的處理。對(duì)于無符號(hào)整數(shù)的為指數(shù)的情況，則輔助值空間應(yīng)為“sizeof(unsigned int) * 8”，同時(shí)，無需再考慮負(fù)指數(shù)的情況。
(這里，很感謝春秋十二月的補(bǔ)充。)