使用有限数学运算符查找多维数据集根

Question

我需要写一个函数来告诉我一个数字是否是一个完美的立方体。如果是，我希望按如下方式返回多维数据集根，否则为false：

cubeRoot(1)   // 1
cubeRoot(8)   // 2
cubeRoot(9)   // false
cubeRoot(27)  // 3
cubeRoot(28)  // false

它一定适用于很大的数字。表现是一项巨大的奖励。

但是，我使用的库意味着我只能使用以下数学函数/运算符：

abs, round, sqrt
/ * + -
===
> >= < <=
%
^

如果在JS中只使用上面的操作符提供答案，我可以自己将答案转换为(big.js)语法(我正在使用的库)。这个是可能的吗？

PS，我需要使用big.js，因为它保证了精度。

Answer 1

这里是与Kamilłczewski代码相同的另一个版本，但是使用了łAPI，并依赖于它的实现细节。

function isZero(v) {
    let digits = v.c;
    return digits.length === 1 && digits[0] === 0;
}

function isInteger(v) {
    if (isZero(v))
        return true;
    return v.c.length <= v.e + 1;
}

function neg(v) {
    return new Big(0).minus(v);
}


function cubeRoot(v) {
    const ZERO = Big(0);
    const TEN = new Big(10);

    let c0 = v.cmp(ZERO);
    if (c0 === 0)
        return ZERO;
    if (c0 < 0) {
        let abs3 = cubeRoot(v.abs());
        if (abs3 instanceof Big)
            return neg(abs3);
        else
            return abs3;
    }

    if (!isInteger(v))
        return false;

    // use 10 because it should be fast given the way the value is stored inside Big
    let left = TEN.pow(Math.floor(v.e / 3));
    if (left.pow(3).eq(v))
        return left;

    let right = left.times(TEN);

    while (true) {
        let middle = left.plus(right).div(2);
        if (!isInteger(middle)) {
            middle = middle.round(0, 0); // round down
        }
        if (middle.eq(left))
            return false;
        let m3 = middle.pow(3);
        let cmp = m3.cmp(v);
        if (cmp === 0)
            return middle;
        if (cmp < 0)
            left = middle;
        else
            right = middle;
    }
}

这段代码的主要思想是使用二进制搜索，但是搜索开始时对left和right的估计要比Kamil的代码要好一些。特别是，它依赖于这样一个事实，即Big以标准化的指数表示法存储该值:作为十进制数字和指数的数组。所以我们可以很容易地找到这样的n，以至于10^n <= cubeRoot(value) < 10^(n+1)。这个技巧应该可以减少循环中的几次迭代。可能使用牛顿-拉夫森迭代而不是简单的二进制搜索可能会更快一些，但我不认为在实践中您会发现两者之间的区别。

Answer 2

您可以使用JS内置BigInt。我假设输入是正整数。对于while循环，我提供了时间复杂度近似，其中n是输入的十进制数。这个版本的答案是受Salix alba回答和wiki“立方体根”的启发：

1. 二进制搜索 O(n log2(10)/3) <= O(1.11*n) (对于n=1000，我得到1110次迭代--测试这里，-对于l=0和r=a O(10/3 n)) 函数cubicRoot(a) { let d=Math.floor((a.toString(2)..length 1)/3)；//二进制数字nuber /3设r= 2n ** BigInt(d+1)；//右边界近似设l= 2n ** BigInt(d)；//左边界近似设x=BigInt(l)；设o=BigInt(0)；//旧历史值；(1){o= x；y=x*x* x；y(i%60？‘)：’\n‘+x).join(’‘)；//将长数拆分成多行字符串。

Answer 3

所以让我们来看看二进制的一些立方体。

2^3 = 8 = 100b (3 binary digits)
4^3 = 64 = 100 000b  (6 binary digits)
8^3 = 512 = 100 000 000b (9 binary digits)
(2^n)^3 = 2^(3n) = (3n binary digits).

因此，对于粗略的第一猜测，计算二进制数，d说，然后除以3，让n = d/3告诉我们立方体根数是否在2^n和2^(n+1)之间。计数数字可以链接到对数的原始第一近似。

如果您无法访问二进制数字，只需重复地除以8(或8的幂)，直到得到零的结果。

现在我们可以用牛顿-拉夫森到家里去解决了。维基百科立方根帮助我们给出了迭代公式。如果a是我们想要找到的数字，并且x_0是我们第一次使用上面的猜测

x_{n+1} = ( a / x_n^2 + 2 x_n ) / 3.

这可以非常快地收敛。例如，在a=12345678901234567890中，我们发现a介于8^21和8^22之间，因此立方体根必须介于2^21和2^22之间。

运行迭代

x_1 = 2333795, x_1^3 = 12711245751310434875 
x_2 = 2311422, x_2^3 = 12349168818517523448
x_3 = 2311204, x_3^3 = 12345675040784217664
x_4 = 2311204, x_4^3 = 12345675040784217664

我们看到，经过三次迭代，它已经收敛。检查表明，a介于2311204^3和2311205^3之间。

该算法可以在使用big.js进行计算时运行。上面的计算是使用Java的BigInt类完成的。