C++之竹

關(guān)于數(shù)值的整數(shù)次方的計(jì)算

在計(jì)算一個(gè)浮點(diǎn)數(shù)（雙精度或單精度）的整數(shù)次方時(shí)，一般的，我們會(huì)直接使用 C++ 本身所提供的 pow 函數(shù)，事實(shí)上也推薦直接使用 pow 函數(shù)（為了稱呼簡(jiǎn)便，后面稱該 pow 函數(shù)為系統(tǒng) pow 函數(shù)）。

但是，當(dāng)我們準(zhǔn)備寫一個(gè)自己的 pow 時(shí)，我們又會(huì)怎么寫呢？一般的，我們會(huì)寫上一個(gè) for 循環(huán)來(lái)循環(huán)冪的指數(shù)次，而且每次循環(huán)都會(huì)去執(zhí)行一次浮點(diǎn)數(shù)的乘法操作。但是，當(dāng)我們拿這個(gè) pow 函數(shù)來(lái)跟系統(tǒng) pow 函數(shù)作一運(yùn)行比較時(shí)，就會(huì)發(fā)現(xiàn)，我們的 pow 實(shí)在是太低效了。那么怎么樣才能使我們自己寫的 pow 也能有系統(tǒng)函數(shù)那樣的時(shí)間效率呢？

仔細(xì)分析，我們用的那個(gè)求冪值的循環(huán)過(guò)程，就能發(fā)現(xiàn)，其實(shí)我們還是做了很多不必要的浮點(diǎn)數(shù)乘法炒作。整個(gè)計(jì)算過(guò)程太過(guò)按步就班了。譬如說(shuō)在計(jì)算 val（待傳入pow 函數(shù)求冪的浮點(diǎn)數(shù)，下同） 的4次方，我們總是先計(jì)算出3次方的值，然后再根據(jù)3次方的值和原始值來(lái)求4次方的值；然而，我們其實(shí)本可以在計(jì)算出2次方值后，平方2次方值來(lái)得到4次方的值的。接下來(lái)，就是探索算法，以減少浮點(diǎn)數(shù)乘法的事了。

通過(guò)所學(xué)的指數(shù)函數(shù)的知識(shí)，我們知道指數(shù)函數(shù)有著這樣的性質(zhì)：

• V^(a+b) = V^a * V^b
• V^a*b = (V^a)^{b             ；這里 * 為乘法運(yùn)算符}

另外，對(duì)于整數(shù)，有如下性質(zhì)：

1.  2ⁿ = (1 << n)         ;這里 << 是向左移位的操作符。
2. C++中的任何一個(gè)正整數(shù)（負(fù)整數(shù)同，但須處理好符合位）都可以表示為以下形式：
   n = 2^a1 + 2^a2 + ... + 2^ak
   (其中，a1, a2, ... , ak 為閉區(qū)間 [0, 30] 上的整數(shù)值，且互不相同。)

由此，我們就可以事先依次計(jì)算出 val, val², val⁴, ... , val³⁰ 預(yù)存?zhèn)溆?，然后再根?jù) val 相應(yīng) bit 上是 1 還是 0，來(lái)選取相應(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次方，都是沒(méi)有意義的，所以對(duì)“if (IsZero(val))”分支內(nèi)的處理如果能加上一些異常的輸出就更好了，如：

   在Widows下，可通過(guò) SetLastError(...) 來(lái)設(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ì)于無(wú)符號(hào)整數(shù)的為指數(shù)的情況，則輔助值空間應(yīng)為“sizeof(unsigned int) * 8”，同時(shí)，無(wú)需再考慮負(fù)指數(shù)的情況。

(這里，很感謝春秋十二月的補(bǔ)充。)
 

posted on 2012-03-17 04:01 青碧竹 閱讀(3020) 評(píng)論(4)  編輯 收藏 引用 所屬分類: 算法相關(guān)