logo标签列表

什么是最佳的（便携式）跨平台任意精度数学库？

c++cbigintegerbigdecimalgmp
90
我正在寻找一个好的C或C++任意精度数学库。你能给我一些建议或建议吗？
主要要求：

  1. 它必须能够处理任意大的整数——我的主要兴趣在于整数。如果您不知道“任意大”这个词是什么意思，可以想象一下100000！（100000的阶乘）。

  2. 精度不需要在库初始化或对象创建时指定。精度应该只受系统可用资源的限制。

  3. 它应该充分利用平台的全部功能，并且应该本地处理“小”数字。这意味着在64位平台上，计算（2 ^ 33 + 2 ^ 32）应该使用可用的64位CPU指令。库不应该像在同一平台上计算（2 ^ 66 + 2 ^ 65）那样计算它。

  4. 它必须高效地处理加法（+）、减法（-）、乘法（*）、整数除法（/）、余数（%）、幂（**）、递增（++）、递减（--）、GCD、阶乘和其他常见的整数算术运算。能够处理不产生整数结果的平方根和对数等函数的能力是一个加分项。能够处理符号计算更好。

这是我目前找到的：

  1. Java中的BigInteger和BigDecimal类：我一直在使用它们。我读过源代码，但我不理解其背后的数学知识。它可能基于我从未学过的理论和算法。

  2. bc、Python、Ruby、Haskell、Lisp、Erlang、OCaml、PHP等其他语言中的内置整数类型或核心库：我曾经使用过其中一些，但我不知道它们使用的是哪个库，或者它们使用的是哪种实现方式。

我已经知道的内容：
1. 使用`char`表示十进制数字，使用`char*`表示十进制字符串，在数字上使用`for`循环进行计算。 2. 使用`int`（或`long int`、`long long`）作为基本的“单位”，并将该类型的数组作为任意长的整数，通过`for`循环对元素进行计算。 3. 使用整数类型存储十进制数字（或几个数字），例如BCD（二进制编码十进制）。 4. Booth乘法算法。
我不知道的内容：
将上述二进制数组以不使用朴素方法的方式转换为十进制。朴素方法的一个例子：(1) 从低位到高位添加位数：1、2、4、8、16、32等；(2) 使用上面提到的char*字符串来存储中间的十进制结果。
我欣赏的是：

  1. 关于 GMP、MPFR、decNumber（或您认为好的其他库）的良好比较。

  2. 建议我应该阅读哪些书籍和文章。例如，有图示的关于一个非幼稚的二进制到十进制转换算法如何工作的文章会很好。Douglas W. Jones 的文章“Binary to Decimal Conversion in Limited Precision”是一篇好文章的例子。

  3. 一般性帮助。

请勿回答此问题，如果您认为使用double（或long double，或long long double）可以轻松解决此问题。如果您这样认为，那么您不理解所涉及的问题。
3
就我所看到的，GMP 似乎是一个不错的库。我想知道的是，为什么 Python / Haskell / Erlang 等贡献者需要重新发明轮子。如果 GMP 这么好，为什么不依赖它呢？GPL / LGPL 许可证可能是其中一个问题，但除此之外（以及舍入模式问题），是否还有其他 GMP 的劣势？Python / Haskell / Erlang 或任何加密库内置整数是否比 GMP 更快？如果是这样，如果许可证允许，我想提取并使用它。 - Siu Ching Pong -Asuka Kenji-
我在http://www.cs.uiowa.edu/~jones/bcd/decimal.html上发现了一篇很好的文章，作者是Douglas W. Jones。这篇文章描述了一种使用仅8位整数运算将16位整数转换为十进制表示的方法。其思想是将16位数字分为4个nibble，每个nibble代表一个基于16进制的“数字”。因此，digit-0（n0）代表x1，n1 => x16，n2 => x256，n3 => x4096。然后，显然十进制数的digit-0（d0）是n0 * 1 + n1 * 6 + n2 * 6 + n3 * 6的结果的digit-0。通过适当地处理进位，也可以计算出d1到d4。 - Siu Ching Pong -Asuka Kenji-
然而，就我所能想象的而言，Douglas上述的想法无法扩展以处理任意长的二进制整数。这是因为数字1（16^0）、16（16^1）、256（16^2）和4096（16^3）是预先计算的。问题变成了如何表示十六进制的16^n，其中n是任意大的数。 - Siu Ching Pong -Asuka Kenji-
5个回答
30
谢谢您提供论文的链接！是的，我同意除法是最棘手的部分。很久以前我就知道如何使用“纸笔方法”手动进行除法 :-)，因此相同的方法可以应用于表示十进制数字的char *（每个char表示一个十进制数字）或BCD字符串的int *（每个int表示4/8/16个BCD数字）。但是，我想知道真实世界中的生产级别库是否模仿了“纸笔方法”，因为它太慢了。 - Siu Ching Pong -Asuka Kenji-
为了了解原因，让我们想象一下100,000,000,000,000,000 / 333,333,333,333的运行方式：第一步是比较100,000,000,000和333,333,333,333。因为前者小于后者，所以计算简单地移动到下一个数字。第二步是找出1,000,000,000,000 / 333,333,333,333的商，这涉及到试错乘法333,333,333,333 * 1（和* 2，* 3和* 4），或在循环中进行连续的减法。你看到它有多慢了吗？我相信存在更有效率的算法。 - Siu Ching Pong -Asuka Kenji-
3
@Sui：Brinch Hanson 展示了如何将试错方法最多减少到两次。真的非常令人印象深刻。 - Norman Ramsey
好的，让我仔细看一下这篇论文。谢谢！ - Siu Ching Pong -Asuka Kenji-
1
我不确定你最终在哪里找到了解决方案，也不知道你用什么格式存储数字，但是COBOL的COMP-3 nybble格式更加方便处理，因为它更紧凑，每4位存储一个0-9值，并且你不需要从ASCII字符值中减去16进制30才能得到可用的数字。 - user1899861
15

总体而言，最快的通用任意精度库是GMP。如果您想使用浮点数值，请查看MPFR库。MPFR基于GMP。

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

谢谢您的回复！您提到了“代码可移植性”。能否请您解释一下问题所在？我认为GMP是可移植的，并且支持主要平台... - Siu Ching Pong -Asuka Kenji-
2
“代码可移植性”并不等同于“支持主要平台”。Python使用简单的实现，对C编译器的行为做出了很少的假设，因此相同的代码可以在几乎任何C编译器上编译。GMP使用更多的代码（C和高度调整的汇编），使GMP更快，但也会对C编译器和汇编器的行为做出更多的假设。例如，GMP不受Microsoft Visual Studio编译器的良好支持。有一个名为MPIR（www.mpir.org）的GMP分支，它支持Microsoft的编译器。 - casevh
我明白了。这意味着Python实现更像ANSI C，而GMP实现使用__asm技巧...谢谢您的解释。 - Siu Ching Pong -Asuka Kenji-
13

请查看TTMath，它是一个小型的模板头文件库，可供个人和商业使用。

嘿！这是一个易于使用的库，它似乎利用了CPU的计算能力，并使用了一些C++模板魔法来完成工作。很棒的库！给你点赞！ - Siu Ching Pong -Asuka Kenji-
是的，它有一种宽松的非强制性BSD许可证。 - plasmacel
从上面的页面可以看出：“值的大小在编译时设置。”- 因此这不符合要求。 - osxdirk
9

我个人没有比较过各种任意精度算术库，但是那些进行比较的人似乎普遍认为GMP最好。值得一提的是，Haskell语言和GNU Guile Scheme中的任意精度整数都是使用GMP实现的，而 语言 shootout 中的 pidigits 基准测试的最快实现也是基于GMP的。

谢谢！^___^ 很棒的信息！ - Siu Ching Pong -Asuka Kenji-
5

那么Pari呢？它是建立在GMP之上的，提供了所有你需要的关于数论运算的其他好东西（以及许多符号计算的内容）。

欢迎您 :-) 此外，使用 Pari，您可以使用 GP 快速创建原型，当您满意后编写优化的 C 版本（我认为它还带有一个 GP->C 编译器来帮助完成这项工作）。 - fortran
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接