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

139

временной битовой сложности при использовании двух параметров размера входа 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). Покажем, что тогда битовая сложность этого

140

Глава 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².