JavaScript 大整数平方根

Question

这涉及 Chrome 和 Node v10.4 中支持的新 JavaScript BigInt 类型

以下两行都会引发错误：

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

错误是：

无法将 BigInt 值转换为数字

如何在 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

有一个 npm 库 bigint-isqrt，似乎工作正常。如果没有整数根，则返回下限值。

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

_{虽然对我来说仍然是个谜，但它的实现中像}

value < 16n

和

1n << 52n

这样的神奇数字如何帮助找到平方根。从PR来看，它是某种近似启发式，我想知道它是否比其他答案中的算法更有效......

Answer 3

一般情况：n次根

这是n次根

的更通用解决方案

/**
 * Calculate n-th root of val
 * Parameters:
 * k: is n-th (default sqare root)
 * limit: is maximum number of iterations (default: -1 no limit)
 */
function rootNth(val, k=2n, limit=-1) {
    let o = 0n; // old approx value
    let x = val;
    
    while(x**k!==k && x!==o && --limit) {
      o=x;
      x = ((k-1n)*x + val/x**(k-1n))/k;
      if(limit<0 && (x-o)**2n == 1n) break;
    }
    
    if ((val-(x-1n)**k)**2n < (val-x**k)**2n) x=x-1n;
    if ((val-(x+1n)**k)**2n < (val-x**k)**2n) x=x+1n;
    return x;
}

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

Answer 4

要计算数字的平方根，牛顿法是最快的方法之一。此外，根的初始近似值越准确，返回结果的速度就越快。下面是一个非常有效地计算平方根的函数示例（请注意，该函数适用于 javaScript 的 BigInt）：

function sqrt(N) {
if(N < 0n) return Math.sqrt(-1);
if(N < 9007199254740992n) return BigInt(Math.floor(Math.sqrt(Number(N))));

let hex = N.toString(16), k = 13, i = 0,
    lg = parseInt(hex[0], 16).toString(2).length;
if(lg < 3) k--;
lg = (lg + lg%2)/2;

let hex_len = hex.length, root_len = hex_len*2 - lg%2,
    cur_len = 78 - 3*(lg%2), flag = hex_len < 26,
    a2 = parseInt(hex.substring( 0, k), 16),
    a1 = parseInt(hex.substring(k, k + 13), 16);

hex = null;
if(flag) a1 = a1<<((13 - hex_len%13)*4);

let r2 = BigInt(Math.floor(Math.sqrt(a2))),
    r1 = (((BigInt(a2) - r2**2n)<<52n) + BigInt(a1))/(2n*r2),
    approx = ((r2<<52n) + r1);
approx = (root_len > cur_len) ?  approx<<BigInt(root_len - cur_len) : approx = approx>>BigInt(cur_len - root_len);

approx = (approx + N/approx)>>1n;
if(flag) return approx;

let approx_prev = approx;
while (i < 4503599627370495) {
    approx = (approx + N/approx)>>1n;
    i++;
    if (approx_prev == approx) break;
    approx_prev = approx;
}

return approx; }