This question already has answers here:
The most efficient way to implement an integer based power function pow(int, int)

(19个回答)


已关闭6年。




我已经读过cmath通过执行pow(a,b)来计算exp(b*log(a))。当b是整数时,不应使用此方法,因为它会大大降低计算速度。什么时候有替代品
  • 使用相同的常量pow()
  • 计算大量连续的a s
  • 事先知道b肯定是是整数吗?

  • 我正在寻找在这些特定情况下有效的快速替代方案。

    最佳答案

    这些年来,我收集了许多更快的替代方法,这些替代方法通常依赖于该函数的recursive实现,并在保证有保证的情况下通过移位来处理乘法。以下提供了针对integerfloatdouble量身定制的功能。它们带有普通的disclaimer:,而速度更快,并不是所有可能的测试都已运行,并且用户应在调用并返回之前确认输入是否正确……等等,等等,等等。但是,它们非常有用:

    我相信适当的归因于jit_a,如蓝色月亮所指出的。我早就失去了链接。看起来像他们。 (减去一两次调整)。

    /* 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;
        }
    }
    

    关于c++ - path()在cmath中的实现和有效的替换,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/26860574/

    10-11 22:07
    查看更多