'Grokkable' 算法来理解指数是浮点的取幂

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)where 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;
    }
}