Effective algorighms for BigInteger

[username1565]

Hello. Is there any effective algorithms for fast multiplying, fast divide, fast finding N-root, fast factorization, etc... I think this will be useful if this will be included to this library.

For example, I cann't got sqrt(x), if x is biginteger square...

Best regards.

[peterolson]

sqrt and similar functions are not in the scope of this library since the output is usually not an integer.

The library already includes the karatsuba multiplication algorithm for large inputs, and there are various performance optimizations for division as well.

[username1565]

Found this here, and this really fast: https://stackoverflow.com/questions/42204941/square-root-and-operators-for-biginteger-and-bigdecimal

Code:

function sqrt(n) { //find whole square root from biggest square
    var a = bigInt(1);
    var b = n.shiftRight(5).add(bigInt(8));
    var mid;

    while (b.compareTo(a) >= 0) {
        mid = a.add(b).shiftRight(1);
        if (mid.multiply(mid).compareTo(n) > 0) {
            b = mid.subtract(bigInt(1));
        } else {
            a = mid.add(bigInt(1));
        }
    }
    var sqrt = a.subtract(bigInt(1));

    return result =
        (sqrt.multiply(sqrt).eq(n)) //if this is square root
        ? sqrt                      //return this
        : [sqrt, n.subtract(sqrt.multiply(sqrt))]; //or return this with difference
        //In this case n = sqrt^2 + difference and sqrt^2 is the biggest square, lower n.
}

test

var big = bigInt.randBetween('1e32', '9e32');
var big2 = big.multiply(big);
document.write(
    '<br><br>big = ', big.toString()
    ,'<br> big^2 = ', big2.toString()
    ,'<br> sqrt(big^2) = big = ', sqrt(big2).toString() //whole square root
);

var big3 = bigInt.randBetween('1e32', '9e32');
document.write(
    '<br><br>big3 = ', big3.toString()
    ,'<br> sqrt(big3) = sqrt(biggest_square) + difference = ', sqrt(big3).toString() //root from biggest square + difference
);

result:

big = 475408029155563129521815212228154
big^2 = 226012794185576762606275652361827838517244511980445399809350247716
sqrt(big^2) = big = 475408029155563129521815212228154

big3 = 457389092316401448683025161965699
sqrt(big3) = sqrt(biggest_square) + difference = 21386656875640976,15503394311733123

I did add this, and fix. Only positive numbers. You can see the source code on my branch.

[username1565]

Negative numbers was been excluded.

[Yaffle]

@username1565 https://github.com/peterolson/BigInteger.js/issues/73#issuecomment-351155110

[username1565]

Thanks, @Yaffle for you code from comment https://github.com/peterolson/BigInteger.js/issues/73#issuecomment-351155110

This code working to me:

// floor(A**(1/n)), ceil and round available too.
//call this by A.nthRoot(n); where A is bigInt.
BigInteger.prototype.nthRoot = function (n, rounding) { // bugs - ? (test this!)
    //"rounding" parameter
    //can be a strings:
    //1. 'floor', undefined, or another other value - by default...
    //2. 'ceil' - up rounding
    //3. 'round' - rounding to nearest integer.

  var A = this;
  //Code from here: https://github.com/peterolson/BigInteger.js/issues/146
  //I already have integer logarithm function here

  // https://stackoverflow.com/questions/15978781/how-to-find-integer-nth-roots
  var nthRoot = function (A, n, e) {
    if (e.compareTo(n) < 0) {
      return bigInt(1);
    }
    var q = e.divide(n).divide(bigInt(2));
    var t = bigInt(2).pow(q);
    var x0 = q.compareTo(bigInt(0)) === 0 ? bigInt(4) : t.add(bigInt(1)).multiply(nthRoot(A.divide(t.pow(n)), n, e.subtract(q.multiply(n))));
    var x = x0;
    var xp = x.add(bigInt(1));
    while (x.compareTo(xp) < 0) {
      xp = x;
      var t = A.divide(x.pow(n.subtract(bigInt(1))));
      x = x.multiply(n.subtract(bigInt(1))).add(t).divide(n);
    }
    return xp;
  };
  A = bigInt(A);
  n = bigInt(n);
  if (A.compareTo(bigInt(0)) < 0 || n.compareTo(bigInt(0)) <= 0) {
    throw new RangeError();
  }
  if (A.compareTo(bigInt(0)) === 0) {
    return bigInt(0);
  }
  var e = bigInt(A.integerLogarithm(bigInt(2)).e);
  var x = nthRoot(A, n, e);

  if(typeof rounding !== 'undefined'){
    if(rounding === 'ceil'){
        return x.next();
    }
    else if(rounding === 'round'){
        //10 n√x = n√(10^n)x;
        //(n√(10^n)x % 10 >= 5) ? n_root++ : n_root;
        var n10 = bigInt('10').pow(n);
        var An10 = A.multiply(n10);
        var n_root_An10 = An10.nthRoot(n);
        var last_digit = n_root_An10.mod(bigInt('10'));
        if(last_digit.geq(bigInt('5'))){return x.next()}
        //else return default floor.
    }
    //else return default floor
  }//else return default floor

  return x;
  //if x not a whole root, and A not a x.pow(m), you can calculate difference yourself.
}   
    SmallInteger.prototype.nthRoot = BigInteger.prototype.nthRoot; //add this to make function callable.

test

//Using random bigIntegers
var x = bigInt.randBetween('1', '1e32');
var n = bigInt.randBetween('1', '30');
//remember that biginteger length limited and maximum 999 digits.
// 999/32 = 31,21875, so 30 is maximum exponent.
var A = x.pow(n);
var n_th_root_A_is_x = A.nthRoot(n);

document.write(
    '<br><br>'
    ,'<br>x = ', x.toString()
    ,'<br>n = ', n.toString()
    ,'<br>A = x^n = ', A.toString()
    ,'<br>n = ', Math.pow(A.toJSNumber(), 1/n.toJSNumber())
    ,'<br><sup>n</sup>√A = x = ', n_th_root_A_is_x.toString()
    ,'<br>(n_th_root_A_is_x.eq(x)): ', n_th_root_A_is_x.eq(x)
);
//another test

var n_th_root_from_x = x.nthRoot(n);
var n_th_root_from_x_ceil = x.nthRoot(n, 'ceil');
var n_th_root_from_x_round = x.nthRoot(n, 'round');

document.write(
    '<br><br>'
    ,'<br>x = ', x.toString()
    ,'<br>n = ', n.toString()
    ,'<br>n = ', Math.pow(x.toJSNumber(), 1/n.toJSNumber())
    ,'<br>y = floor(<sup>n</sup>√x) = ', n_th_root_from_x.toString()
    ,'<br>y = ceil(<sup>n</sup>√x) = ', n_th_root_from_x_ceil.toString()
    ,'<br>y = round(<sup>n</sup>√x) = ', n_th_root_from_x_round.toString()

    ,'<br>(n_th_root_from_x.pow(n).eq(x)): ', n_th_root_A_is_x.pow(n).eq(x) //sometimes true
);

result:

x = 6474764970850501921673626511516
n = 10
A = x^n = 129491149078855753972157214579042030550896160804706462534931300402880317054541403892334373642017325799387537666133854443197460531410719438768049477531279542285944473364328318503776303585957504612557638982148438703047897303769888615815117481506969477722861704096335509610525713442932016278096081667310696267776
n = 6.474764970850528e+30
n√A = x = 6474764970850501921673626511516
(n_th_root_A_is_x.eq(x)): true

x = 6474764970850501921673626511516
n = 10
n = 1205.3756135968495
y = floor(n√x) = 1205
y = ceil(n√x) = 1206
y = round(n√x) = 1205
(n_th_root_from_x.pow(n).eq(x)): false

Success!