无论特定语言如何，是否存在有效的任意精度算术通用实现策略？
我正在考虑实现任意精度算术的不同方法（有时称为 Bignum、Integer 或 BigInt）。
似乎常见的习惯用法是使用数组来存储实际值，并在空间需求增长或收缩时根据需要重新分配它。
更准确地说，数组元素的位大小通常是通常支持的第二大大小（可能是为了使溢出计算更容易实现？），例如语言/平台支持 128 位大小的数字 -> 64位数字+ 128位变量的数组来处理溢出。
是否有根本不同的方法来实现任意精度算术，或者上述是“经过验证的”方法来实现它而不会造成巨大的性能损失？
我的问题是关于底层数据结构，而不是操作算法。我认识Karatsuba、Toom-Cook 等人。
I'm thinking about different ways to implement arbitrary-precision arithmetic (sometimes called Bignum, Integer or BigInt).
It seems like the common idiom is to use an array for the storage of the actual value and reallocate it as needed if space requirements grow or shrink.
More precisely, it seems that the bit size of the array elements is often the second largest size commonly supported (to make calculations with overflow easier to implement probably?), e. g. language/platform supports 128bit-sized numbers -> array of 64bit numbers + 128bit variable to handle overflow.
Are there fundamentally different ways to implement arbitrary-precision arithmetic or is the above the “tried and true” way to implement it without huge performance losses?
My question is about the underlying data structure, not the algorithms for operations. I know Karatsuba, Toom-Cook et alii.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
可以使用中国剩余定理来以与通常完全不同的方式表示大整数以 2^n 为底的系统。
我相信基于 CRT 的表示仍将使用元素数组，该数组与传统表示一样，基于可用的最方便的本机算术。然而，这些元素保存的是数字除以素数序列时的余数，而不是基数 2^n 的数字。
与传统的表示一样，所使用的元素的数量决定了可表示数字的最大大小。不幸的是，计算一个基于 CRT 的数字是否大于另一个数字并不容易，因此很难判断您的表示是否超出了最大大小。请注意，加法和乘法在 CRT 表示中非常快，如果您可以处理溢出问题，这可能是一个优势。
然而，回答你的问题：我相信可以准确地说，base-2^n 系统确实是“经过验证的真实”表示，大多数流行的 bignum 库都使用它。我想我记得有现存的基于 CRT 的 bignum 库，尽管我最近没有检查它们是否仍然存在......
It is possible to use the Chinese Remainder Theorem to represent large integers in a fundamentally different way from the usual base-2^n system.
I believe a CRT-based representation will still use an array of elements which, like the conventional representation, are based on the most convenient native arithmetic available. However, these elements hold the remainders of the number when divided by a sequence of primes, not base-2^n digits.
As with the conventional representation, the number of elements used determines the maximum size of the representable number. Unfortunately, it is not easy to compute whether one CRT-based number is greater than another, so it is hard to tell if your representation has overflowed the maximum size. Note that addition and multiplication are very fast in CRT representation, which could be an advantage if you can deal with the overflow issue.
However, to answer your question: I believe it is accurate to say that the base-2^n system is indeed the "tried and true" representation, which is used by most popular bignum libraries. I think I recall that there are extant CRT-based bignum libraries, although I have not checked lately to see if they are still around....