如何使用FFT將一個非常大的整數從一個基數/基數轉換爲另一個基數/基數？

Question

是否有已知的算法，將採取一個大整數n數字編碼在一個基地/基數，並將其轉換爲另一個任意基地？ （比方說，從基地7至19基地）ñ可真大，像100多  000位，所以我要尋找爲O運行更好的東西（ñ ）時間。

我已經看到了一些算法，可以使用快速傅立葉變換（FFT），兩個巨大的整數相乘，帶O的理論複雜性（ñ日誌ñ），其中ñ是數字的號碼，所以我想知道鹼基/基數轉換是否存在類似的情況？

Answer 1

我沒有很好的話題熟悉自己，但這裏有一個暗示怎麼辦基數轉換比幼稚餘和除法算法快一點的頁面：

• GNU MP - Binary to Radix

該頁面提示您需要一個快速分而治之劃分算法，而該算法又需要快速乘法算法（Karatsuba，Toom-Cook，FFT等）。