JavaScript 大整数平方根

Question

这涉及新的 JavaScript BigInt 类型，在 Chrome 和 Node v10.4

中得到支持

以下两行都会引发错误：

Math.sqrt(9n)
Math.sqrt(BigInt(9))

错误是：

Cannot convert a BigInt value to a number

如何获得 JavaScript 中 BigInt 的平方根？ TIA

Answer 1

从这里开始：https://golb.hplar.ch/2018/09/javascript-bigint.html

function sqrt(value) {
    if (value < 0n) {
        throw 'square root of negative numbers is not supported'
    }

    if (value < 2n) {
        return value;
    }

    function newtonIteration(n, x0) {
        const x1 = ((n / x0) + x0) >> 1n;
        if (x0 === x1 || x0 === (x1 - 1n)) {
            return x0;
        }
        return newtonIteration(n, x1);
    }

    return newtonIteration(value, 1n);
}

sqrt(BigInt(9))

Answer 2

这是 n-th root

的更通用的解决方案

function rootNth(val, k=2n) {
    let o = 0n; // old approx value
    let x = val;
    let limit = 100;
    
    while(x**k!==k && x!==o && --limit) {
      o=x;
      x = ((k-1n)*x + val/x**(k-1n))/k;
    }
    
    return x;
}

let v = 1000000n;
console.log(`root^3 form ${v.toString()} = ${rootNth(v,3n).toString()}` );

Answer 3

有一个 npm 库 bigint-isqrt，似乎工作正常。 returns 没有整数根时的下限值。

const sqrt = require('bigint-isqrt');
> sqrt(1023n);
31n
> sqrt(1024n);
32n

_{虽然对我来说仍然是一个谜，如 value < 16n 和 1n << 52n 在它的实现中如何帮助找到平方根。从 PR 判断它是某种近似启发式算法，我想知道它是否比其他答案中的算法更有效...}

JavaScript 大整数平方根

JavaScript big integer square root

javascript

bigint

node.js