C++之竹

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

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

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

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

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

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

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

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

由此，我們就可以事先依次計算出 val, val², val⁴, ... , val³⁰ 預存?zhèn)溆茫缓笤俑鶕?jù) val 相應 bit 上是 1 還是 0，來選取相應的預存數(shù)據(jù)進行相乘，從而得到最終的結(jié)果。當然，合理設(shè)計邏輯，還可以減少所需的預存數(shù)據(jù)。下面是我的Pow 代碼，歡迎點評。

#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;
}

 
【補充】：

1. 在指數(shù)中，0的負數(shù)次方和0的0次方，都是沒有意義的，所以對“if (IsZero(val))”分支內(nèi)的處理如果能加上一些異常的輸出就更好了，如：

   在Widows下，可通過 SetLastError(...) 來設(shè)置錯誤碼。

2. Pow中的 “double tempVal[INTBITS_WITHOUT_SIGN];” 一句，改寫為

   double * pTempVal = new double[sizeof(int) * 8 - 1];

(當然，后面代碼中的tempVal 也都要改為相應的 pTempVal，同時須記得在return 前把delete [] pTempVal)

就可以使代碼也能夠適應于64位系統(tǒng)的處理。對于無符號整數(shù)的為指數(shù)的情況，則輔助值空間應為“sizeof(unsigned int) * 8”，同時，無需再考慮負指數(shù)的情況。

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

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