CODEWITHSUNDEEP
javascriptnode.jsbigint
danday74
danday74

Reputation: 56966

JavaScript big integer square root

This concerns the new JavaScript BigInt type, as supported in Chrome and Node v10.4

Both the following lines throw an error:

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

Error is:

Cannot convert a BigInt value to a number

How do I get the square root of a BigInt in JavaScript? TIA

Upvotes: 15

Views: 10214

Answers (4)

anton platonov
anton platonov

Reputation: 11

To calculate the square root of a number, Newton's method is one of the fastest. Moreover, the more accurate the initial approximation of the root, the faster it will return the result. Below is an example of a function that calculates the square root quite efficiently (please note that the function is for javaScript's BigInt):

function sqrt(N) {
if(N < 0n) return Math.sqrt(-1);
let aprx;
if(N < 9007199254740991n) {
    aprx = BigInt(Math.floor(Math.sqrt(Number(N))));
    if(aprx**2n > N) aprx--;
    return aprx;
};

let base32 = N.toString(32),
    len = base32.length*5 - 5 + parseInt(base32[0], 32).toString(2).length;
base32 = null;

function approx(a1, len) {
    if(len < 53) {
        let aprx = BigInt(Math.floor(Math.sqrt(Number(a1))));
        if(aprx**2n > a1) aprx--;
        return aprx;
    }
    let base = Math.floor(len/2) - len%2;
    if(base%2 == 1) base--;

    let b1 = a1>>BigInt(base),
        b0 = BigInt.asUintN(base, a1),
        r1 = approx(b1, len - base),
        r0 = (((b1 - r1**2n)<<BigInt(base)) + b0)/(2n*r1);

    return (r1<<BigInt(base/2)) + (r0>>BigInt(base/2));
}

aprx = approx(N, len);
if(aprx**2n > N) aprx--;
return aprx; }

Upvotes: 1

Kamil Kiełczewski
Kamil Kiełczewski

Reputation: 92377

General case: n-th root

Here is more general solution for n-th root

/**
 * 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)}` );

Upvotes: 3

Klesun
Klesun

Reputation: 13673

There is an npm library bigint-isqrt, seem to work ok. It returns the floor value if there is no integer root.

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

Though it's still a mystery for me how magic numbers like value < 16n and 1n << 52n in it's implementation help finding a square root. Judging from a PR it's some sort of an approximation heuristic, I wonder whether it's more efficient than algorithms in other answers...

Upvotes: 3

kopaty4
kopaty4

Reputation: 2296

From here: 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))

Upvotes: 18

Related Questions