当基数为 float/double 时，二进制求幂无法正常工作

Question

我从 this 站点学习了如何在 C++ 中实现二进制求幂。我使用了递归算法：

long long binpow(long long a, long long b) {
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2);
    if (b % 2)
        return res * res * a;
    else
        return res * res;
}

在我的情况下，我需要 a 是一个双精度值。我这样做是为了做到这一点：

double binpow(double a, long long b) {
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2);
    if (b % 2)
        return res * res * a;
    else
        return res * res;
}

我不需要 b 是一个双精度，而且我知道如果 b 是一个双精度，我将需要使用不同的方法来获得实际值。

当我运行代码为：binpow(3.1, 3) 时，正确答案是 29.79，但 binpow 算法给了我 27.9。我也试过binpow(9.23, 3)，它给了我747.63，而真正的答案是786.33。

此外，当我切换到天真的方法时：

double naive(double a, long long b) {
    
    double final = 1;
    
    for (;b > 0; b--) {
        final*=a;
    }
    
    return final;
}

我得到 786.33

的正确答案

这是什么问题，有什么办法可以解决吗？

Answer 1

您在这里将 binpow 的结果转换为 long long：

long long res = binpow(a, b / 2);

这会改变结果。

相反，您需要这样做：

double res = binpow(a, b / 2);

甚至更好

auto res = binpow(a, b / 2);  // so res has the same type that binpow returns

这解决了问题。这是 demo.

当基数为 float/double 时，二进制求幂无法正常工作

Binary Exponentiation is not working properly when the base is a float/double

c++

exponentiation