什么是将bignum类型结构转换为可读字符串的有效方法?

首先,如果没有基本的操作(例如除法和模),就无法以合理的方式进行I/O。为了提供将bigint转换为base-10字符串的有效实现,我正在研究两种可能的优化:

首先,你可以除以10的幂,而不是精确的10。这意味着,你将得到四个基数10位数,每次你除以10000举例来说。

第二,你将如何选择10的哪一个幂?10、100、1000、10000等等。。。
似乎有一个很好的选择,它是10的最大权力,可以在您的字(32位)。幸运的是,用一个单词实现除法/模比用两个“bigint”更有效。

除以适合你的基本类型的10的最大幂是最好的开始方式。在你的情况下,这将是除以10^9。此代码应该是通用的,因为您可以将其重用为通用除法/模代码的一部分。

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

如果您正在编写一个交互式计算器,其中将显示每个数字,那么使用基数10^9将更快地显示(它将是O(n),即,如果您的数字是原来的两倍,则转换只需要两倍的时间)。

当你回到最后32位(或64位)时,你可以恢复到除法10。

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

1. 假定A是2而不失一般性 ^n+1个
2. ² 如果这是最顶层的递归级别,则通过重复平方将i提升到n。
3. 将输入数字的位序列分为B和C两部分。具有较低有效位的部分C包括2 A的最低有效位,而B部分是剩余的更高有效位。
4. 使用 二次运行时算法,如果它们足够短,或者通过递归调用此算法。
5. 将B的十进制表示形式乘以缓存的十进制表示形式2 ⁿ 再加上C的十进制表示,得到A的十进制表示。