Эффективный алгоритм для преобразования целого числа в десятичное

Question

Задача 31.1-12 из книги алгоритмов CLRS задает следующий вопрос:

Дайте эффективный алгоритм для преобразования данного β-битное (двоичное) целое число в десятичном представлении. Утверждают, что если умножение или деление целых чисел, длина которых не более β занимает много времени M(β), то двоичное в десятичное преобразование может быть выполнено во времени Θ( M(β) lg β), (Подсказка: используйте подход "разделяй и властвуй", получая верхнюю и нижнюю половины результата с отдельными рекурсиями.

Это требует времени Θ( M(β) lg β), Как это вообще возможно для алгоритма "разделяй и властвуй", если lg β одна высота дерева рекурсии? Кто-нибудь знает, что это за решение?

Answer 1

Чтобы подсказка сработала, должен быть случай, когда M (β) является линейной функцией; в частности, что M(β) ≈ 2·M(β/2).

Если это дано, есть очевидное решение: рекурсивно разбить данные на части, обработать части по отдельности и объединить результаты. На уровне k рекурсии будет 2ᵏ части, каждая из которых имеет длину приблизительно β/(2,) битов или около β total. Обработка на уровне k стоит 2ᵏ·M(β/(2ᵏ)) ≈ M(β), откуда O(M(β)·lg β) общее время.

Чтобы разделить значение u битами β и обработать его две части (v, w), пусть 2 · d или 2·d+1 = ⌊β·ln(2)/ln(10)⌋; пусть v = ⌊u/10ᵈ⌋ и w = uv·10ᵈ.