Обычный способ «в столбик», известный многие столетия, выглядит для нас самым быстрым. Наверное, мы просто не представляем, что числа можно перемножать как‑то иначе.
Но, оказывается, существуют и другие методы умножения, и куда более эффективные!
В этой статье мы обсудим один из таких методов, обнаруженный в 1962 году московским математиком Анатолием Александровичем Карацубой (тогда 25‑летним молодым ассистентом, а сейчас он профессор МГУ). Сначала теоретически, «на листе бумаги» оценим привычный способ умножения и новый метод, а затем экспериментально, написав программы, проверим теорию на практике.
1. Оцениваем сложность алгоритма умножения «в столбик»
Не будем детально разбирать всем знакомый школьный (стандартный, классический, обычный) алгоритм умножения столбиком, а сразу оценим его временную сложность, то есть необходимое для его реализации число «элементарных операций».
Рассмотрим такой пример:
Здесь мы совершили 4*4=36 элементарных умножений (каждая цифра одного числа провзаимодействовала с каждой цифрой другого числа) и некоторое количество сдвигов и сложений.
Вообще, если мы перемножаем столбиком n‑значные числа, то нужно произвести n2 элементарных умножений, а сдвигов и сложений заведомо не больше по порядку n2, то есть основную нагрузку несут именно элементарные умножения. Поэтому можно указать такую константу C1, отражающую количество сложений и сдвигов, что сложность алгоритма T(n)£C1n2 для любого n.
Точной зависимости T(n) мы не нашли, но указали её оценку. Так обычно и поступают для конкретного алгоритма или программы, ведь нахождение точной зависимости – задача непростая. А хорошая оценка даёт достаточное представление о сложности алгоритма.
2. Открываем алгоритм Карацубы
В основе нового метода лежит такой фундаментальный принцип, как «разделяй и властвуй» ("divide and conquer"), на котором построены сотни различных быстрых алгоритмов (вспомним хотя бы сортировки или динамическое программирование). Задачу разбивают на части, находят их решение, а затем получают решение всей задачи. Этот приём часто эффективен, особенно если его применять рекурсивно.
Итак, «разделяем». Заметим, чтобы стандартно перемножить два 2n‑значных числа, нужно сделать 4 умножения n‑значных чисел плюс сдвиги и сложения.
Пусть x и y – 2n‑значные числа. Мы можем представить их, как x = a × 10n + b и y = c × 10n + d, где a, b, c, d – n‑значные числа (например, 9036=90*102+36), и тогда произведение
(S)
Действительно, 4 умножения: a × c, a × d, b × c и b × d. И формула (S) – это всё тот же школьный способ умножения столбиком, только в системе счисления с основанием 10n.
«Властвуем». Но сделаем ещё один шаг в преобразованиях, который и приведёт к методу Карацубы. Простой приём – используем произведения, которые уже вычислили. Для этого заменяем число a × d + b × c на равное ему (a + b) × (c + d) – a × c – b × d . В результате
(K)
И у нас уже только 3 умножения: a × c, b × d и (a + b) × (c + d)! Хотя на три операции сложения‑вычитания больше.
Вот здесь мы и выигрываем соревнование с обычным способом – за счет замены «трудоемкой» операции умножения фиксированным числом операций сложения‑вычитания. Ведь, начиная с достаточно больших n, умножение n‑значных чисел требует всё больше времени, чем любое фиксированное число n‑разрядных сложений или вычитаний, разница во времени становится настолько значительной, что мы практически экономим операцию умножения.
Казалось бы, при уменьшении числа произведений n‑значных чисел с четырех до трех выигрыш во времени – в лучшем случае всего 25%.
Но естественно продолжить гонку, то есть полученные три произведения найти таким же образом, свести их вычисление к девяти произведениям, снова сэкономить 25% времени, и т. д. В результате выигрыши на каждом шаге объединяются и дают асимптотическое улучшение временной сложности. Таким образом, мы получаем рекурсивный метод умножения больших целых чисел.
3. Приводим пример и учитываем некоторые особенности алгоритма
Наглядно процесс умножения по Карацубе представляется в виде дерева рекурсивных вызовов. На входе в рекурсию произведение двух «длинных» чисел порождает вычисление трех произведений «коротких» чисел, каждое из которых – ещё по три произведения, и так до произведений однозначных чисел. «Последние» произведения вычисляются обычным способом, а затем на выходе из рекурсии по формуле (K) «собираются» произведения более высоких уровней до искомого произведения в вершине.
Перемножим, например, числа 9036 и 9744. Конечно, на таких небольших числах мы не почувствуем эффективность нового метода, но ещё раз разберёмся с его логикой и выделим некоторые особенности.
Строим дерево рекурсивных вызовов:
(график)
И здесь могут возникнуть две проблемы, объединённые общим вопросом «а как же дальше продолжить использование метода?»
1. Длины перемножаемых чисел оказались нечетными. Тогда длины «левых» частей (a и c) берём на единицу больше. Очевидно, формула (K) по прежнему верна, и в качестве n будет общая длина «правых» частей (b и d).
Пример: 126*141 = 12*14*102+((12+6)*(14+1) – 12*14 – 6*1)*101+6*1
= 12*14*102+(18*15 – 12*14 – 6*1)*101+6*1
2. В произведении (a + b)*(c + d) суммы имеют различную длину (а максимально они могут отличаться на 1). Тогда уравниваем их, дополняя «короткую» нулём и, конечно, после вычисления произведения избавляемся от лишнего нуля. Этот же способ применяем и в случае, когда различны длины исходных чисел.
Пример: 9*16=(90*16)/10 = (9*1*102+((9+0)(1+6) – 9*1 – 0*6) *101+0*6)/10
= 1440/10=144
Вычислив «элементарные» произведения, поднимаемся по дереву и «собираем» произведения:
9*16 = (90*16)/10=(9*102+(63 – 9 – 0)*101+0)/10 = 144
90*97=81*102+(144 – 81 – 0)*101+0 = 8730
12*14=1*102+(15 – 1 – 8)*101+8 = 168
18*15=1*102+(54 – 1 – 40)*101+40 = 270
126*141=168*102+(270 – 168 – 6)*101+6 = 17766
36*44=12*102+(72 – 12 – 24)*101+24 = 1584
9036*9744=8730*104+(17766 – 8730 – 1584)*102+1584 = 88046784
4. Оцениваем сложность
Если перемножаемые числа имеют длину n = 2k, то на последнем шаге входа в рекурсию, мы выполняем не более 3k+1 элементарных умножений. Так как с каждым шагом количество произведений «коротких» чисел увеличивается в три раза, а совершается не более k + 1 шагов (ровно k, если не учитывать возможное увеличение разрядности в суммах a + b и c + d). А затем мы выходим из рекурсии, собирая произведения «длинных» чисел из произведений «коротких» с помощью сдвигов, сложений и вычитаний, количество которых не превосходит по порядку количества элементарных умножений.
Тогда сложность такого метода для любого n = 2k T(n) £ C × 3k+1, где константа C отражает количество сдвигов, сложений и вычитаний метода.
Если же n – любое натуральное число, то существует натуральное k такое, что 2k–1<> C1) «стирается», и временные сложности определяются степенями n1,6 и n2.
5. Формулируем усовершенствованный алгоритм Карацубы
Заметим, что процесс деления «длинных» чисел на «короткие» мы можем остановить на любом из шагов метода, далее полученные произведения найти обычным способом. Назовём точкой стандартного умножения – то значение длины чисел, на котором мы переходим к их обычному умножению.
Когда же выгоднее это сделать, продолжать ли процесс до однозначных чисел?
Среди точек стандартного умножения есть особенная – обменная точка N, начиная с которой описанная выше замена произведения «нетрудоёмкими» операциями (или один шаг метода) становится выигрышной. Это отнюдь не происходит сразу, сокращение числа произведений выполняется ценой дополнительных сложений‑вычитаний, разбиения числа на части. Вообще обменная точка во многом зависит от программной реализации алгоритма, её оптимальности или неоптимальности: непродуманная программа может значительно увеличить эту цену.
Но тогда разумно взять в качестве точки стандартного умножения именно обменную точку. Так мы максимально ускорим метод. Ведь перемножать по Карацубе числа, длиной меньшие N, уже не эффективно, а перемножать стандартно числа, длиной большие N, значит упускать возможность ускорить умножение.
Обменную точку несложно определить для конкретной программной реализации алгоритма, что мы и сделаем, написав программу (как?– вопрос на понимание метода, проверьте себя).
Итак, формулируем окончательный вариант алгоритма Карацубы. Пусть необходимо найти произведение двух целых чисел x × y с равными длинами.
Шаг 1. Если длина x и y меньше N – длины обменной точки (или точки стандартного умножения, если N пока неизвестно), то перемножаем их классическим способом.
Шаг 2. Иначе разбиваем каждое из сомножителей на две части: x = a × 10n + b и y = c × 10n + d, где n– длина «правых» частей, которая либо равна длине «левых» частей для чётной длины чисел x и y, либо на единицу меньше в противном случае.
Шаг 3. Вычисляем частичные произведения a × c, b × d и (a + b) × (c + d), рекурсивно обращаясь к данному алгоритму, уравнивая при необходимости длины перемножаемых сумм.
Шаг 4. Получаем произведение x × y, собирая частичные произведения с помощью операций сложения, вычитания и сдвига по формуле ???. Конец алгоритма.
6. Программно реализуем алгоритм Карацубы
Остаётся аккуратно записать код этой несложной рекурсивной логики.
Числа занесём в списки от младшего разряда к старшему, «задом‑наперёд», так как такая запись удобна при выполнении арифметических операций:
type TNumber=^TDigit;
TDigit=record
data:byte;
next:TNumber;
end;
var num1, num2, answer:TNumber;
И приведём основную функцию метода Карацубы, построенную на нескольких вспомогательных процедурах и функциях, реализацию которых мы оставляем за читателем (см. книгу [5], где описаны основные операции над «длинными» числами).
Отметим только, что эти процедуры и функции необходимо максимально освободить от лишних операций. Например, сложение в стандартном умножении выполнять не по окончанию, а по ходу его, то есть, перемножив очередные цифры, сразу же добавлять результирующую цифру в нужный разряд и формировать перенос в следующий разряд. Иначе многократно повторяясь для больших чисел, эти на первый взгляд «безобидные» лишние операции (в примере запись и чтение промежуточных результатов) очень замедлят программу.
function Multiply(x, y:TNumber; N:integer):TNumber;
var a, b, c, d, p1, p2, p3, sum1, sum2:TNumber;
N1, N2, Dl1, Dl2:integer;
begin
if N
Таблица 1
Эксперимент второй
Сравниваем время вычислений по обычному способу и методу Карацубы, ускоренному с помощью определённой в первом эксперименте обменной точки. Построенные таблица и график не нуждаются в каких‑либо комментариях, это результат всей проделанной выше работы.
Таблица 2
Как говорится, что и требовалось доказать.
8. В заключение несколько вопросов и упражнений
1. (В качестве разминки) Часто понятие рекурсии объясняется на примерах, где она вовсе необязательна. Так обычное «циклическое» вычисление факториала не только значительно экономит память, но и почти в два раза быстрее рекурсивного варианта, хотя в нем программа и выглядит «компактнее». Оправдана ли рекурсия в методе Карацубы и возможно ли принципиально (не моделируя стек вызовов программно) заменить её циклом?
2. (В качестве разминки) Будем увеличивать с некоторым шагом длину перемножаемых чисел, при этом скорость «чистого» метода Карацубы (где процесс деления «длинных» чисел на «короткие» продолжается до однозначных чисел) возрастает по сравнению со скоростью обычного способа, и, начиная с некоторого значения, становится больше последней. Является ли это значение обменной точкой?
3. (для математиков) Временная сложность алгоритма Карацубы удовлетворяет рекуррентному неравенству ??? (задача умножения 2n‑значных чисел сводится к двум умножениям n‑значных чисел, одному умножению не более (n+1)‑значных чисел, и простым операциям сложения, вычитания и сдвига, сложность которых пропорциональна n). Решите это неравенство, получив на более строгом уровне, чем это было сделано ранее, оценку временной сложности алгоритма.
4. (Для математиков) Известно, что многие свойства чисел и многочленов очень похожи. Арифметические операции с многочленами выполняются практически аналогично (разница только в отсутствии переноса разрядов). Опишите алгоритм Карацубы для умножения многочленов.
5*. (Для математиков) Поддержание равновесия, или балансировка – один из основных принципов при разработке хорошего алгоритма. Разбивая задачу на неравные части, мы можем получить неэффективный алгоритм. В случае алгоритма Карацубы факт максимальной результативности при разбиении чисел на равные части имеет несложное математическое доказательство. Попытайтесь найти это доказательство. Немного подскажем: весь фокус метода Карацубы – в избавлении от одного, как оказалось, лишнего произведения, и чем «весомее» это произведение, тем лучше.
6. (Для программистов) В качестве основной формулы метода Карацубы можно взять и такую:
???, (K/)
несколько отличную от формулы (K). Укажите рекуррентное неравенство и продумайте программу для этой модификации метода (здесь возникают некоторые свои особенности, например, при реализации арифметических операций необходимо учитывать знак чисел).
7. (Для программистов) Приведённая выше процедура перемножает числа равной длины. Если же числа имеют различные длины, то предварительно необходимо их уравнять, например, приписав к «короткому» числу незначащие нули в его начало. При этом эти нули далее используются наравне с собственными цифрами чисел, то есть происходит увеличение размерности задачи. Иной подход состоит в следующем. Числа x и y длинами lx и ly соответственно снова представляем, как x = a × 10n + b и y = c × 10n + d, где n = max(lx, ly)div 2 и a, b, c, d – не более чем n‑значные числа, и применяем ту же формулу– (K) или (K/). Программно реализуйте описанный метод.
Замечательный своей неожиданностью алгоритм, обнаруженный А. А. Карацубой, становится первым из серии быстрых алгоритмов умножения больших чисел. Обычный способ «в столбик» – уже не самый эффективный, и открывается дорога для дальнейшего исследования. И позже найдены ещё более совершенные методы, использующие идею интерполяции, быстрое преобразование Фурье, модулярную арифметику, понимание которых требует несколько больших познаний в математике. Это алгоритмы Тоома–Кука, Шенхаге, Шенхаге–Штрассена [1, 2, 4].
Для вас статьи на разнообразные темы: интересно и доступно
