将bignum类型结构转换为人类可读字符串的有效方法是什么？
我有点问题。 为了增长我对C的了解，我决定尝试实现一个基本的bigint库。
bigint结构的核心是一个32位整数数组，因为它们适合寄存器而被选中。 这将允许我在数字之间进行操作，这些数字将以64位整数溢出（这也适合寄存器，因为我在x86-64上），并且我可以对结果的每个部分进行位移位。 我已经实现了基本的添加，并且为了测试它是否正常工作，我必须打印数组。 对于我自己的测试目的，如果我使用printf()并以hex输出每个数字就没问题。 我可以读到这很好。
但是，大多数人都读不懂hex。 由于数字存储在（基本上）基数2 ^ 32中，因此打印有点问题。 什么是转换到基数10的好方法？
编辑：
这不涉及知道如何从基数转换为基数，而是关于实现这一点的好方法。 我正在考虑用另一个基础制作另一个bigint并转换打印。
首先，如果没有基本操作（例如除法和模数），就不能以合理的方式进行I / O. 为了提供将bigint转换为base-10字符串的有效实现，我正在研究两种可能的优化：
首先，你可以除以十分之一而不是十分之一。 这意味着，每次将数字除以10000时，您将得到4个基数为10的数字。
第二，你如何选择除以10的幂？ 10,100,1000,10000等……
似乎有一个很好的选择，即10个最大功率可以适合你的字（32位）。 幸运的是，与两个“bigint”相比，你可以更有效地实现一个单词的除法/模数。
我还没有给出实现，因为我还在业余时间研究这个问题，因为我已经在我的库中实现了基本操作，I / O是下一步希望;）
除以适合您的基本类型的10的最大功率是最好的开始方式。 在你的情况下，这将除以10 ^ 9。 此代码应该是通用的，因为您可以将其重用为一般部门/模数代码的一部分。
运行时间将是O（n ^ 2）（即如果您的数字是两倍大，转换会说话的时间长四倍），但对于中等大小的数字，它应该足够快。
对于非常大的值，您将需要缓存10的大功率，比如10 ^ 1000,10 ^ 2000,10 ^ 4000,10 ^ 8000，….然后除以大于或等于10的幂。等于您尝试转换的数字的1/2。 重复此过程，直到数字足够小，使用除以10 ^ 9快速转换。 根据划分算法的效率，这种方法可能会更快，直到遇到超过一百万或更多的数字。
如果您正在编写一个交互式计算器，其中将显示每个数字，那么使用基数10 ^ 9将更快显示（它将是O（n），即如果您的数字是两倍大，转换将只需要两倍长）。
反复划分10的正常方式显然会非常缓慢。
一种显而易见的快速方法是使预先计算的bigint数组对应于每个位置中每个数字的值。 然后，您可以进行二进制搜索和相对便宜的比较/减法，以查找ms数字，然后依次查找每个数字。
当你到达最后的32位（或64位）时，你可以恢复到除以10。
我能想到的最有效的算法如下。 它应具有O（n·（log n）²·log log n）中的运行时复杂性，而不是具有二次运行时复杂性的朴素算法。
- 假设不失一般性，数字A是2 n + 1位长。 它可能有前导零。
- 如果这是最顶层的递归级别，则通过重复平方来计算数字2 2 i的最小值n的十进制表示。
- 将输入数字的比特序列分成两部分B和C.具有较低有效比特的部分C包括A的2 n个最低有效比特，而部分B是剩余的更高有效比特。
- 将B和C转换为十进制表示，如果它们足够短，则使用二次运行时算法，或者通过递归调用此算法。
- 将B的十进制表示乘以2 2 n的缓存十进制表示，并添加C的十进制表示以获得A的十进制表示。
在步骤2和5中，您需要一个十进制乘法算法。 对于具有数万个数字的数字，您应该使用在基数10中运行的Schönhage-Strassen算法版本。这将导致上述运行时复杂性。 对于较短的数字，根据其长度，应使用Toom-Cook算法，Karatsuba算法或长乘法。 但是，我目前无法告诉如何在基数10中实现Schönhage-Strassen算法，因为我能找到的所有完整描述都是针对基数2的，而我自己并不知道足够的数论来推导它。