algorithm - 是否存在适用于特定语言的任意精度算术的通用实现策略？

Question

我正在考虑实现任意精度算术(有时称为 Bignum、Integer 或 BigInt)的不同方法。

似乎常见的习惯用法是使用数组来存储实际值，并在空间需求增长或缩小时根据需要重新分配它。

更准确地说，似乎数组元素的位大小通常是通常支持的第二大大小(可能使溢出计算更容易实现？)，e。 G。语言/平台支持 128 位大小的数字 -> 64 位数字数组 + 128 位变量来处理溢出。

是否有根本不同的方法来实现任意精度算术，或者上述是否是在没​​有巨大性能损失的情况下实现它的“行之有效”的方法？

我的问题是关于底层数据结构，而不是操作算法。我认识 Karatsuba、Toom-Cook 等人。

Answer 1

可以使用 Chinese Remainder Theorem至 represent large integers以与通常的 base-2^n 系统根本不同的方式。

我相信基于 CRT 的表示仍将使用元素数组，与传统表示一样，这些元素也是基于最方便的可用 native 算术的。但是，这些元素在除以一系列素数时保留数字的余数，而不是 base-2^n 数字。

与常规表示一样，使用的元素数量决定了可表示数字的最大大小。不幸的是，计算一个基于 CRT 的数字是否大于另一个并不容易，因此很难判断您的表示是否超出了最大大小。请注意，加法和乘法在 CRT 表示中非常快，如果您可以处理溢出问题，这可能是一个优势。

但是，要回答您的问题:我相信可以准确地说 base-2^n 系统确实是“久经考验”的表示形式，大多数流行的 bignum 库都使用它。我想我记得有现存的基于 CRT 的 bignum 库，尽管我最近没有检查它们是否仍然存在......