Алгоритм Карацубы: различия между версиями

В 1960 году [[Колмогоров, Андрей Николаевич|Андрей Колмогоров]] проводил семинар, посвящённый математическим задачам кибернетики. Одной из рассматриваемых на семинаре задач стало [[умножение]] двух <math>n</math>-разрядных целых чисел. Основным известным методом умножения в то время было умножение «в столбик», которое при алгоритмической реализации требовало <math>O(n^2)</math> [[Модель вычислений|элементарных операций]] (сложений или умножений одноразрядных чисел). Колмогоров выдвинул гипотезу, что умножение «в столбик» является оптимальным алгоритмом умножения двух чисел в том смысле, что [[Временная сложность алгоритма|время работы]] любого метода умножения не меньше <math>n^2</math> по порядку величины. На правдоподобность «гипотезы <math>n^2</math>» указывало то, что метод умножения «в столбик» известен не менее четырёх тысячелетий, и если бы был более быстрый метод умножения, то он, вероятно, уже был бы найден. Однако, через неделю 23-летний [[Карацуба, Анатолий Алексеевич|Анатолий Карацуба]]<ref>{{статья|автор=Карацуба А., Офман Ю.|заглавие=Умножение многозначных чисел на автоматах|год=1962|издание=Доклады Академии Наук СССР|том=145|номер=2}}</ref><ref>{{статья|автор=Karacuba A.|заглавие=Berechnungen und die Kompliziertheit von Beziehungen|год=1975|издание=Elektronische Informationsverarbeitung und Kybernetik|том=11|язык=de}}</ref><ref>{{статья |автор=Карацуба А. А. |заглавие=Сложность вычислений |год=1995 |издание=Тр. МИАН|том=211 |страницы=186–202 |ссылка=http://mi.mathnet.ru/tm1120}}</ref><ref>{{книга |автор=[[Кнут, Дональд Эрвин|Кнут Д.]] |заглавие=Искусство программирования |издание=3-е изд |место={{М.}} |издательство=[[Вильямс (издательство)|Вильямс]] |том=2. Получисленные алгоритмы|год=2007|страниц=832|isbn=0-201-89684-2}}</ref> предложил новый метод умножения двух <math>n</math>-значных чисел с оценкой времени работы <math>O(n^{\log_23})</math> и тем самым опроверг «гипотезу <math>n^2</math>».

 

 

== Описание метода ==