c# - “Grokkable”算法，用于理解指数为 float 的求幂

Question

首先澄清一下:

• 2^3 = 8。这相当于 2*2*2。简单。
• 2^4 = 16。这相当于 2*2*2*2。也很简单。
• 2^3.5 = 11.313708...呃，这不是那么容易理解的。

我想要的是一个简单的算法，它最清楚地显示了 2^3.5 = 11.313708 的原理。除了基本的加法、减法、乘法或除法运算符外，它最好不要使用任何函数。

代码当然不一定要快，也不一定要短(尽管这会有所帮助)。别担心，它可以近似于给定的用户指定精度(这也应该是算法的一部分)。我希望会出现二进制印章/搜索类型的东西，因为这很容易理解。

到目前为止，我找到了 this ，但最佳答案在概念层面上远非简单易懂。

答案越多越好，因此我可以尝试理解解决问题的不同方法。

我对答案的语言偏好是 C#/C/C++/Java，或者我所关心的伪代码。

Answer 1

好吧，让我们只使用二进制搜索、加法和乘法来实现 pow(x, y)。

驾驶 y低于 1

首先，解决这个问题:

pow(x, y) == pow(x*x, y/2)
pow(x, y) == 1/pow(x, -y)

这对于处理负指数和驱动很重要 y下面1 ，事情开始变得有趣。这将问题简化为查找 pow(x, y)其中 0<y<1 .

实现sqrt

在这个答案中，我假设您知道如何执行 sqrt .我知道sqrt(x) = x^(1/2) , 但很容易实现它，只需使用二进制搜索来查找 y = sqrt(x)使用 y*y=x搜索功能，例如:

#define EPS 1e-8

double sqrt2(double x) {
    double a = 0, b = x>1 ? x : 1; 
    while(abs(a-b) > EPS) {
        double y = (a+b)/2;
        if (y*y > x) b = y; else a = y;
    }
    return a;
}

寻找答案

基本原理是每个小于 1 的数字都可以近似为分数之和 1/2^x :

0.875 = 1/2 + 1/4 + 1/8
0.333333... = 1/4 + 1/16 + 1/64 + 1/256 + ...

如果你找到这些分数，你实际上会发现:

x^0.875 = x^(1/2+1/4+1/8) = x^(1/2) * x^(1/4) * x^(1/8)

这最终导致

sqrt(x) * sqrt(sqrt(x)) * sqrt(sqrt(sqrt(x)))

因此，实现(在 C++ 中)

#define EPS 1e-8

double pow2(double x, double y){
    if (x < 0 and abs(round(y)-y) < EPS) {
        return pow2(-x, y) * ((int)round(y)%2==1 ? -1 : 1);
    } else if (y < 0) {
        return 1/pow2(x, -y);
    } else if(y > 1) {
        return pow2(x * x, y / 2);
    } else {
        double fraction = 1;
        double result = 1;

        while(y > EPS) {
            if (y >= fraction) {
                y -= fraction;
                result *= x;
            }

            fraction /= 2;
            x = sqrt2(x);
        }
        return result;
    }
}