§ 21. Наивная арифметика: деление с остатком

Обратимся к наивному делению с остатком. Здесь мы считаем, что m = m_г^ m₂.

Предложение 21.1. Пусть T*_D(m) — сложность по числу битовых операций наивного деления при использовании m в качестве разме­ра входа. Пусть T*^(m_ъ m₂)— сложность по числу битовых операций этого же алгоритма при использовании m_ъ m₂ в качестве двух пара­метров размера входа. Тогда

T*_D(m) = Q(m²), T^*(m₁,m₂) = e((m₁-m₂ + l)m₂). (21.1)

Доказательство. Наивное деление a на b сводится к ряду вы­читаний числа b, и в каждом вычитании битовая длина уменьша­емого либо равна, либо на единицу превосходит m₂. Битовые затра­ты на каждое такое вычитание не могут превзойти, как мы зна­ем, c{m₂ + 1). Количество всех таких вычитаний не превосходит m_г-m₂ + 1, откуда T^* {m_ъm₂) = O{{m_г - m₂ + 1)(m₂ + 1)) и, после

§ 21. Наивная арифметика: деление с остатком

141

упрощения, Т^(т_1г т₂) = 0{{т_г -т₂ + 1)т₂) (см. задачу 101). С дру­гой стороны, если, например, а = 2™¹ - 1, Ъ = 2'"²-¹, то число вы­читаний равно т_г-т₂ + 1, и, как следствие, битовые затраты на наивное деление будут не меньше, чем {т_г - т₂ + 1)т₂. Поэтому Т**₀(.т_ъ т₂) = GCCni! - т₂ + 1)т₂).

Оценка T*_D(т) = 0{т²) следует теперь из неравенства т² ^т_гт₂ ^ ^{т_г-т₂ + 1)т₂. Если взять а = 2^т-1, b = 2^Lm/2J, то битовые затра- ты на наивное деление будут не меньше чем (т-у+1](тМ+1], и, как следствие, 7^_D(m) = Г2(т²). Получаем 7^_D(m) = 6(т²). П

Мы не пишем Т*£(т_ъ т₂) = Gt^ - т₂)т₂) из-за возможности ра­венства т_г = т₂ (из которого не следует, что а = Ъ). Эта возможность указывает и на то, что неверно соотношение T^_l{m₁,m₂) = Q{m₁m₂).

Предложение 21.2. При использовании самих положительных це­лых а,Ъ, а^Ъ>1, в качестве параметров размера входа, сложность наивного деления а на Ъ допускает оценку О (log a log Ь). При исполь­зовании а в качестве размера входа имеем оценку О (log² а).

Доказательство. Как уже говорилось, число битовых операций, требуемых наивным умножением, не превосходит произведения

c((Uog₂ а] + 1) - (Llog₂ Ъ\ + 1) + 1) (Llog₂ Ъ\ + 1)

(с — положительная константа), которое не превосходит в свою оче­редь

c(log₂ а - log₂ Ъ + 2)(log₂ Ъ + 1).

Каждое слагаемое, возникающее в результате раскрытия скобок в по­ следнем выражении, есть O(logalogb) при а, Ь—><*>, а^Ъ. Отсюда следует первая часть утверждения. Вторая часть следует из того, что log₂ a log₂ Ъ s= log² а при а ^ Ъ. □

Пример 21.1. Пусть пик — положительные целые числа, к ^ 2, заданные в двоичной системе счисления. Покажем, что при избра­нии п в качестве размера входа п, к (равно как и при избрании п, к в качестве двух параметров размера этого входа) битовая сложность обычного алгоритма построения fc-ичной записи числа п с помощью наивных делений с остатком допускает оценку О (log² п).

В самом деле, при построении fc-ичной записи п шаг за шагом рас-сматриваются числа q₀,<li, ...,q_t, t= |_log_fc n\ + 1, где q₀ = n,q_t= -^-- , i = 1, 2,..., t. Очевидно, что q_t s= n, в силу чего общие затраты всех ша­гов для данных пик допускают оценку О (log п log к log_fc п). Очевидно, log к log_fc п = log п (например, log₂ к log_fc п = log₂ п), поэтому оценка для

142