javascript - 用小数编写你自己的指数幂函数

Question

因此，我想使用某种算法在代码中编写一个函数来计算任何数字的任何幂，包括小数。我使用 JavaScript，它已经有一个内置的 pow 函数:

Math.pow(2, 0.413) // 2^0.413 = 1.331451613236371, took under 1 second.

现在我想这样写自己的:

function pow(x, y) {
    // Algorithm
}

这是一个计算任意数 (x^0.5) 的平方根的函数，并且仅循环 10 次就非常准确:

function sqrt(x, p) { // p = precision (accuracy)
    var a = 1;
    var b = x;

    while (p--) {
        a = (a + b) / 2
        b = x / a
    }

    return a
}

是否有任何简单的公式可以计算任何指数？

没有简单的，还有难的吗？

如果解决方案很慢，JavaScript 的 pow 怎么估计不到一秒？

Answer 1

这是一个很好的正整数幂算法，它首先处理一些简单的情况，然后使用循环测试指数的二进制位。例如查找 3^11 11在二进制中是1011所以循环中的阶段是

• 位掩码 = 1011，evenPower = 3，结果 = 3
• bitMask = 101, evenPower = 3*3 = 9, 结果 = 3*9 = 27
• bitMask = 10, evenPower = 9*9 = 81, 结果 = 27
• bitMask = 1, evenPower = 81*81 = 6561, 结果 = 27*6561 = 177147

这是每个循环的 evenPower 平方，如果底部位为 1，则结果乘以 evenPower。代码已从 Patricia Shanahan 的方法中提取 http://mindprod.com/jgloss/power.html它又起源于 Kunth，可以追溯到公元前 200 年的印度。

/**
 * A fast routine for computing integer powers.
 * Code adapted from {@link <a href="http://mindprod.com/jgloss/power.html">efficient power</a>} by Patricia Shanahan pats@acm.org
 * Almost identical to the method Knuth gives on page 462 of The Art of Computer Programming Volume 2 Seminumerical Algorithms.
 * @param l number to be taken to a power.
 * @param n power to take x to. 0 <= n <= Integer.MAX_VALUE
 * Negative numbers will be treated as unsigned positives.
 * @return x to the power n
 * 
 */
public static final double power(double l,int n)
{
    assert n>=0;

    double x=l;
    switch(n){
    case 0: x = 1.0; break;
    case 1: break;
    case 2: x *= x; break;
    case 3: x *= x*x; break;
    case 4: x *= x; x *= x; break;
    case 5: { double y = x*x; x *= y*y; } break;
    case 6: { double y = x*x; x = y*y*y; } break;
    case 7: { double y = x*x; x *= y*y*y; } break;
    case 8: x *= x; x *= x; x *= x; break;
    default:
    {
        int bitMask = n;
        double evenPower = x;
        double result;
        if ( (bitMask & 1) != 0 )
            result = x;
        else
            result = 1;
        bitMask >>>= 1;
        while ( bitMask != 0 ) {
            evenPower *= evenPower;
            if ( (bitMask & 1) != 0 )
                result *= evenPower;
            bitMask >>>= 1;
        } // end while
        x = result;
    }
    }
    return x;
}

对于实指数，您基本上需要找到 exp 和 log 的方法。您可以使用最简单的泰勒级数，但还有更好的方法。我们有

exp(x) = 1 + x + x^2/2 + x^3/6 + x^4/24 + x^5/120 + x^6/6! + ...

ln(1+x) = x - x^2 /2 + x^3 /3 - x^4 / 4 + x^5 / 5 - x^6/6 + ... |x|<1

要找到 x^y 笔记 ln(x^y) = y*ln(x) .现在我们需要在正确的范围内获得参数，以便我们可以使用我们的幂级数。令 x = m * 2^ex，尾数和指数选择为 1/sqrt(2)<= m < sqrt(2) 和 ln(m*2^ex) = ln(m) + ex*ln(2) .设 h = m-1 并求 ln(1+h)。

使用 java 和 float ，因为有一种简单的方法可以找到 IEEE 表示的内部结构(我使用了 float ，因为需要处理的位数较少)

int b = Float.floatToIntBits(x);
int sign = (b & 0x80000000) == 0 ? 1 : -1;
int mattissa = b & 0x007fffff;
int ex = ((b & 0x7f800000) >> 23 ) - 127;

在 javascript 中这对我们来说可能是最简单的 Number.toExponential并解析结果。

接下来构造一个在期望范围内的数字z 1/sqrt(2) < z < sqrt(2)

int bits = mattissa | 0x3f800000;
float z = Float.intBitsToFloat(bits);
if(z>root2) { 
    z = z/2;
    ++ex;
}

使用此函数使用泰勒级数求 1+x 的对数

static float ln1px(float x) {
    float x_2 = x*x; // powers of x
    float x_3 = x_2 * x;
    float x_4 = x_3 * x;
    float x_5 = x_4 * x;
    float x_6 = x_5 * x; 
    float res = x - x_2 /2 + x_3 /3 - x_4 / 4 + x_5 / 5 - x_6/6;
    return res;
}

这似乎对三位有效数字很好，当 x 接近 0 时通常会好得多。

然后可以找到我们编号x的log

float w = z - 1;
float ln_z = ln1px(w);
float ln_x = ln_z + ln2 * ex;
System.out.println("ln "+ln_x+"\t"+Math.log(x));

现在，如果我们编写 y = n + a，则为实际的幂，其中 n 是整数，a 是小数。所以 x^y=x^(n+a) = x^n * x^a .使用此答案中的第一个算法找到 x^n .写作 x=m*2^ex然后 ln((m*2^ex)^a) = y<em>ln(m) + y</em>ex*ln(2)和

x^a=exp(ln((m*2^ex)^a)) = exp(a * ln(m)) * exp(a * ln(2))^ex

这两个指数项的值相当小，因此泰勒级数应该不错。

我们需要一个函数来表示指数函数的泰勒级数

static float exp(float x) {
    float x_2 = x*x; // powers of x
    float x_3 = x_2 * x;
    float x_4 = x_3 * x;
    float x_5 = x_4 * x;
    float x_6 = x_5 * x; 
    float res = 1+ x + x_2 /2 + x_3 /6 + x_4 / 24 + x_5 / 120 + x_6/ 720;
    return res;
}

终于可以拼凑起来了

// Get integer and fractional parts of y
int n = (int) Math.floor(y);
float a = y-n;

float x_n = power(x,n);         // x^n
float a_ln_m = a * ln_z;        // ln(m^a) = a ln(m)
float a_ln_2 = a * ln2;         // ln(2^a) = a ln(2)
float m_a = exp(a_ln_m);        // m^a = exp(a ln(m))
float _2_a = exp(a_ln_2);       // 2^a = exp(a ln(2))
float _2_a_ex = power(_2_a,ex); // (2^ex)^a = 2^(a*ex) = (2^a)^ex 
float x_a = m_a * _2_a_ex;      // x^a = m^a * 2^(a*ex)

float x_y = x_n * x_a;          // x^y = x^n * x^a

System.out.println("x^y "+x_y+"\t"+Math.pow(x,y));

这应该是完整的程序，你需要一些智慧来应对负面争论等。

请注意，这并不是特别准确，因为我只使用了泰勒级数的几个项。其他SO问题有更详细的解答How can I write a power function myself?