Алгоритмы быстрого умножения: метод Карацубы | OTUS

Курсы

Программирование
iOS Developer. Basic
-23%
Python Developer. Professional
-13%
Разработчик на Spring Framework
-23%
Golang Developer. Professional
-17%
Python Developer. Basic
-16%
iOS Developer. Professional
-13%
Node.js Developer
-15%
Unity Game Developer. Professional
-11%
React.js Developer
-12%
Android Developer. Professional
-7%
Software Architect
-12%
C++ Developer. Professional
-8%
Разработчик C#
-8%
Backend-разработчик на PHP Архитектура и шаблоны проектирования
-12%
Программист С Базы данных Framework Laravel PostgreSQL Reverse-Engineering. Professional CI/CD Agile Project Manager Нереляционные базы данных Супер - интенсив по паттернам проектирования Супер-практикум по использованию и настройке GIT IoT-разработчик Advanced Fullstack JavaScript developer Супер-интенсив "Azure для разработчиков"
Инфраструктура
Мониторинг и логирование: Zabbix, Prometheus, ELK
-17%
DevOps практики и инструменты
-18%
Архитектор сетей
-21%
Инфраструктурная платформа на основе Kubernetes
-22%
Супер-интенсив «IaC Ansible»
-16%
Супер-интенсив по управлению миграциями (DBVC)
-16%
Administrator Linux.Basic
-10%
Супер-интенсив «ELK»
-10%
Administrator Linux. Professional MS SQL Server Developer Безопасность Linux PostgreSQL Reverse-Engineering. Professional CI/CD VOIP инженер Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Супер-интенсив «СУБД в высоконагруженных системах»
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

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

В этой статье будет рассмотрен алгоритм умножения по методу Карацубы и три его идеи. Дополнительно выполним оценку времени работы этого алгоритма.

Формальное описание последовательности действий, ведущих к достижению конкретной цели, называют алгоритмом. Если говорить об информационных технологиях, то здесь в качестве исполнителя выступает вычислительное устройство. Оно проверяет свойства объекта, данного на входе, с последующим вычислением значения в соответствующей системе счисления.

Алгоритм может проверить простоту входящего числа (однозначное, многозначное), выполнить необходимую операцию (сложение и умножение, деление и вычитание). Но тут интересно другое: для программиста algorithm — это идея программы, поэтому нередко для того, чтобы написать качественный программный код, нужно изучить классические алгоритмы. А вот для математика algorithm представляет собой большую формулу, позволяющую работать с числами с целью вычисления необходимых значений (умножения, деления и пр.). И алгоритм, работающий наикратчайшим способом и быстрее, чем это принято, — весьма интересный математический факт.

Говоря о кратчайших способах вычисления, возьмем для примера не деление, а умножение. Известное всем умножение в столбик 2-х n-разрядных чисел занимает n2 умножений разряд на разряд. Так как происходит умножение каждого числа на каждое число, получается порядка n2 сложений. Возникает вопрос: а есть ли кратчайший способ умножения? Можно ли умножать быстрее? Ранее существовала гипотеза, что кратчайшего пути не существует, т. к. это невозможно — все-таки пар цифр же n2, плюс все это надо перемножить. Да и вообще, если бы существовал кратчайший способ умножения (алгоритм вычисления чисел), его давно бы уже придумали.

Однако советский ученый и математик Анатолий Алексеевич Карацуба такой алгоритм создал.

Screenshot_1-1801-c71dc9.png

Чтобы быстро умножить два 2-разрядных числа, по определению, надо вычислить четыре произведения, а потом сложить их и вычислить перенос.

Screenshot_2-1801-e3a79b.png

Первая идея метода Карацубы

Идея заключается в том, что 2 двухразрядных числа можно перемножить не за четыре, а за три операции умножения:

Screenshot_3-1801-766ad8.png

Вторая идея

Согласно ей, точно таким же образом можно умножать 2 n-разрядных числа:

Screenshot_4-1801-732f5b.png

Третья идея

Суть проста: чтобы вычислить каждое из 3-х произведений чисел вдвое меньшей длины, следует использовать тот же метод рекурсивно. Причем на каждом уровне рекурсии размер задачи снижается в два раза, в результате чего глубина рекурсии составляет log2n.

Оценка времени работы алгоритма умножения чисел

Рекурсивные вызовы процесса умножения приводят к образованию дерева. При каждом вызове происходит некоторое число расчетов, плюс выполняются 3 рекурсивных вызова. Общим временем работы в данном случае является сумма времени, затраченного на выполнения расчетов во всех узлах (вершинах) дерева, тогда как непосредственный процесс вызова процедур занимает гораздо меньше времени.

Screenshot_5-1801-a6228e.png

Главные идеи вышеописанного алгоритма неоднократно использовались при решении самых разных задач с однозначными и многозначными числами. Общая методика этого алгоритма умножения чисел получила название «разделяй и властвуй». Согласно данной технике вычисления, задачу делят на непересекающиеся подзадачи того же типа, однако меньшего размера, причем каждая подзадача вычисляется отдельно, а результаты решения в итоге объединяются в решение исходной задачи.

Можно умножать однозначные и многозначные числа ещё быстрее — за время O(n log n log log n), используя быстрое преобразование Фурье.

Algo_970x90-1801-545cb2.png

Источник

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться