c++ - cmath 中的 pow() 实现和高效替换

Question

<分区>

Answer 1

多年来我收集了许多更快的替代方案，它们通常依赖于函数的递归实现，并在必要时通过位移来处理乘法。以下提供为 integer、float 和 double 定制的函数。它们带有正常的 disclaimer: 虽然速度更快，但并非所有可能的测试都已运行，用户应在调用之前和返回时验证输入是否正常......等等，等等，等等......但是，他们是非常有用:

我相信适当的归因于 Geeks for Geeks Pow(x,n)正如蓝月亮所指出的那样。我早就失去了链接.. 看起来像他们。 (减去一两次调整)。

/* Function to calculate x raised to the power y

    Time Complexity: O(n)
    Space Complexity: O(1)
    Algorithmic Paradigm: Divide and conquer.
*/
int power1 (int x, unsigned int y)
{
    if (y == 0)
        return 1;
    else if ((y % 2) == 0)
        return power1 (x, y / 2) * power1 (x, y / 2);
    else
        return x * power1 (x, y / 2) * power1 (x, y / 2);

}

/* Function to calculate x raised to the power y in O(logn)
    Time Complexity of optimized solution: O(logn)
*/
int power2 (int x, unsigned int y)
{
    int temp;
    if (y == 0)
        return 1;

    temp = power2 (x, y / 2);
    if ((y % 2) == 0)
        return temp * temp;
    else
        return x * temp * temp;
}

/* Extended version of power function that can work
for float x and negative y
*/
float powerf (float x, int y)
{
    float temp;
    if (y == 0)
    return 1;
    temp = powerf (x, y / 2);
    if ((y % 2) == 0) {
        return temp * temp;
    } else {
        if (y > 0)
            return x * temp * temp;
        else
            return (temp * temp) / x;
    }
}

/* Extended version of power function that can work
for double x and negative y
*/
double powerd (double x, int y)
{
    double temp;
    if (y == 0)
    return 1;
    temp = powerd (x, y / 2);
    if ((y % 2) == 0) {
        return temp * temp;
    } else {
        if (y > 0)
            return x * temp * temp;
        else
            return (temp * temp) / x;
    }
}