86

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 “<strong>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.

4

5 回答 5

27

GMP是流行的选择。Squeak Smalltalk 有一个非常好的库，但它是用 Smalltalk 编写的。

您要求提供相关书籍或文章。bignums 的棘手部分是长除法。我推荐 Per Brinch Hansen 的论文Multiple-Length Division Revisited: A Tour of the Minefield。

于 2010-04-04T04:48:21.547 回答
14

总的来说，他最快的通用任意精度库是GMP。如果要使用浮点值，请查看MPFR库。MPFR 基于 GMP。

关于其他语言的本机任意精度支持，由于许可证、代码大小和代码可移植性的原因，Python 使用自己的实现。GMPY模块允许 Python 访问 GMP 库。

于 2010-04-03T07:56:21.580 回答
9

请参阅TTMath，这是一个免费的小型模板化标头库，可供个人和商业使用。

于 2012-03-12T09:22:40.760 回答
8

我自己并没有将任意精度的算术库相互比较，但是那些确实似乎或多或少一致地选择了 GMP 的人。值得一提的是，GHC Haskell 和 GNU Guile Scheme 中的任意精度整数都是使用 GMP 实现的，并且语言枪战中 pidigits 基准测试的最快实现是基于 GMP。

于 2010-04-02T23:04:36.110 回答
5

帕丽呢？它建立在顶级 GMP 之上，并提供了您将需要的所有其他关于数论运算的好东西（以及许多符号计算的东西）。

于 2010-11-10T17:31:24.263 回答