Вычислительная сложность преобразования базы

Question

Какова сложность преобразования очень большого n-битного числа в десятичное представление?

Я думаю, что элементарный алгоритм повторного целочисленного деления, принимая остаток для получения каждой цифры, будет иметь O(M(n)log n) сложность, где M(n) сложность алгоритма умножения; однако деление происходит не между 2 n-разрядными числами, а с 1 n-разрядным числом и небольшим постоянным числом, поэтому мне кажется, что сложность может быть меньше.

Answer 1

Наивное базовое преобразование, как вы описали, занимает квадратичное время; ты о n деления bigint-by-smallint, большинство из которых занимают время, линейное по размеру n-битного bigint.

Однако вы можете выполнить базовое преобразование за время O(M(n) log(n)), выбрав степень целевого основания, примерно равную квадратному корню от числа, которое должно быть преобразовано, выполнив деление-остаток это (что может быть сделано за время O(M(n)) с помощью метода Ньютона) и повторяется на двух половинах.