Как я могу преобразовать очень большое целое число из одной базы / основание в другое, используя FFT?

Question

Существуют ли известные алгоритмы, которые будут принимать большое целое число с n цифрами, закодированными в одну базу / основание, и преобразовывать его в другую произвольную базу? (Допустим, от базы 7 до базы 19.) n может быть очень большим, например, более 100 000 цифр, поэтому я ищу что-то лучше, чем O ( n ² ) время выполнения.

Я видел некоторые алгоритмы, которые могут умножать два огромных целых числа, используя быстрое преобразование Фурье (БПФ), с теоретической сложностью O ( n log n ), где n это количество цифр, так что мне интересно, существует ли что-то подобное для преобразования базис / основание?

Answer 1

Я сам не очень разбираюсь в этой теме, но вот страница, которая намекает на то, как сделать радикальное преобразование немного быстрее, чем наивный алгоритм деления и деления:

• GNU MP - Binary to Radix

На странице указывается, что вам нужен быстрый алгоритм деления и завоевания, который, в свою очередь, нуждается в быстром алгоритме умножения (Karatsuba, Toom-Cook,БПФ и др.).