Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Categories:

умножение карацубы

Анатолию Карацубе было 23 года, когда в 1960 году он обнаружил способ умножения чисел, более быстрый, чем известные до тех пор, и положил тем самым начало всей области быстрых алгоритмов.

История этого открытия описана вкратце в его обзорной статье о сложности вычислений (математика там довольно сухая, зато есть интересный исторический обзор об умножении в древности). Великий математик Колмогоров стремился доказать, что умножение двух n-размерных чисел требует примерно n^2 элементарных операций, и меньшим числом не обойтись. Например, представьте, что вы умножаете 1234 * 5678 в столбик: вам надо по сути дела умножить каждую цифру числа 1234 на каждую цифру числа 5678, т.е. сделать 16 элементарных умножений цифры на цифру; плюс еще много раз складывать промежуточные результаты и приписывать нули в конце. Но общее число операций будет порядка 16 (может, в два или три раза больше, чтобы учесть все сложения и приписывания). А если вы умножаете два числа по 1000 цифр в каждом, то общее число операций будет 1000^2, т.е. миллион (может, в 2-3 раза больше, но это несущественно). Колмогоров считал несомненным, что нет какого-то магического способа умножать числа быстрее, чем умножение в столбик, которым люди пользуются уже 2000 лет. Но он не мог это доказать.

Карацуба: "Осенью 1960 г. в Московском университете на механико-математическом факультете начал работать семинар по математическим вопросам кибернетики под руководством А.Н. Колмогорова, где А.Н. Колмогоровым была сформулирована гипотеза n^2 и поставлен ряд задач об оценке сложности решений линейных систем уравнений и других сходных вычислений. Я активно стал размышлять над гипотезой n^2 и ровно через неделю обнаружил, что алгоритм, которым я надеялся получить нижнюю оценку, дает оценку вида O(n^1,549...). После очередного заседания семинара я сообщил А.Н. Колмогорову о новом алгоритме умножения и об опровержении гипотезы n^2. Это сильно взволновало А.Н. Колмогорова, так как противоречило его довольно правдоподобной гипотезе. На следующем заседании семинара мой метод умножения был рассказан самим А.Н. Колмогоровым, и на этом семинар прекратил свою работу."

Попытаюсь объяснить суть открытия Карацубы в упрощенном виде. Представьте себе, что перед вами поставили задачу перемножить два числа, например 1234 * 5678, но при этом все операции сложения и приписывания нулей вам дают "бесплатно", а вот за каждое умножение двух цифр надо платить, ну не знаю, доллар. Может, кому-то удалось запатентовать таблицу умножения? Понятно, что это можно "обойти", сделав умножение через сложение, но давайте притворимся, что мы так не умеем, и что каждый раз, когда надо умножить две цифры, мы честно платим доллар; естественно, мы хотим делать как можно меньше умножений.

Если умножать в столбик обычным способом, то будет 16 умножений (каждая цифра на каждую), ничего не поделать. Но можно попробовать вывернуться как-то. Что если мы разделим каждое 4-х значное число на два двузначных?

1234 * 5678 = (12*100 + 34) * (56*100 + 78)

Здесь *100 не является по-настоящему умножением (это всего лишь приписывание нулей в конце, бесплатно). Если мы раскроем скобки, то получим сложную формулу в которой будут участвовать произведения чисел 12, 34, 56, 78, плюс всякие нули и сложения. Сколько умножений надо сделать? На первый взгляд четыре, когда мы раскрываем скобки: 12*56, 12*78, 34*56, 34*78. Если мы предполагаем, что два двузначных числа мы перемножаем в столбик, по 4 умножения цифр для каждого (а лучше мы пока не умеем), то выходит всего 4*4 = 16 умножений, и мы ничего не улучшили.

И тут открытие Карацубы. Обратим внимание, что нам на самом деле нужно получить, для окончательного сложения, три вещи: 12*56 (к нему приписать четыре нуля), 34*78 (не приписывать нулей), и 12*78+34*56 (к этому приписать два нуля). Если бы эту сумму двух произведений можно было как-то получить с помощью всего одного умножения, то вместе четырех мы бы получили три двузначных произведения. Карацуба заметил, что если мы скомпонуем вместе 12+34, и 56+78 - это весьма неинтуитивно, потому что мы складываем сотни и тысячи с десятками и единицами, казалось бы, зачем - и умножим, то получим:

(12+34)*(56+78) = 12*56 + 34*78 + 12*78 + 34*56.

Но первые два произведения мы и так уже вычисляем: 12*56 и 34*78. А оставшиеся два - это как раз то, что нам нужно. Значит, достаточно сделать только три умножения:

12*56
34*78
(12+34)*(56+78)

И из результата третьего вычесть первые два, чтобы получить все, что нам нужно для результата (после приписывания нулей и сложений, которые бесплатны). Если каждое из этих трех умножений двузначных чисел (да, 56+78 оказывается трехзначным, но это крохотное усложнение, которое легко учесть и не меняет сути) занимает, как раньше, 4 умножения, теперь у нас всего требуется только 3*4=12 умножений двух цифр. А ведь каждое умножение двухзначных чисел можно по такому же принципу свести к 3-м, а не 4-м умножениям, и тогда выходит всего 3*3=9 умножений, вместо исходных 16.

Это и есть алгоритм Карацубы, в одном из его видов. Естественно, это все становится важным, только когда мы умножаем 50-значные или 1000-значные числа, а не такие маленькие. Но суть в том, чтобы свести задачу к меньшей, с под-задачами на числах в 2 раза короче, но благодаря этому странному трюку оказывается надо делать не 4 под-задачи, а только три. Эти под-задачи в свою очередь разбиваются на три поменьше, и так далее. Кропотливый математический анализ показывает, что число операций для умножения двух n-разрядных чисел становится не n в квадрате, а примерно в степени полтора. А для очень длинных чисел это играет важную роль.
Tags: математика
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 31 comments