Преобразуйте β-битное целое число в массив цифр, используя только O(lg β) умножения и деления

Question

(отредактировать: вопрос, дублирование которого мой вопрос был помечен, уже был связан в моем исходном сообщении, даже до пометки, и я не посчитал достаточным ответить на мой конкретный вопрос, почему возникла необходимость в достижении определенной сложности без любые предположения о неизвестной функции.)

Я пытаюсь решить упражнение в CLRS (Cormen Intro to Algorithms, 3ed). Упражнение гласит:

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

Этот вопрос был задан здесь и здесь. Однако ответы там либо делают неверные предположения, такие как M(β)=O(β), либо дают ответ, полностью игнорирующий то, что задает вопрос. В другом ответе здесь даже явно указывается результат Θ [M (β) lgβ], но объяснение довольно сложное, как если бы результат был очевиден:

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

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

Как я понимаю, вопрос состоит в том, что каждая операция умножения, частное и остаток занимает постоянное время M, которое доминирует во всех других видах операций, таких как сложение. Следовательно, доминантный член M (β) lgβ происходит просто от выполнения только умножений и делений lgβ.

Однако я не могу придумать ничего, что требует только деления lgβ. Например, если мы возьмем подсказку из вопроса, мы можем придумать следующий алгоритм "разделяй и властвуй" в псевдокоде.

decimal(x, start, end, n):
    digits = end - start + 1 // assume power of 2
    if digits == 1:
        x[start] = n // 1-based index
    else:
        t = 10^(digits/2) // assume negligible time
        quotient, remainder = n / t // takes M time
        decimal(x, start, start+digits/2-1, quotient)
        decimal(x, start+digits/2, end, remainder)

призвание decimal(x,1,d,n) на d-значном числе n со степенью 2 для простоты помещает десятичное представление в массиве size-d x. Предполагая, что линия quotient, remainder = n / t, занимает время M и доминирует над всем остальным во время выполнения, рекурсия времени выполнения T(β) = 2T(β/2) + M, которая имеет решение T(β) = Θ(βM), а не Θ(Mlgβ).

Правильно ли я понимаю вопрос? Если это так, как можно получить десятичное представление, используя только Θ(lgβ) умножения и / или деления?

На следующей странице очень известный пользователь Stackru обсуждает эту проблему. Особенно:

Binary -> Radix: двоичное преобразование -> radix то же самое, но в обратном порядке. Начните с N-значного числа X в базе 16. Вы хотите преобразовать его в M-значное число R в базе b. Вычислить: высокий = пол ( X / bM/2). Вычислить: низкий = X - bM/2 * высокий. Рекурсивно конвертировать низкие и высокие. Добавить результаты. Конечный результат R будет исходным числом, преобразованным в базу b.

Тем не менее, я до сих пор не понимаю, как это O (LG B) умножения; если вы выполняете рекурсию на обеих половинах, вы по определению посещаете каждый узел в дереве рекурсии, поэтому существует O(B) умножений!

на странице 55 из 239 "Современной компьютерной арифметики" Брента, которую можно увидеть здесь, также обсуждаются "субквадратичные алгоритмы" и упоминается алгоритм M (β) lgβ "разделяй и властвуй". Тем не менее, я до сих пор не знаю, откуда взялся lg β. Опять же, если вы разделяете и властвуете, и повторяете на обеих половинах, время выполнения будет по крайней мере линейным, а не логарифмическим! На странице 55 из 239 этой книги приведен следующий алгоритм (слегка перефразированный):

Algorithm 1.26 FastIntegerOutput
Input: A = (sum 0 to n-1) a_i 2^i
Output: a string S of characters, representing A in based 10
    if A < 10 then
        return char(A)
    else
        find k such that 10^(2k-2) <= A < 10^(2k)
        (Q, R) = DivRem(A, 10^k)
        r = FastIntegerOutput(R)
        return concatenate(FastIntegerOutput(Q), zeros(k-len(r)), r)

Брент утверждает:

Если на входе A есть n слов, алгоритм FastIntegerOutput имеет сложность O(M(n) log n)

но опять же, я не вижу, как это возможно, так как линия (Q, R) = DivRem(A, B^k) называется O (N) раз, а не O (LG N)?

Answer 1

Во-первых, чтобы убрать это с пути: то, о чем просит заголовок моего вопроса, сделать преобразование с логарифмическим числом делений и умножений, насколько я знаю, невозможно; и это было только предположение, которое я сделал, основываясь на неправильном понимании толкования вопроса.

Я переписывался с авторами учебника " Современная компьютерная арифметика", и они сказали, что алгоритм действительно вызывает деление β (β) раз, а не Θ (lg β), и на более глубоких рекурсивных уровнях M фактически действует на аргументы меньшего размера не на константе, на верхнем уровне β, как я неправильно предположил в своем вопросе. В частности, вызов верхнего уровня дерева имеет M(β/2), следующий уровень имеет 2M(β/4), затем 4M(β/8) и т. Д. Для общего количества уровней lg β. До тех пор, пока M(β) = Ω(β), суммирование деревьев будет O(M(β) lg β), хотя в общем случае не Ω(M(β) lgβ) и, следовательно, не Θ(M(β) lgβ). Например, для полинома M(β) = Θ(β^α) суммирование деревьев: Θ(β lg β) = Θ(M(β) lg β) для α = 1 и Θ(β^α) = Θ(M(β)) при α > 1.

Следовательно, если мы примем только M(β) = Ω(β), то время выполнения будет более точно описано как O(M(β) lg β), а не Θ (M (β) lg β), как в упражнении CLRS., (В моей переписке с одним из авторов "Современной компьютерной арифметики" они предположили, что CLRS означает "дать эффективный алгоритм", предполагающий, что M (β) является линейным или квазилинейным, но CLRS обычно довольно явно говорит о предположениях, которые мы предполагаем сделать, и "дать эффективный алгоритм" - это просто несколько общая фраза, которую они довольно часто используют в тексте для упражнений и задач, поэтому я чувствую, что это может быть незначительной опечаткой со стороны CLRS.

Обновление: я отправил это незначительное исправление на страницу с ошибками CLRS, и теперь оно вышло:

Стр. 933, Упражнение 31.1-13. Добавьте ограничение, что M(β) = Ω(β), и измените требуемую временную границу с Θ (M (β) lg β) на O(M(β) lg β). Об этом сообщает Дэвид Лю. Опубликовано 25 декабря 2017 г. Уровень серьезности: 3 Будет исправлено в восьмом печатном издании третьего издания.