BigInteger libraries for JS

Some time ago I wrote an article about using JS in the Code Jam competition; sometimes, the solution for its problems require need the processing of very large integer numbers, to the point where they exceed the maximum “real” integer length of JS.

UPDATE 08/09/2013: The Silent Matt library test code has been updated, as a reader pointed out in a comment that it could run quite faster with a simple change; also, I rerun all tests in Chrome 28, which shows improvements in most libraries.

While JS doesn’t have a real integer primitive (everything is “number”), using values over 9007199254740992 (equivalent to 2^53) may not return the exact answer, as precision is lost; also, bitwise operations (like >> or |) are not allowed.

To work around this limitation, we can use “BigInteger”, a data structure that can hold integer numbers as big as we need them to be. In JS there are several libraries that offert his kind of structure. So, in order to find the best library for my usage, I investigated the different alternatives, and decided to write this post in order to share my findings.

In order to compare the performance of the different libraries, a brute force implementation of “Bullseye”, which is problem A of Round 1A 2013, was implemented, adjusting it for each library. The value used for the tests was “1 100000000000000”.

Tom Wu’s BigInteger (website)

It’s used by the Dojo toolkit as their BigInteger class, and was also used by Google as one of their V8 benchmarks.

While it’s quite well made for 2005 code, it defines many functions in the global namespace; on the bright side, it has a lot of functionality, and it’s quite easy to use even though the documentation is almost non-existant, as all the functions are listed at the bottom of the library.

The code:

var params = readStrings();

var currentPaint = new BigInteger(params[1], 10);
var currentRadius = new BigInteger(params[0], 10).add(BigInteger.ONE);
var numberCircles = 0;
var finished = false;
var TWO = BigInteger.ONE.add(BigInteger.ONE);
while (!finished) {
  var neededPaint = currentRadius.shiftLeft(1).subtract(BigInteger.ONE);
  if (neededPaint.compareTo(currentPaint) <= 0) {
    numberCircles++;
    currentPaint = currentPaint.subtract(neededPaint);
    currentRadius = currentRadius.add(TWO);
  } else {
    finished = true;
  }
}

return numberCircles;

It completes the test in 16.81 seconds.

JavaScript BigInteger Library by Silent Matt (website)

Well documented and easy to use library; the functions will take strings, regular numbers and BigInt objects, which is a big plus. On the down side, it didn’t include “bit shifting” functions, which should do operations like multiplying by a power of 2 a lot more efficient.

The code:

var params = readStrings();

var currentPaint = new BigInteger(params[1]);
var currentRadius = new BigInteger(params[0]).add(BigInteger.small[1]);
var numberCircles = 0;
var finished = false;
var TWO = BigInteger(2);

while (!finished) {
  var neededPaint = currentRadius.multiply(2).subtract(BigInteger.small[1]);
  if (neededPaint.compare(currentPaint) <= 0) {
    numberCircles++;
    currentPaint = currentPaint.subtract(neededPaint);
    currentRadius = currentRadius.add(BigInteger.small[2]);
  } else {
    finished = true;
  }
}

return numberCircles;

Completes the test in 14.71 seconds.

Big Integer Library by Leemon Baird (website)

Very powerful library, although can be a bit tricky to use. What I liked the most about it is the ability to do operations “in place”; while the other libraries will always create a new instance of BigInteger for each operation, this library provides the possibility to perform the operations directly on its values, which can make it a lot faster. On the down side, it can be tricky to use; for instance, when parsing a string into a bigInt, the minimum number of elements needs to be specified, and the in-place operations require manual control of the number size in order to provide a correct result.

The code:

var params = readStrings();
var currentPaint = str2bigInt(params[1], 10, 25);
var currentRadius = str2bigInt(params[0], 10, 25);
addInt_(currentRadius, 1);
var numberCircles = 0;
var finished = false;
while (!finished) {
  var neededPaint = dup(currentRadius);
  leftShift_(neededPaint, 1);
  addInt_(neededPaint, -1);
  if (equals(neededPaint, currentPaint)|| greater(currentPaint, neededPaint)) {
    numberCircles++;
    sub_(currentPaint, neededPaint);
    addInt_(currentRadius, 2);
  } else {
    finished = true;
  }
}

return numberCircles;

Completes the test in 8.24 seconds (best result among all libraries, quite impressive!).

BigInteger.js by Peter Olson (website)

This library has a nice documentation, and is simple and easy to use; for instance, the functions will take integer values, and it’s even possible to use regular integer operations as the “valueOf” function is overwritten; that said, it has limited functionality, and in some cases the function names are quite different than the other libraries, and, in my opinion, using a different style than what other languages tend to choose.

The code:

var params = readStrings();
var currentPaint = bigInt(params[1]);
var currentRadius = bigInt(params[0]).next();
var numberCircles = 0;
var finished = false;
var TWO = bigInt(2);

while (!finished) {
  var neededPaint = currentRadius.times(2).minus(1);
  if (neededPaint.compare(currentPaint) <= 0) {
    numberCircles++;
    currentPaint = currentPaint.minus(neededPaint);
    currentRadius = currentRadius.add(2);
  } else {
    finished = true;
  }
}

return numberCircles;

Completes the test in 5 minutes 57.32 seconds.

Conclusion

Ultimately, the choice of library depends on the project; some may require basic functionality, and others may need as much performance as possible. In the past I used Tom Wu’s library, but I’m quite impressed with the performance and design of Silent Matt’s solution, so that will be my choice for future developments that require very large integers.

comments powered by Disqus