如何将任意大整数从任意基数转换为不同的基数？

Question

我有一个长度为数十万个字符的 base-n（无符号）整数。

如何将此数字（从文件中读取的字符串）转换为 2-256 之间的任何基数？当然是在合理的时间。

GMP 库仅支持碱基 2-62。

Answer 1

GMP对真正的大整数使用巧妙的分而治之的基数变化算法。

使用相同的基本思想做一些事情并不难。调用您的基数r和输入数字x。

让rp[i] = r^(2^i)每个iup 直到rp[i]大约是原始数字位数的一半；打电话给最后一位rp[n-1]。减少您的数字模数rp[n-1]。然后高2^(n-1)基数r是x / rp[n-1]转换为r基数r的那些，低基数是x % rp[n-1]转换为基数的基数r。请注意，您只需计算rp一次。

这比一次提取一个数字更有效，因为我们将一个k-bit 数减少到两个大致的k/2-bit 数，而不是一个log(r)-bit 数和一个k-log(r)-bit 数。