What are the best (portable) cross-platform arbitrary-precision math libraries?

Question

I’m looking for a good arbitrary precision math library in C or C++. Could you please give me some advices or suggestions?

The primary requirements:

1. It must handle arbitrarily big integers—my primary interest is on integers. In case that you don’t know what the word arbitrarily big means, imagine something like 100000! (the factorial of 100000).

2. The precision must not need to be specified during library initialization or object creation. The precision should only be constrained by the available resources of the system.

3. It should utilize the full power of the platform, and should handle “small” numbers natively. That means on a 64-bit platform, calculating (2^33 + 2^32) should use the available 64-bit CPU instructions. The library should not calculate this in the same way as it does with (2^66 + 2^65) on the same platform.

4. It must efficiently handle addition (+), subtraction (-), multiplication (*), integer division (/), remainder (%), power (**), increment (++), decrement (--), GCD, factorial, and other common integer arithmetic calculations. The ability to handle functions like square root and logarithm that do not produce integer results is a plus. The ability to handle symbolic computations is even better.

Here are what I found so far:

1. Java's BigInteger and BigDecimal class: I have been using these so far. I have read the source code, but I don’t understand the math underneath. It may be based on theories and algorithms that I have never learnt.

2. The built-in integer type or in core libraries of bc, Python, Ruby, Haskell, Lisp, Erlang, OCaml, PHP, some other languages: I have used some of these, but I have no idea which library they are using, or which kind of implementation they are using.

What I have already known:

1. Using char for decimal digits and char* for decimal strings, and do calculations on the digits using a for-loop.

2. Using int (or long int, or long long) as a basic “unit” and an array of that type as an arbitrary long integer, and do calculations on the elements using a for-loop.

3. Using an integer type to store a decimal digit (or a few digits) as BCD (Binary-coded decimal).

4. Booth’s multiplication algorithm.

What I don’t know:

1. Printing the binary array mentioned above in decimal without using naive methods. An example of a naive method: (1) add the bits from the lowest to the highest: 1, 2, 4, 8, 16, 32, … (2) use a char*-string mentioned above to store the intermediate decimal results).

What I appreciate:

1. Good comparisons on GMP, MPFR, decNumber (or other libraries that are good in your opinion).

2. Good suggestions on books and articles that I should read. For example, an illustration with figures on how a non-naive binary-to-decimal conversion algorithm works would be good. The article “Binary to Decimal Conversion in Limited Precision” by Douglas W. Jones is an example of a good article.

3. Any help in general.

Please do not answer this question if you think that using double (or long double, or long long double) can solve this problem easily. If you do think so, you don’t understand the issue in question.

Answer 1

GMP is the popular choice. Squeak Smalltalk has a very nice library, but it's written in Smalltalk.

You asked for relevant books or articles. The tricky part of bignums is long division. I recommend Per Brinch Hansen's paper Multiple-Length Division Revisited: A Tour of the Minefield.