如何使用 FFT 将非常大的整数从一个基数/基数转换为另一个基数/基数？
是否有已知的算法可以采用一个基数/基数编码的 n 位大整数并将其转换为另一个任意基数？ （假设从基数 7 到基数 19。）n 可能非常大，比如超过 100 000 位数字，所以我正在寻找比 O(n 2) 运行时间。
我见过一些算法可以使用快速傅立叶变换 (FFT) 将两个大整数相乘，其理论复杂度为 O(n log n)，其中 n 是位数，所以我想知道基数/基数转换是否存在类似的东西？
Are there known algorithms which will take a big integer with n digits encoded in one base/radix and convert it to another arbitrary base? (Let's say from base 7 to base 19.) n can be really big, like more than 100 000 digits, so I am looking for something better than O(n2) run time.
I have seen some algorithms that can multiply two huge integers using the Fast Fourier Transform (FFT), with the theoretical complexity of O(n log n), where n is the number of digits, so I wonder if something similar exists for bases/radix conversion?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我自己不太熟悉这个主题，但这里有一个页面提示如何比简单的余数除法算法更快地进行基数转换：
该页面提示您需要一个快速的分治除法算法，而这又需要一个快速的分治算法乘法算法（Karatsuba、Toom-Cook、FFT 等）。
I'm not well versed on the topic myself, but here's a page that hints at how to do radix conversion a bit faster than the naive remainder-and-divide algorithm:
The page hints that you need a fast divide-and-conquer division algorithm, which in turn needs a fast multiplication algorithm (Karatsuba, Toom-Cook, FFT, etc.).