Глава 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. Наивная арифметика: деление с остатком

143

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

^CLlog₂ q_iJ +l)(Llog₂ a_iJ +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= 3c(log₂ a_l) fn + J] log₂ q_i =

i=l i=l

= 3c(log₂ a_i)(n + log₂(qiq₂...q_n)) < 3c(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(loga₀loga_i) (21.3)

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

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

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

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

144