Изучение более быстрого способа умножения двух целых чисел, чем старый школьный метод.
Как посчитать 3 х 4? Очевидный ответ заключается в том, что нас заучивали наизусть во время учебы в школе, и мы знаем, что ответ равен 12. Как насчет вычисления 23 x 42, некоторые из нас могут умножать это в уме, в то время как другие используют ручку и бумагу, и мы приходим к результату 966. Что бы вы сделали, если бы я увеличил количество цифр с 3,4,… до, скажем, 60 в множителе и множимом, мы бы попробовали метод умножения, которому нас научили, верно.
Но, к нашему удивлению, нам не нужно использовать старый метод умножения. Здесь нам на помощь приходит алгоритм умножения Карацубы. Что это? Как это реализовано? И внесет ли это эффективность в вычисления по мере увеличения количества цифр? Прочитав эту статью, вы получите ответы на все такие вопросы, так что продолжайте читать.
Оглавление:
- Почему алгоритмы?
- Введение в алгоритм умножения Карацубы.
- Пример, иллюстрирующий алгоритм Карацубы.
- Доказательство алгоритма.
- Реализация алгоритма на Python.
- Анализ временной сложности.
Прежде чем погрузиться в Карацубу, давайте коснемся алгоритмов. Как мы все знаем, алгоритмы состоят из серии шагов/инструкций, разработанных для решения вычислительной задачи. Эти вычислительные задачи варьируются от простого целочисленного умножения до XYZ. (P.S. Я был поражен, когда прочитал об этом приложении для умножения целых чисел.)Важность использования таких алгоритмов становится совершенно очевидной, когда размер входных данных достаточно велик (стремится к бесконечности). Не то чтобы люди или современные компьютерные калькуляторы не могли их решить, но нам не нужно беспокоиться о точности и аккуратности при решении вычислительных задач с помощью алгоритмов. Добавляем красивую мантру Альфреда В. Ахо, которая говорит:
«Возможно, самый важный принцип для хорошего разработчика алгоритмов — отказаться быть довольным».
Итак, как программисты-алгоритмы, мы всегда должны думать, можем ли мы сделать лучше? Как и в случае целочисленного умножения, алгоритм Карацубы действительно лучше, чем метод старой школы.
Без лишних слов давайте перейдем к шагам, связанным с алгоритмом умножения Карацубы.
Постановка задачи. Рассмотрим умножение двух чисел, максимальная длина которых равна n.
Шаги:
1. Перепишите x и y в виде n/2 цифр в виде a, b, c и d.
2. Вычислить значение ac.
3. Вычислить значение bd.
4. Вычислить значение (a+b)(c+d)
5. Вычислить ad + bc путем вычитания ответа шага 4 — шага 3 — шага 2
6. Наконец, вычислите ответ, сделав несколько дополнений/вычитаний к нашим вычисленным значениям, используя приведенное ниже выражение.
Важно отметить, что мы вычисляем ad + bc, умножая (a+b) и (c+d) и затем выполняя некоторые вычитания. Это имеет решающее значение для производительности алгоритмов, поскольку мы знаем, что операции сложения/вычитания выполняются быстрее, чем умножения. Таким образом, мы делаем 3 рекурсивных умножения вместо 4, что значительно экономит время.
Например, рассмотрим x = 5678 и y = 1234.
Позвольте мне также доказать, почему этот метод работает для умножения двух целых чисел.
Доказательство:
Двигаемся вперед с реализацией алгоритма на языке Python:
Весь код можно посмотреть на GitHub здесь.
Сложность алгоритма во время выполнения:
Чтобы проанализировать сложность алгоритма Карацубы, рассмотрим количество умножений, выполняемых алгоритмом, как функцию от n, M(n). Как мы обсуждали ранее, алгоритм делает 3 рекурсивных вызова. Если n = 2 ^ k для любого значения k, то алгоритм трижды рекурсирует на n/2-значных числах, что приводит к рекуррентному соотношению:
Помимо рекурсивных умножений, сложения и вычитания, используемые на протяжении всей процедуры, будут выполняться за O(n). Таким образом, общая временная сложность составляет:
Применяя теорему Мастера к приведенному выше рекуррентному уравнению, мы получаем время выполнения как:
что быстрее, чем O (n²). (n-значное * n-значное умножение).
Надеемся, что эта статья была вам полезна. Спасибо за прочтение! Подписывайтесь и делитесь со всеми в вашем сообществе и не забывайте ставить лайки и комментировать. Подпишитесь на мою страницу на Medium Rishika Gupta.
Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter и LinkedIn. Посетите наш Community Discord и присоединитесь к нашему Коллективу талантов.
