实现精确的cbrt（）函数而无需额外的精度 [英] Implementing an accurate cbrt() function without extra precision

问题描述

在JavaScript中，没有可用的本地 cbrt 方法。从理论上讲，您可以使用如下方法：

In JavaScript, there is no native cbrt method available. In theory, you could use a method like this:

function cbrt(x) {
  return Math.pow(x, 1 / 3);
}

但是，这失败了，因为数学中的恒等不一定适用于浮点数算术。例如，不能使用二进制浮点格式精确地表示1/3。

However, this fails because identities in mathematics don't necessarily apply to floating point arithmetic. For example, 1/3 cannot be accurately represented using a binary floating point format.

以下是失败的示例：

cbrt(Math.pow(4, 3)); // 3.9999999999999996

随着数字变大，情况变得更糟：

This gets worse as the number gets larger:

cbrt(Math.pow(165140, 3)); // 165139.99999999988

是否有任何算法能够将立方根值计算到几个ULP之内（如果可能的话，最好是1个ULP）？

Is there any algorithm which is able to calculate a cube root value to within a few ULP (preferably 1 ULP if possible)?

此问题类似于计算正确取整/几乎正确取整的浮点立方根，但请记住，JavaScript没有更高的-精度数字类型（JavaScript中只有一种数字类型），也没有内置的 cbrt 函数开始。

This question is similar to Computing a correctly rounded / an almost correctly rounded floating-point cubic root, but keep in mind that JavaScript doesn't have any higher-precision number types to work with (there is only one number type in JavaScript), nor is there a built-in cbrt function to begin with.

推荐答案

您可以移植现有的实现，例如用C 编写的Java代码。该代码有两种变体，一种是更精确的迭代性，另一种是非交互性的。

You can port an existing implementation, like this one in C, to Javascript. That code has two variants, an iterative one that is more accurate and a non-interative one.

Ken Turkowski的实现依赖于将radicand分解为尾数和指数，然后重新组合，但这仅用于使它达到1/8和1之间的范围。对于第一个近似值，可以通过在-2到0之间执行一个二进制指数来实现。在Javascript中，您可以通过重复除以8或乘以8来做到这一点，这不会影响准确性，因为它只是一个指数移位。

Ken Turkowski's implementation relies on splitting up the radicand into mantissa and exponent and then reassembling it, but this is only used to bring it into the range between 1/8 and 1 for the first approximation by enforcing a binary exponent between -2 and 0. In Javascript, you can do this by repeatedly dividing or multiplying by 8, which should not affect accuracy, because it is just an exponent shift.

如上所示，该实现对于单精度浮点数是准确的，但是Javascript使用双精度数。再添加两个牛顿迭代可产生良好的准确性。

The implementation as shown in the paper is accurate for single-precision floating-point numbers, but Javascript uses double-precision numbers. Adding two more Newton iterations yields good accuracy.

这是上述 cbrt 算法的Javascript端口：

Here's the Javascript port of the described cbrt algorithm:

Math.cbrt = function(x) 
{    
    if (x == 0) return 0;
    if (x < 0) return -Math.cbrt(-x);

    var r = x;
    var ex = 0;

    while (r < 0.125) { r *= 8; ex--; }
    while (r > 1.0) { r *= 0.125; ex++; }

    r = (-0.46946116 * r + 1.072302) * r + 0.3812513;

    while (ex < 0) { r *= 0.5; ex++; }
    while (ex > 0) { r *= 2; ex--; }

    r = (2.0 / 3.0) * r + (1.0 / 3.0) * x / (r * r);
    r = (2.0 / 3.0) * r + (1.0 / 3.0) * x / (r * r);
    r = (2.0 / 3.0) * r + (1.0 / 3.0) * x / (r * r);
    r = (2.0 / 3.0) * r + (1.0 / 3.0) * x / (r * r);

    return r;
}

我还没有对其进行广泛的测试，尤其是在定义不明确的极端情况下，但是用 pow 进行的测试和比较看起来还不错。性能可能不是很好。

I haven't tested it extensively, especially not in badly defined corner cases, but the tests and comparisons with pow I have done look okay. Performance is probably not so great.

这篇关于实现精确的cbrt（）函数而无需额外的精度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！