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

Question

我有一个基数为n(无符号)的整数，长度为数十万个字符。

如何将这个数字(从文件中读取的字符串)转换为2-256之间的任意基数？当然是在合理的时间内。

GMP文库仅支持碱基2-62。

Answer 1

GMP对非常大的整数使用a clever divide-and-conquer radix change algorithm。

使用相同的基本概念来做一些事情并不难。将基数r和输入数字x命名为。

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

这比一次提取一个数字要高效得多，因为我们将一个k-bit数减少为两个粗略的k/2-bit数，而不是一个log(r)-bit数和一个k-log(r)-bit数。