Алгоритмы быстрого умножения: метод Карацубы | OTUS
⚡ Подписка на курсы OTUS!
Интенсивная прокачка навыков для IT-специалистов!
Подробнее

Курсы

Программирование
Разработчик чат-ботов и приложений для виртуальных ассистентов
-15%
PHP Developer. Professional Алгоритмы и структуры данных Scala-разработчик PHP Developer. Basic C# Developer. Professional
-23%
C# ASP.NET Core разработчик Python Developer. Basic Python Developer. Professional Cloud Solution Architecture Специализация iOS
-25%
HTML/CSS Android Developer. Professional React.js Developer Unity Game Developer. Professional NoSQL Java Developer. Professional Highload Architect C++ Developer. Basic Web-разработчик на Python Unity Game Developer. Basic Интенсив «Оптимизация в Java» Супер-практикум по использованию и настройке GIT Symfony Framework Java Developer. Basic Супер-интенсив "Tarantool"
Инфраструктура
MongoDB
-30%
Разработчик чат-ботов и приложений для виртуальных ассистентов
-15%
Administrator Linux. Professional
-26%
Network engineer Administrator Linux. Advanced Специализация Administrator Linux
-25%
Разработчик программных роботов (RPA) на базе UiPath и PIX
-27%
NoSQL Инфраструктурная платформа на основе Kubernetes Highload Architect Мониторинг и логирование: Zabbix, Prometheus, ELK Супер-практикум по использованию и настройке GIT Administrator Linux.Basic Экспресс-курс «IaC Ansible» Экспресс-курс по управлению миграциями (DBVC) Экспресс-курс "Версионирование и командная работа с помощью Git" Network engineer. Basic Основы Windows Server
Корпоративные курсы
Безопасность веб-приложений MongoDB
-30%
Разработчик чат-ботов и приложений для виртуальных ассистентов
-15%
Agile Project Manager Руководитель поддержки пользователей в IT
-10%
Промышленный ML на больших данных Cloud Solution Architecture Внедрение и работа в DevSecOps Spark Developer Reverse-Engineering IT-Recruiter Machine Learning. Professional Интенсив «Оптимизация в Java» Супер-практикум по использованию и настройке GIT Экcпресс-курс «ELK» Enterprise Architect Экспресс-курс «CI/CD или Непрерывная поставка с Docker и Kubernetes» Экспресс-курс «Введение в непрерывную поставку на базе Docker» Вебинар CERTIPORT
Специализации Курсы в разработке Подготовительные курсы Подписка
+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 комментариев
Для комментирования необходимо авторизоваться
🔥 Выгодные предложения
Подборка курсов, которые можно приобрести по выгодной цене только до конца июля!