将大数类型的结构转换为人类可读字符串的高效方法是什么？

Question

我有点问题。为了增加我的C语言知识，我决定尝试实现一个基本的bigint库。bigint结构的核心将是一个32位整数数组，因为它们可以适应寄存器。这样，我就可以在64位整数中进行数字操作，而且每个部分的结果都可以进行位移。我已经实现了基本的加法，并为了测试其工作情况，必须打印该数组。对于我的自我测试目的，如果我使用printf()并以十六进制输出每个数字，那么这样做是可以的。我可以很好地阅读它。

然而，大多数人无法阅读十六进制。由于该数字存储在（本质上）2 ^ 32进制中，因此打印有点棘手。有什么好方法可以转换为10进制？

编辑：

这与如何从一种进制转换到另一种进制无关，而是涉及到一种良好的实现方式。我想到了使用另一种具有转换功能的大数值来生成另一种进制的输出。

- ZachS

---

为了测试一个大数实现，我建议使用像Clisp这样的通用Lisp实现。Common Lisp内置了bignums，您可以启动解释器并键入表达式。您不需要了解Lisp即可执行基本操作，例如加法(+ 1 2 3)或指数运算(expt 42 10000)。十六进制常量是以#x开头的数字。(= #x10 16)显示真值T，而(= #x10 10)则显示假值NIL。 - Gilles 'SO- stop being evil'

如果你熟悉Emacs，还有一个更简单的大数引用实现是它的计算器（M-x calc）。 - Gilles 'SO- stop being evil'

@Giles：谢谢你的建议，不过我目前正在使用GCHi进行测试。这是个好主意。 - ZachS

bc 和 dc 实用程序也可以进行大数计算。 - caf

Answer 1

首先，在没有基本操作（如除法和模数）的情况下，您无法以合理的方式进行I/O。为了提供将大整数转换为基于10的字符串的高效实现，我正在研究两种可能的优化方法：

第一种是您可以通过某个10的幂次方来进行除法，而不是直接除以10。这意味着，例如每次将数字除以10000时，您将获得四个基于10的数字。

第二种是，您如何选择要除以哪个10的幂次方？10、100、1000、10000等等...
似乎有一个很好的选择，那就是最大能够适应您的字（32位）的10的幂次方。幸运的是，您可以比实现两个“bigint”时更有效地实现单字除法/模数。

我还没有给出具体实现，因为我仍在利用我的业余时间研究这个问题，因为我已经在我的库中实现了基本操作，而I/O则是下一步，希望能够成功 ;)

- Khaled Alshaya

---

如果我没记错的话，这是Knuth推荐的方法。+1 - President James K. Polk

这基本上就是我要的。我知道 IO 是后面的问题，但它是需要解决的问题，所以我想不妨问一下。 - ZachS

Answer 2

首先，将您的基本类型中最大的10的幂除以它是开始的最佳方式。在您的情况下，这将是除以10^9。由于您将能够将其重用于通用除法/模数代码的一部分，因此此代码应该是通用的。

运行时间将为O(n^2)（即如果您的数字是两倍大，转换将需要四倍长），但对于中等大小的数字来说，速度应该足够快。

对于非常大的值，您将希望缓存大的10的幂，例如10^1000、10^2000、10^4000、10^8000等，然后除以大于或等于要转换的数字的1/2的10的幂。重复此过程，直到数字足够小，可以使用除以10^9快速转换。根据您的除法算法的效率如何，除非遇到超过一百万位或更多的数字，否则此方法可能不会更快。

如果您正在编写一个交互式计算器，在其中每个数字都将被显示，则使用基数10^9将更快速地进行显示（它将是O(n)，即如果您的数字是两倍大，转换只需要两倍长）。

- casevh

Answer 3

重复除以10的常规方法显然会非常缓慢。

一个明显的快速方法是预先计算每个位置上每个数字对应的大整数数组。然后，您可以进行二进制搜索和相对便宜的比较/减法来找到最高位数字，然后逐个找到每个数字。

当您降至最后的32（或64）位时，可以恢复除以10。

- Dipstick

---

你建议对每个大整数进行缓存吗？它们有太多了。 - recursive

@recursive- 不是每个可能的大整数。只有所有数字都为零，除了一个数字的所有可能的大整数。因此，如果最大的大整数在十进制下会产生28位数字，那么您将缓存280个值。 - bta

@crhisharris：对于大多数典型的bigint使用情况，与更复杂的操作（如两个bignum的乘法（或更糟糕的是它们的矩阵乘法）或测试它们是否为质数）相比，重复除以10的成本微不足道。 - Gilles 'SO- stop being evil'

我认为我理解了你的方法，但我不确定它是否比每一步都除以10更快。请记住，比较两个占用k个32位字的大整数需要k步。 - President James K. Polk

@GregS - 比较不需要 k 步骤 - 你只需要查看一个数字是否小于另一个数字，这样你就可以在它们不同的第一步停止了。显然，减法需要 k 步骤，但这仅在每个非零数字执行一次。 - Dipstick

Answer 4

我能想到的最有效的算法如下。它应该具有O(n·(log n)²·log log n)的运行时间复杂度，而不是具有二次运行时间复杂度的朴素算法。

1. 假设不失一般性，数字A为2ⁿ⁺¹位长。它可能有前导零。
2. 通过重复平方计算i从0到n的2的2的i次方的十进制表示，如果这是最顶层的递归，则进行此操作。
3. 将输入数字的位序列分成两部分B和C。较不重要的部分C包括A的2ⁿ个最低有效位，而部分B则是其余更重要的位。
4. 使用二次运行时间算法将B和C转换为它们的十进制表示，如果它们足够短，则可以通过递归调用此算法来完成。
5. 将B的十进制表示乘以缓存的2的2的n次方的十进制表示，并加上C的十进制表示，以获得A的十进制表示。

在第2步和第5步中，您需要一个十进制乘法算法。对于数位数为数万的数字，应使用适用于10进制的Schönhage-Strassen算法版本。这将导致上述运行时复杂度。对于较短的数字，根据其长度，应使用Toom-Cook算法、Karatsuba算法或长乘法。然而，我目前无法告诉您如何在10进制中实现Schönhage-Strassen算法，因为我找到的所有完整描述都是针对2进制的，而我不知道足够的数论知识来推导它。

- Benjamin Berger