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 青碧竹 阅读(2948) 评论(4)  编辑 收藏 引用 所属分类: 算法相关