Введение

Алгоритм умножения двух чисел

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

Алгоритмы умножения вручную

В дополнение к стандартному столбикному умножению, существует несколько других методов, используемых для выполнения умножения вручную. Такие алгоритмы могут быть разработаны для повышения скорости, облегчения вычислений или в образовательных целях, особенно когда компьютеры или таблицы умножения недоступны.

Умножение решетки

Умножение решеткой, или ситом, алгоритмически эквивалентно столбичному умножению. Оно требует подготовки решетки (сетки, нарисованной на бумаге), которая направляет вычисления и разделяет все умножения от сложений. В Европу этот метод был введен в 1202 году в книге Фибоначчи «Liber Abaci». Фибоначчи описал эту операцию как выполняемую мысленно, используя правую и левую руки для промежуточных вычислений. Матракчи Насух представил 6 различных вариантов этого метода в своей книге XVI века «Umdet ul Hisab». Метод широко использовался в школах Эндеруна по всей Османской империи. Кости Нейпера, или палочки Нейпера, также использовали этот метод, как опубликовал Нейпер в 1617 году, в год своей смерти. Как показано на примере, множимое и множитель записываются над и справа от решетки, или сита. Этот метод встречается в «Арифметике» Мухаммада ибн Мусы аль-Хорезми, одном из источников Леонардо, упомянутых Сиглером, автором книги «Liber Abaci Фибоначчи», 2002 года. На этапе умножения решетка заполняется двузначными произведениями соответствующих цифр, обозначающих каждую строку и столбец: цифра десятков помещается в верхний левый угол. На этапе сложения решетка суммируется по диагоналям. Наконец, если требуется перенос, ответ, показанный вдоль левой и нижней сторон решетки, приводится к нормальному виду переносом десятков, как при столбичном сложении или умножении.

Российское крестьянское размножение

Бинарный метод также известен как крестьянское умножение, поскольку он широко использовался людьми, которых причисляли к крестьянам и которые, таким образом, не заучивали таблицы умножения, необходимые для столбичного умножения. Этот алгоритм применялся ещё в Древнем Египте. Его главные преимущества заключаются в том, что его можно быстро освоить, он не требует запоминания и может быть выполнен с использованием подручных средств, например, фишек для покера, если нет бумаги и карандаша. Недостаток же состоит в том, что он требует больше шагов, чем столбичное умножение, и поэтому может быть неудобен для работы с большими числами.

Описание

На бумаге запишите в одном столбце числа, которые вы получаете, многократно деля множитель пополам, игнорируя остаток; в столбце рядом с ним многократно удваивайте множимое. Вычеркните каждую строку, в которой последняя цифра первого числа четная, и сложите оставшиеся числа во втором столбце, чтобы получить результат.

История четверть квадратного умножения

В доисторические времена умножение с использованием четвертей квадрата включало в себя функцию взятия целой части; что некоторые источники приписывают вавилонской математике (2000–1600 гг. до н.э.). Антуан Воазен опубликовал таблицу четвертей квадратов от 1 до 1000 в 1817 году в качестве вспомогательного средства для умножения. Более крупная таблица четвертей квадратов от 1 до 100000 была опубликована Сэмюэлем Ланди в 1856 году, а таблица от 1 до 200000 — Джозефом Блатером в 1888 году. Умножители, использующие метод четвертей квадрата, применялись в аналоговых компьютерах для формирования аналогового сигнала, являющегося произведением двух аналоговых входных сигналов. В этом применении сумма и разность двух входных напряжений формируются с помощью операционных усилителей. Квадрат каждого из этих значений аппроксимируется с использованием кусочно-линейных схем. Затем вычисляется разность двух квадратов и масштабируется в четверть с помощью еще одного операционного усилителя. В 1980 году Эверетт Л. Джонсон предложил использовать метод четвертей квадрата в цифровом умножителе. Для вычисления произведения двух 8-битных целых чисел, например, цифровое устройство вычисляет сумму и разность, находит соответствующие значения в таблице квадратов, вычисляет разность результатов и делит на четыре, сдвигая два бита вправо. Для 8-битных целых чисел таблица четвертей квадратов будет содержать 29−1=511 записей (одна запись для полного диапазона 0–510 возможных сумм, а для разностей используются только первые 256 записей в диапазоне 0–255) или 29−1=511 записей (используя для отрицательных разностей технику двух дополнительных кодов и 9-битной маски, что позволяет избежать проверки знака разности), каждая запись имеет ширину 16 бит (значения записей варьируются от (0²/4)=0 до (510²/4)=65025). Метод умножения с использованием четвертей квадрата был полезен для 8-битных систем, не имеющих аппаратного умножителя. Чарльз Путни реализовал его для процессора 6502.

Вычислительная сложность умножения

Одна из областей исследований в теоретической информатике посвящена количеству однобитовых арифметических операций, необходимых для умножения двух n-битных целых чисел. Это известно как вычислительная сложность умножения. Традиционные алгоритмы, выполняемые вручную, имеют асимптотическую сложность O(n²), но в 1960 году Анатолий Карацуба обнаружил, что можно достичь лучшей сложности (с помощью алгоритма Карацубы). В настоящее время алгоритм с наилучшей вычислительной сложностью – это алгоритм Дэвида Харви и Йориса ван дер Ховена, разработанный в 2019 году, который использует стратегии, основанные на преобразованиях Фурье, впервые применённых в алгоритме Шёнхаге–Страссена, для умножения целых чисел, используя всего O(n log n) операций. Предполагается, что это оптимальный алгоритм, однако доказать нижнюю границу сложности, равную O(n log n), пока не удалось.

История

Алгоритм Карацубы был первым известным алгоритмом умножения, асимптотически превосходящим по скорости длинное умножение, и поэтому может рассматриваться как начало теории быстрых умножений.

Кук

Другой метод умножения называется Toom–Cook или Toom 3. Метод Toom–Cook разбивает каждое число, которое необходимо умножить, на несколько частей. Метод Toom–Cook является одним из обобщений метода Карацубы. Toom–Cook с тремя разложениями позволяет выполнить умножение размера 3N, выполнив пять умножений размера N. Это ускоряет операцию в 9/5 раз, в то время как метод Карацубы ускоряет её в 4/3 раза. Хотя увеличение количества частей может дополнительно сократить время, затрачиваемое на рекурсивные умножения, накладные расходы на сложение и управление разрядами также возрастают. По этой причине метод преобразований Фурье обычно быстрее для чисел, содержащих несколько тысяч цифр, и асимптотически быстрее для еще больших чисел.

История

Алгоритмы были изобретены Страссеном (1968). Алгоритм стал практичным, а Шёнгаге и Страссен предоставили теоретические гарантии в 1971 году, что привело к созданию алгоритма Шёнгаге–Страссена.

Дальнейшие улучшения

В 2007 году асимптотическая сложность умножения целых чисел была улучшена швейцарским математиком Мартином Фюрером из Пенсильванского государственного университета до n log(n) 2Θ(log*(n)) с использованием преобразований Фурье над комплексными числами, где log* обозначает итерированный логарифм. Аниндья Де, Чандан Саха, Пиюш Курур и Рампрасад Саптарши в 2008 году предложили аналогичный алгоритм, использующий модульную арифметику, и достигли того же времени работы. В контексте вышеизложенного, эти последние авторы добились нахождения N, значительно меньшего, чем 23k + 1, так что Z/NZ имеет (2m)-й корень из единицы. Это ускоряет вычисления и снижает временную сложность. Однако эти алгоритмы быстрее, чем алгоритм Шёнхаге–Страссена, только для непрактически больших входных данных. В 2014 году Харви, Йориc ван дер Ховен и Лесерф представили новый алгоритм с временем работы , явно указав подразумеваемую константу в показателе. Они также предложили вариант своего алгоритма, достигающий , но обоснованность которого опирается на стандартные предположения о распределении чисел Мерсена. В 2016 году Кованов и Томе предложили алгоритм умножения целых чисел, основанный на обобщении чисел Ферма, который, предположительно, достигает сложности . Это соответствует условному результату 2015 года, полученному Харви, ван дер Ховеном и Лесерфом, но использует другой алгоритм и опирается на другую гипотезу. В 2018 году Харви и ван дер Ховен использовали подход, основанный на существовании коротких векторов решетки, гарантированных теоремой Минковского, чтобы доказать безусловную оценку сложности . В марте 2019 года Дэвид Харви и Йориc ван дер Ховен объявили об открытии алгоритма умножения со сложностью O(n log n). Результаты были опубликованы в Annals of Mathematics в 2021 году. Поскольку Шёнхаге и Страссен предсказывали, что n log(n) является "наилучшим возможным" результатом, Харви заявил: "Ожидается, что наша работа станет завершением исследований в этой области, хотя мы пока не знаем, как это строго доказать."

Нижняя граница

Существует тривиальная нижняя оценка Ω(n) для умножения двух n-битовых чисел на одном процессоре; соответствующий алгоритм (на обычных машинах, то есть на машинах, эквивалентных по Тьюрингу) и более строгая нижняя оценка неизвестны. Умножение не принадлежит классу AC0[p] для любого простого числа p, что означает отсутствие семейства схем постоянной глубины и полиномиального (или даже субекспоненциального) размера, использующих логические элементы AND, OR, NOT и MODp, способных вычислять произведение. Это следует из сведения задачи MODq к умножению за постоянное число шагов. Также известны нижние оценки для умножения в некоторых классах программ ветвления.