1.3. Золотое правило разработчиков алгоритмов

Теперь рассмотрим для примера простую задачу, которая известна всем еще с начальной школы, а также метод решения этой задачи - умножение двух чисел. Эту задачу можно описать следующим образом:
Вход: 2 целых n-разрядных числа x и y
Выход: произведение чисел x · y
Рассмотрим пример для чисел x = 5678 и y = 1234. Результат известного с детства метода умножения в столбик будет выглядеть следующим образом:

Легко заметить, что элементарные операции, которые здесь используются, это - умножение и добавления одноразрядных чисел. Предположив, что операция умножения занимает больше времени чем операция сложения для одной пары чисел, оценим количество таких элементарных операций. Все они выполняется в области, выше обозначена серым цветом. В данном примере количество элементарных операций произведения составит 16 = 4², А в общем случае составит n². Поэтому, количество операций для произведения двух целых n-разрядных чисел методом умножения в столбик оценивается как cn², Где c - некоторая константа.

Однако можем ли мы улучшить этот результат, получив метод произведения чисел, который будет работать быстрее? Чтобы мотивировать себя для поиска такого метода, приведем цитату из книги «Разработка и анализ компьютерных алгоритмов» (Аго, Гопкрофт, Ульман, 1974): «Возможно наиболее важным принципом для хорошего разработчика алгоритмов является отказ от того, чтобы быть довольным результатом ». Следуя этому правилу, рассмотрим еще раз подробнее природу объектов задачи произведения чисел.

По условию на вход подается два n-разрядных числа. Допустим мы разобьем каждое число пополам, получив так называемые верхнее и нижнее полуслова. То есть, можно записать , Где a, b, c, d - целые n / 2-разрядные числа. Тогда произведение x · y можно представить так:

Таким образом мы естественно подошли к рекурсивного метода вычисления произведения двух целых чисел, который сводит расчет произведения двух n-разрядных чисел к расчету четырех произведений n / 2-разрядных чисел. Попробуем выяснить, улучшится таким образом скорость произведения двух чисел. Каждое из чисел a, b, c, d имеют n / 2 разрядов, а затем произведение любой их пары (если использовать для него старый алгоритм умножения в столбик) занимать c (n / 2)² операций, то есть cn²/ 4. Четыре таких произведения в сумме снова дадут начальный результат: 4 · cn²/ 4 = cn². Итак, выигрыш по времени не было получено.

Неужели нельзя улучшить результат работы метода умножения чисел в столбик? На самом деле, возможно и ответом на этот вопрос является метод умножения Карацубы (1960). Если посмотреть на формулу (1.1), то заметим, что на самом деле важны не четыре произведения, а три: ac, bd и (ad + bc), то есть элементы ad и bc нас не интересуют сами по себе, а только их сумма. Можно получить их сумму умножив только два числа? Так:

Таким образом, сумму (ad + bc) можно получить из произведения двух n / 2-разрядных числа (Возможно, n / 2 + 1) (a + b) и (c + d), а также произведений ac и bd, которые мы уже имеем. И, следовательно, количество рекурсивных вызовов сократились с четырех до трех. Анализ скорости метода умножения Карацубы приводит к оценке 3n^log₂3≈3n^1,585.

Этот пример красноречиво свидетельствует, что пространство для движения разработчика алгоритмов является намного больше чем может казаться поначалу.