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

Обратимся к наивному делению с остатком. Здесь мы считаем, что 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. Наивная арифметика: деление с остатком

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

Оценка T*_D (т) = 0{т²) следует теперь из неравенства т² ^т_гт₂ ^
^{т_г-т₂ + 1)т₂. Если взять а = 2^т-1, b = 2^{L m/ 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 (log a log b) при а, Ь—><*>, а^Ъ. Отсюда
следует первая часть утверждения. Вторая часть следует из того, что
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₂ п), поэтому оценка для

Глава 5. Битовая сложность

затрат переписывается в виде О (log² п); при указанных выше размерах входа эта оценка является и оценкой сложности.

Вновь вернемся к обозначению т для битовой длины максималь­ного из двух данных целых положительных чисел, и пусть т рас­сматривается как размер входа а, Ъ алгоритмов умножения и деления с остатком. Для сложностей наивного умножения и деления мы по­лучили оценки 6(т²), следствием которых являются нижние оценки Г2(т²). Вместе с этим, для умножения и деления известны алгорит­мы, сложности которых при т —> ∞ растут существенно медленнее, чем т²: первый алгоритм такого рода для умножения был предложен в 1962 г. А. А. Карацубой (верхняя оценка 0(m ^lo&³)), наилучшую из известных к настоящему времени верхнюю асимптотическую оценку битовой сложности О (т log т log log m) имеет алгоритм А.Шенхаге и Ф. Штрассена. Существуют алгоритмы деления, сложность которых допускает такие же оценки (см. задачу 152 к главе 7). Алгоритм Кара-цубы будет рассмотрен нами в § 27, алгоритм Шенхаге—Штрассена в этом курсе подробно не рассматривается; несколько слов о нем бу­дет сказано в конце § 27.

Пример 21.2. Исследуем битовую сложность алгоритма Евклида. В качестве размера входа можно рассмотреть большее число а₀, но ни в коем случае не а_г: если фиксировано а_ъ то, неограниченно уве­личивая а₀, мы будем неограниченно увеличивать битовые затраты, связанные с первым делением с остатком (а₀ на а_г). Поэтому при вы­боре а_г в качестве размера входа битовая сложность этого алгоритма тождественно равна бесконечности — здесь битовая сложность суще­ственно отличается от алгебраической (т. е. в данном случае от слож­ности по числу делений). Можно считать а₀ размером входа, а можно рассмотреть два параметра а₀,а_г размера входа. Если т₀,т_г — бито­вые длины данных чисел а₀, а_ъ то в качестве размера входа мож­но рассмотреть т = max{ m ₀, т_г} = т₀ или же два параметра входа т₀,т_г. В настоящем примере мы будем использовать т.

Прежде всего покажем, что для алгоритма Евклида

a;-i = q; a; + a_{i +1}, i = l,2,..., n, a_{n +1} = 0,

выполняется

a₀^ q₁q₂...q_n. (21.2)

В самом деле,

a₀>q₁a₁, a₁>q₂a₂,..., a_n-₂ > q_n-ian-i> an-i = 4nan>

и получаем a₀ ^ q₁q₂...q_na_n, откуда следует (21.2).

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

Для построения a_i+1 делением a_i __х на a_i с остатком требуется не более c (Llog₂ q_i\ + l)(Llog₂ a_i\ + 2) битовых операций, где c —положи­тельная константа. Это дает общую оценку сверху

^CLlog₂ q_i J +l)(Llog₂ a_i J +2),

c

i =1

при этом возможно, что некоторые из q_i равны единице. Написанная сумма не превосходит

c (Llog₂ a_г] + 2) ^ (Uog₂ q_i} + 1).

i=l

При a₁>1 выполнено |_log₂ a_г] + 2 sj 3 log₂ a_г и, как следствие, c (Llog₂ a_г\ + 1) j^(Uog₂ q_i\ + 2) s= 3 c (log₂ a _l) fn + J] log₂ q_i =

i=l i=l

= 3 c (log₂ a _i)(n + log₂(q i q ₂... q_n)) < 3 c (log₂ a _i)(n + log₂ a ₀). Как мы знаем, n ^ 2 log₂ a _x + 1; при a _x > 1, очевидно, можем на­писать n ^31og₂ a ₁. Это дает нам оценку сверху

3c(log₂a₁)(3log₂a₁+log₂a₀)

для числа битовых операций при a_г > 1. Учитывая, что a₀^a_ъ мы получаем отсюда следующее.

Количество битовых операций, затрачиваемых при применении алгоритма Евклида к a₀, a_ь допускает оценку

O (log a ₀log a _i) (21.3)

и оценки O (log² a ₀), O{m²), m = A(a ₀).

Приведенные оценки получены в предположении, что для построе­ния остатков используется наивное деление, имеющее квадратичную сложность. Может ли быть так, что привлечение имеющего меньшую битовую сложность алгоритма деления с остатком приведет к суще­ственно меньшим битовым затратам алгоритма Евклида? Ответ отри­цательный: нетрудно, например, показать, что если a₀ берется в ка­честве размера входа, то для битовой сложности алгоритма Евклида выполняется оценка n(log² a ₀).

В самом деле, в примере 10.1 было показано, что для каждо­го a₀ можно подобрать меньшее его a_г такое, что для числа делений с остатком выполняется неравенство (10.10). Если обозначить это чис­ло делений через n, то будем иметь n = n(log a ₀), при этом

A(a ₀),A(a ₁),...,A(an)

Глава 5. Битовая сложность

является невозрастающей конечной последовательностью натураль­ных чисел, и в силу предложения 9.1 никакое значение не встречается в ней более двух раз. Так как деление с остатком a_i _ _г на a_i требует не менее А(a_i) битовых операций, то общее число битовых опера­ций не может быть меньше, чем 1+ 1+ 2 + 2 +...+ k + k = k (. k + 1) при k= [ ⁿ ^\ и n = n(log a ₀). Следовательно, общее число битовых

операций есть ft(log² a ₀).

Вместе с ранее установленной оценкой O (log² a ₀) это дает оценку в (log² a ₀). Теорема 4.2 из § 4 приводит нас к оценке в(m ²) для бито­вой сложности алгоритма Евклида при избрании битовой длины m числа a₀ в качестве размера входа. Итак:

Если алгоритм Евклида основывается на некотором алгоритме де­ления с остатком, битовые затраты которого применительно к де­лимому v и делителю w допускают верхнюю оценку O (log v log w), то при рассмотрении большего входного числа a₀ в качестве разме­ра входа битовая сложность алгоритма Евклида допускает оценку 6(log² a ₀). При рассмотрении m = А(a ₀) в качестве размера входа име­ем оценку в(m ²).

Оказывается, что полученные оценки сохраняют силу и при рас­смотрении расширенного алгоритма Евклида (пример 9.1)—обсто­ятельство, имеющее большое значение для модулярной арифметики (§ 22).

Предложение 21.3. Пусть расширенный алгоритм Евклида осно­вывается на некоторых алгоритмах деления с остатком и умноже­ния, битовые затраты каждого из которых применительно к целым v иw допускают верхнюю оценку O (log v log w). Тогда, при рассмот­рении большего входного числа a₀ в качестве размера входа, бито­вая сложность расширенного алгоритма Евклида допускает оценку e(log² a ₀), а при рассмотрении битовой длины m большего числа a₀ в качестве размера входа —оценку в(m ²).

Доказательство. Исходя из вычислительных формул (9.8) и при­
нимая во внимание (9.12), (9.13), мы заключаем, что битовые за­
траты, дополнительные к затратам собственно алгоритма Евкли­
да («нерасширенного») на вычисление s_n, t_n, допускают оценку
O (log a ₀log a _i)—это обосновывается так же, как оценка (21.3). По­
этому сложность добавочной части расширенного алгоритма Евкли­
да допускает оценку O (log² a ₀) и, в силу теоремы 4.2, оценку O{m²).
Остается заметить, что, например, в(m ²) + O{m²) = в(m ²). □

§ 22. Модулярная арифметика

Дата добавления: 2014-01-11