我有一个数十万字符长的以 n 为底的（无符号）整数。
如何将此数字（从文件中读取的字符串）转换为 2-256 之间的任何基数？当然是在合理的时间内。
GMP 库仅支持碱基 2-62。
问问题
536 次
1 回答
5
GMP 对非常大的整数使用聪明的分治基数变化算法。
使用相同的基本思想做一些事情并不难。调用您的基数r和输入的数字x。
让rp[i] = r^(2^i)每个i直到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为两个大致k/2位数，而不是一个log(r)位数和一个k-log(r)位数。
于 2013-11-10T21:15:42.583 回答