C++之竹

關于數值的整數次方的計算

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

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

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

通過所學的指數函數的知識，我們知道指數函數有著這樣的性質：

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

另外，對于整數，有如下性質：

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

由此，我們就可以事先依次計算出 val, val², val⁴, ... , val³⁰ 預存備用，然后再根據 val 相應 bit 上是 1 還是 0，來選取相應的預存數據進行相乘，從而得到最終的結果。當然，合理設計邏輯，還可以減少所需的預存數據。下面是我的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. 在指數中，0的負數次方和0的0次方，都是沒有意義的，所以對“if (IsZero(val))”分支內的處理如果能加上一些異常的輸出就更好了，如：

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

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

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

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

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

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

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