如何使用FFT将非常大的整数从一个基数/基数转换为另一个基数/基数? [英] How can I convert a very large integer from one base/radix to another using FFT?
问题描述
是否存在已知的算法，该算法会采用以一个基数/基数编码的具有 n 个数字的大整数，并将其转换为另一个任意基数? (比方说，从7到19). n 可能真的很大，例如超过100个数字，因此我正在寻找比O( n 2 )运行时间.
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.
我已经看到一些算法，可以使用快速傅立叶变换(FFT)将两个大整数相乘，其理论复杂度为O( n log n )，其中 n 是位数，所以我想知道是否存在类似的基数/基数转换?
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?
推荐答案
我自己并不熟悉该主题，但是这里的页面提示如何比单纯的余数更快地进行基数转换.除法算法:
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:
页面提示您需要一种快速的分治法除法，而反过来又需要一种快速的乘法算法(Karatsuba，Toom-Cook，FFT等).
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.).
这篇关于如何使用FFT将非常大的整数从一个基数/基数转换为另一个基数/基数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
