Наивная арифметика: умножение

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

T*_M(m) = Q(m²), T*l_l(m₁,m₂)=Q(m₁m₂). (20.1)

Доказательство. Затраты наивного умножения a на b связаны с суммированием m, чисел n-i,n?,...,n_m , где каждое n_i равно 0 или a ■ 2ⁱ-¹ в зависимости от соответствующей цифры в двоичной запи­си b. Несложной индукцией доказывается, что для s_i = n_г + n₂ + ... ...+n_i, i = l,2,...,m₂, выполнено X{s_i)^m₁ + i. Если n_i+1ф0, то по­следние i цифр числа n_i+1 суть нули, и при вычислении s_i+1 = s_i + n_i+1 мы не притрагиваемся к этим цифрам, а преобразуем s_i в s_i+1 сло­жением двух чисел, первое из которых образовано всеми разрядами числа si, кроме i последних (согласно сказанному, битовая длина это­го числа не превосходит m_г), второе же слагаемое есть a, и его би­товая длина равна m_г. Число битовых операций, требующихся для преобразования s_i в s_i+1, не превосходит c{m_г +1) для некоторой по­ложительной константы c. В том случае, когда все цифры числа b равны 1, это число при любом i не меньше, чем m_ъ по лемме 19.1.

¹ См., например, книгу [50]. В литературе на английском языке, в частности в кни­ге [50], используется термин «word complexity».

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

Поэтому битовые затраты, связанные с наивным умножением а на Ъ, не превосходят с{т_г + 1)т₂, а при Ъ = 2^т? - 1 (двоичная запись это­го Ъ состоит только из единиц) затраты не меньше, чем т_гт₂. Это дает оценку Щ_1[{т_ът₂) = 6(m₁m₂).

Рассмотрим теперь т как размер входа. Так как т_г ^ т и т₂ ^ т,
то затраты не превосходят c(m + l)m, это дает оценку Т*_м(т) = 0(,т²).
С другой стороны, если т_г = т₂ = т и а = Ъ = 2^т - 1, то затраты не
могут быть меньше, чем т², и, следовательно, Г*(т) = Г2(т²). Таким
образом, Г_м*_м(т) = в (т²). □

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

S*_NM(m) = 2т + 0(1), S^Qn_lt т₂) = т_г + т₂ + 0(1).

Обсудим переход от параметров т_ъ т₂ размера входа к парамет­рам а, Ъ (можно считать, что и к параметрам logo, logЪ—между а, Ъ и log a, log Ъ в этом смысле нет принципиальной разницы, так как одни параметры однозначно определяют другие; в то же время мы не можем восстановить а,Ъ по riog₂(a + l)l, [log₂(b +1)1).

Для перехода в верхних оценках сложности от A(fc) к log₂ к, fee gN*, часто оказывается удобным простое неравенство |"log₂(fc + 1)] ^ ^ 2 log₂ к, справедливое для всех к ^ 2:

[log₂(fc + 1)1 = Llog₂ fcj + 1 ^ log₂ к+ 1^2 log₂ к.

Поэтому, например,

т₁ ^ 2 log₂ a, m₂ ^ 2 log₂ b

и

т_гт₂^ 4 log₂ a log₂b (20.2)

для всех a, b ^ 2. Имеем для достаточно больших т_ъ т₂ и некоторой положительной константы с

Cl_u{a, Ъ) s= Т^_Л{т_ъ т₂) s= ст_гт₂ s= Ac log₂ a log₂ Ъ.

Мы можем написать C^_M(a, b) = 0(loga logb), считая, что выражение под знаком О рассматривается как функция двух переменных а, Ъ, при этом а, Ь—>оо; считаем также, что логарифмы имеют общее ос­нование (подобные предположения будут подразумеваться и в даль­нейшем). Остается заметить, что битовая временная сложность при использовании самих а, Ъ в качестве параметров размера входа сов­падает с битовыми временными затратами. Это позволяет получить из оценки Т**_м(.т_ът₂) = 0(.т₁т₂) оценку T_NM(a, Ь) = О (log a logb) для

§ 20. Наивная арифметика: умножение

временной битовой сложности при использовании двух параметров размера входа a, b. Итак:

При использовании самих положительных целых a,b в качестве параметров размера входа сложность наивного умножения a на b по числу битовых операций допускает оценку O(logalogb).

Выше наивное умножение (умножение «столбиком») понималось так, что если какая-то цифра числа b равна нулю, то, несмотря на это, построение соответствующих n_i и s_i требует не менее m_г би­товых операций. При таком взгляде сложность будет величиной 6(loga log b). Но можно считать, что в рассматриваемом случае бито­вые затраты на получение s_i не зависят от a и ограничены констан­той. Тогда оценка n(logalogb) места не имеет: если a = 2^k\b = 2^k, где k_г,k₂—положительные целые, то битовые затраты будут ограни­чены линейной функцией от k_ъ k₂.

Пример 20.1.Покажем, что битовая временная сложность алго­ритма вычисления n\с помощью пошаговых наивных умножений

2-3, (2-3)-4, ..., (2-3...(n-1))-n

при использовании n в качестве размера входа допускает верхнюю оценку O((n logn)²). В силу предложения 20.1 и неравенства (20.2) рассматриваемая сложность не превосходит cf{n), где c — некоторая положительная константа, а значение f(n) равно

log₂ 2 log₂ 3 + log₂(2 •3) log₂ 4 + ... + log₂(2 •3... (n - 1)) log₂ n.

Имеем

f(n) s=log₂(2 •3... (n - l))(log₂ 2 + log₂ 3 + ... + log₂ n) s=log²(n!).

Одним из следствий формулы Стирлинга является оценка log₂(n!) = = O(n log n), откуда log²(n!) = O((n log n)²), иf(n) = O((n log n)²).

Пример 20.2.Мы упоминали о том, что для алгоритма, входом которого является несколько целых чисел, можно в некоторых случа­ях определять размер входа как суммарную битовую длину всех этих чисел. Предположим, что имеется несколько целых чисел a_г, a₂, •••, a_n, каждое из которых ^ 2, и с помощью пошаговых наивных умножений

a_гa₂, {a_гa₂)a^ ..., {a_гa₂...a_n-_г)a_n (20.3)

вычисляется произведение A = a_гa₂...a_n. Пусть суммарная битовая длина чисел равна M, и число M рассматривается как размер вхо­да алгоритма (20.3). Покажем, что тогда битовая сложность этого

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

алгоритма допускает верхнюю оценку O{M²), — примечательно, что число n, т. е. общее количество сомножителей, в этой оценке не по­является.

В силу предложения 20.1 и неравенства (20.2) битовые затраты на вычисление a_ъa₂, ■■■a_n не превосходит cF{a_г,a₂, ...,a_n), где c—неко­торая положительная константа, а значение F{a_г, a₂,..., a_n) равно

log₂ a_г log₂ a₂ + log₂(a_ia₂) log₂ a₃ + ... + log₂(a₁a₂...a_n_₁) log₂ a_n

(использовано предположение, что a_ъa₂,..., a_n ^ 2). Мы легко полу­чаем

F(a_ъ a₂,...,a_n) s= log₂(a₁...a_n_₁)aog₂ a₂ + ... + log₂ an)

и

F{a_ъ a₂,..., an) s= (log₂ a_г + log₂ a₂ + ... + log₂ a_n)².

Последнее неравенство позволяет перейти к рассмотрению M в ка­честве размера входа, так как, очевидно,

F(a₁,a₂,...,a_n)^(riog₂(a₁ + l)l + riog₂(a₂ + l)l+...+ riog₂(a_n + l)l)2 =M 2 ,

что дает нам требуемое.

Доказанное утверждение справедливо и в том случае, когда сре­ди a_г,a₂, ...,a_n имеются единицы, если считать, что умножение на 1 требует одной битовой операции. Если среди a_ъa₂,...,a_n имеются k единиц, то из M ^ k следует (M - k)² + k s= M².