var one = BigInt("1");
var A = BigInt("1");
var B = BigInt("1");for (var i=1; i<=1000; i++)
A = BigInt.multiply(A, B);
B = BigInt.add(B, one);
}console.log("factorial(1000) is " + A);
- finding a C/C++ library for arbitrary precision integer arithmetic.
- adapt the code and feed it to the Cheerp compiler.
- test it and benchmark it.
- go to bed.
Choosing a C/C++ BigInt library
I wrestled a bit with Boost and GMP build systems (I had to make them work with the Cheerp compiler) before turning to LibTomMath and managing at the first attempt. It’s a pure C library with a mainly educational purpose. No dependencies required, very liberal license, seemed the perfect choice for my purpose.
[[ps: while publishing the article I realized that there is a sister library that promise to be even faster: TomsFastMath. I will give it a try at some point]]
Wrapping the memory management and C-style functions calls in a C++ class was needed and consulting the library manual it turned out straightforward (and required no understanding of how a BigInt library internally works).
This is, for example, a function to sum 2 BigInts:
static BigInt* BigInt::add(const BigInt& a, const BigInt& b)
BigInt* res = new BigInt();
//mp_add is the libtommath backend function
//wrapper takes care of checking the error
code returned by mp_add
Then I played a bit with calculating some factorials, fixed the inevitable errors, and I had a working C++ class.
Compile it with Cheerp
Cheerp aims to be just a regular C/C++ compiler. You call it like:
/opt/cheerp/bin/clang++ source_file.cpp -o output.js -target cheerp
cd build_libtommath &&
/opt/cheerp/bin/clang *.c -c -O3 -target cheerp &&
cd .. &&
/opt/cheerp/bin/clang++ wrapper.cpp -c -Ilibtommath -O3 -target cheerp &&
/opt/cheerp/bin/clang++ build_libtommath/*.bc wrapper.bc -o wrapper.js -O3 -target cheerp -cheerp-pretty-code
It builds, perfect.
#include <client/types.h> //Cheerp provided header
//that forward declares String methodsclient::String* BigInt::toString(int radix) const
int dim = 0;
wrapper( mp_radix_size(&number, radix, &dim) );
wrapper( mp_toradix(&number, &std_string, radix) );
return new client::String( std_string.c_str() );
Recompiling everything (by now I had a script in place), a couple of more bug fixing, and …with more
Test & benchmark
I ran some tests, it seemed to work well enough, it was late… I will need to get back to checking things for real at some other point.
I found some great resources on BigInt around, and one had a very easy to hack benchmarking page, that allowed to add your very own implementation of BigInt to be pit against the others directly on the client-side.
You could try it for yourself: BigInt’s benchmark.
Ideally, try it on different browsers/devices. On Chrome the results are not very encouraging (= is the last among the considered libraries), while on Firefox and Safari the Cheerp backed BigInt implementation is clearly the fastest in the first 2 families of benchmarks.
There are lots of benchmarks, I would advise to concentrate on addition/subtraction one, that are the only ones in which this library is competitive (and luckily, they are at the top of the page).
What does all this mean?
So, by being very restrictive I could claim to be “creator of the best addition and subtraction BigInt library that exists outside Chrome”.
I don’t see anything coming in the way of you repeating the same outlined process for [fill in with whatever library you may need]. The problem is not in finding great C/C++ libraries, nor in adapting the few lines of code required.
Learning to work with the Cheerp compiler may take a few tries, we are trying to render less steep the process, and there are lots of resources to get you started.