?

Log in

No account? Create an account
умножение карацубы - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

умножение карацубы [июл. 14, 2018|09:38 pm]
Anatoly Vorobey
[Tags|]

Анатолию Карацубе было 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 в квадрате, а примерно в степени полтора. А для очень длинных чисел это играет важную роль.
СсылкаОтветить

Comments:
From: karpion
2018-07-14 07:45 pm
Я бы добавил (в коней статьи, к последнему предложению), что такое умножение востребовано в современном шифровании, в т.ч. в ЭЦП.

Upd: Прикол в том, что (56+78) - это не двузначное, а трёхзначное число.
(12+34) - тоже могло бы быть трёхзначным, но вот не получилось.

Edited at 2018-07-14 19:51 (UTC)
(Ответить) (Thread)
[User Picture]From: lightjedi
2018-07-14 08:56 pm
Гораздо интереснее добавить что востребовано оно в ЭЦП на очень небольшую глубину рекурсии как раз из за того что реальное умножение всего в несколько раз медленнее сложения и вот эта куча сложений очень быстро начинает нивелировать эффект меньшего числа умножений.
(Ответить) (Parent) (Thread)
From: dmpogo
2018-07-14 08:39 pm
Идея напоминает FFT
(Ответить) (Thread)
[User Picture]From: akor168
2018-07-14 09:00 pm
Это по сути одно и то же. Развитие этих алгоритмов и наилучшие современные результаты как раз достигнуты через быстрое преобразование фурье в разных хитрых кольцах.
(Ответить) (Parent) (Thread)
[User Picture]From: lightjedi
2018-07-14 09:02 pm
Все таки стоит написать что реально сложение ни на какой архитектуре небесплатное по сравнению с умножением.

Что привело к тому что от последующих 30 лет улучшений карацубиных алгоритмов толку на практике никакого нет.
(Ответить) (Thread)
[User Picture]From: akor168
2018-07-14 10:02 pm
Кажется это справедливо по отношению к любым улучшениям быстрых алгоритмов(в умножении матриц кажется та же фигня). Проблема очевидно же в том, что константы при уменьшении показателя степени никак не могут оставаться теми же, а растут, а значит вероятность что для практических целей эта константа съест все улучшение на РЕАЛЬНЫХ данных начала числового ряда повышается. Эта проблема кажется очень плохо освещается и в теоретических и практических курсах, что O(n^3) запросто может быть лучше O(n^2) из-за того что константа во втором случае может быть намного-намного больше.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: relf
2018-07-14 09:57 pm

"на этом семинар прекратил свою работу" - других интересных вопросов помимо умножения не нашлось?

(Ответить) (Thread)
From: ald1976
2018-07-18 11:52 am
Семинар создавался под конкретную задачу.

А "другие интересные вопросы" рассматривают на других семинарах.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: volk007
2018-07-15 03:10 am
Я не понимаю, за что борьба - в двоичной-то системе умножение вообще состоит только из сдвигов и сложений.
(Ответить) (Thread)
[User Picture]From: cryinstone
2018-07-15 04:16 am
Курс Стенфорда по алгоритмам 1 на Курсере как раз начинался с умножения Карацубы :)

Edited at 2018-07-15 04:16 (UTC)
(Ответить) (Thread)
[User Picture]From: repliki
2018-07-15 04:43 am
Справедливости ради надо сказать, что первым складывать нескладываемое (единицы с десятками <=> мнимую часть с действительной) придумал не Карацуба, а Гаусс, для умножения комплексных чисел.
(Ответить) (Thread)
[User Picture]From: utnapishti
2018-07-15 08:22 am
Разве комплексные числа придумал Гаусс?..
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: gegmopo4
2018-07-15 06:06 am
Интересное следствие этого. Если считать факториал большого числа последовательно умножая числа от 1 до N (в любом порядке), то сложность растёт приблизительно квадратично, и на вычисление 1000000! нужно несколько часов. А вот если разделить множество множителей на две части, перемножить их отдельно (используя рекурсивно этот же алгоритм), и потом перемножить их результат, то время сокращается на порядки. Именно из-за того, что при перемножении больших чисел мы экономим используя умножение Карацупы, а при умножении большого числа на маленькое — нет.

Впрочем, для вычисления факториала есть ещё более эффективные алгоритмы.
(Ответить) (Thread)
[User Picture]From: levtsn
2018-07-15 10:52 am

А что если синтезировать алгоритм в виде двоичной логики. И минимизировать его по критерию.

(Ответить) (Thread)
(Удалённый комментарий)
[User Picture]From: levtsn
2018-07-15 10:53 am

А если графическим методом. Придумать апаратуру соответствующую. Типа японского метода.

(Ответить) (Thread)
[User Picture]From: matholimp
2018-07-15 07:57 pm
Всё закономерно и банально до единственного момента: можно заменить систему счисления. Да, перевод из системы с основанием 10 в систему с основанием 100 имеет нулевую трудность. В иных случаях эти затраты нужно учесть. Но с учётом затрат можно оптимизировать выбор основания системы счисления, счёт в которой требует меньших затрат.
(Ответить) (Thread)
From: d1gital_love
2018-07-27 05:22 pm
Хорошее замечание!

Добавлю только

число *
123456789012345678901234567890
123456789012345678901234567890
1234567890123456789012345678901234567890

имеет только 10 разных "умножений".

Любой криптограф или специалист в конечных полях объяснит это. Объяснение "почему это так" простым смертным не нужно ИМХО, тем более на первом курсе.
(Ответить) (Parent) (Thread)
From: a_shen
2018-07-15 08:08 pm
там была ещё удивительная и загадочная история, как это обозвали Gauss trick https://www.dropbox.com/s/wv8gv4wuviyztcs/uspensky-2.pdf?dl=0
(Ответить) (Thread)
[User Picture]From: hervejoncour
2018-07-15 09:00 pm
Tim Roughgarden, читающий лекции в Стэнфорде написал книжку Algorithms Illuminated, Part !: The Basics, там этот метод в первой главе, я когда читал изумлялся насколько элегантно. Спросил в офисе, но никто ни сном ни духом.
(Ответить) (Thread)
From: humanbean194
2018-07-16 02:25 pm
1.5849…
(Ответить) (Thread)