Алгоритм умножения

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

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

Самый старый и простой метод, известный с античности как длинное умножение или умножение в начальной школе , состоит из умножения каждой цифры в первом числе на каждую цифру во втором и сложения результатов. Это имеет временную сложность , где n — количество цифр. При ручном выполнении это также можно перефразировать как умножение методом сетки или решетчатое умножение . В программном обеспечении это может называться «сдвиг и сложение», поскольку сдвиги битов и сложение являются единственными двумя необходимыми операциями. ${\displaystyle O(n^{2})}$

В 1960 году Анатолий Карацуба открыл умножение Карацубы , вызвав поток исследований в области быстрых алгоритмов умножения. Этот метод использует три умножения вместо четырех для умножения двух двузначных чисел. (Вариант этого также может быть использован для быстрого умножения комплексных чисел .) Рекурсивно это имеет временную сложность . Разбиение чисел на более чем две части приводит к умножению Тума-Кука ; например, использование трех частей приводит к алгоритму Тума-3 . Использование многих частей может установить показатель степени произвольно близко к 1, но постоянный множитель также растет, что делает его непрактичным. ${\displaystyle O(n^{\log _{2}3})}$

В 1968 году был открыт алгоритм Шёнхаге-Штрассена , который использует преобразование Фурье по модулю . Его временная сложность составляет . В 2007 году Мартин Фюрер предложил алгоритм со сложностью . В 2014 году Харви, Йорис ван дер Хувен и Лесерф предложили алгоритм со сложностью , таким образом сделав неявную константу явной; он был улучшен до в 2018 году. Наконец, в 2019 году Харви и ван дер Хувен придумали галактический алгоритм со сложностью . Это соответствует предположению Шёнхаге и Штрассена о том, что это будет оптимальная граница, хотя сегодня это остается гипотезой . ${\displaystyle O(n\log n\log \log n)}$ ${\displaystyle O(n\log n2^{\Theta (\log ^{*}n)})}$ ${\displaystyle O(n\log n2^{3\log ^{*}n})}$ ${\displaystyle O(n\log n2^{2\log ^{*}n})}$ ${\displaystyle O(n\log n)}$

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

Длинное умножение

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

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

Пример

В этом примере используется умножение в столбик для умножения 23 958 233 (множимое) на 5 830 (множитель) и получается результат 139 676 498 390 (произведение).

 23958233× 5830——————————————— 00000000 ( = 23,958,233 × 0) 71874699 (= 23 958 233 × 30) 191665864 (= 23 958 233 × 800)+ 119791165 (= 23 958 233 × 5 000)——————————————— 139676498390 (= 139 676 498 390)

Другие обозначения

В некоторых странах, например, в Германии , указанное выше умножение изображается аналогичным образом, но исходное произведение располагается горизонтально, а вычисление начинается с первой цифры множителя: ^[1]

23958233 · 5830——————————————— 119791165 191665864 71874699 000000099——————————————— 139676498390

Ниже приведен псевдокод, описывающий процесс умножения выше. Он сохраняет только одну строку для сохранения суммы, которая в конечном итоге становится результатом. Обратите внимание, что оператор '+=' используется для обозначения суммы к существующему значению и операции сохранения (подобно таким языкам, как Java и C) для компактности.

умножить ( a [ 1 .. p ] , b [ 1 .. q ] , основание ) // Операнды, содержащие самые правые цифры в индексе 1    product = [ 1 .. p + q ] // Выделяем место для результата    для b_i = 1 до q // для всех цифр в b       перенос = 0   для a_i = 1 до p // для всех цифр в a       произведение [ a_i + b_i - 1 ] += перенос + a [ a_i ] * b [ b_i ]           перенос = произведение [ a_i + b_i - 1 ] / основание         продукт [ a_i + b_i - 1 ] = продукт [ a_i + b_i - 1 ] mod base             продукт [ b_i + p ] = перенос // последняя цифра берется из конечного переноса      возврат товара 

Использование в компьютерах

Некоторые чипы реализуют длинное умножение, на аппаратном уровне или в микрокоде , для различных размеров целых и плавающих слов. В арифметике произвольной точности обычно используют длинное умножение с основанием, равным 2 ^w , где w — количество бит в слове, для умножения относительно небольших чисел. Чтобы умножить два числа с n цифрами с помощью этого метода, требуется около n ² операций. Более формально, умножение двух n -значных чисел с помощью длинного умножения требует Θ ( n ² ) однозначных операций (сложений и умножений).

При программной реализации алгоритмы длинного умножения должны иметь дело с переполнением во время сложений, что может быть затратным. Типичное решение — представить число в малой базе, b , так что, например, 8 b является представимым машинным целым числом. Затем можно выполнить несколько сложений, прежде чем произойдет переполнение. Когда число становится слишком большим, мы добавляем его часть к результату или переносим и отображаем оставшуюся часть обратно в число, которое меньше b . Этот процесс называется нормализацией . Ричард Брент использовал этот подход в своем пакете Fortran, MP. ^[2]

Первоначально компьютеры использовали очень похожий алгоритм длинного умножения в двоичной системе счисления, но современные процессоры оптимизировали схемы для быстрого умножения, используя более эффективные алгоритмы, ценой более сложной аппаратной реализации. ^{[ необходима цитата ]} В двоичной системе счисления длинное умножение иногда называют «сдвигом и сложением» , потому что алгоритм упрощается и состоит только из сдвига влево (умножение на степени двойки) и сложения. Большинство доступных в настоящее время микропроцессоров реализуют этот или другие похожие алгоритмы (например, кодирование Бута ) для различных целочисленных и плавающих размеров в аппаратных умножителях или в микрокоде . ^{[ необходима цитата ]}

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

 (( x  <<  2 )  +  x )  <<  1  # Здесь 10*x вычисляется как (x*2^2 + x)*2  ( x  <<  3 )  +  ( x  <<  1 )  # Здесь 10*x вычисляется как x*2^3 + x*2

В некоторых случаях такие последовательности сдвигов и сложений или вычитаний будут превосходить аппаратные умножители и особенно делители. Деление на число формы или часто может быть преобразовано в такую ​​короткую последовательность. ${\displaystyle 2^{n}}$ ${\displaystyle 2^{n}\pm 1}$

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

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

Метод сетки

Метод сетки (или метод ящика) — это вводный метод для умножения многозначных чисел, который часто преподается ученикам начальной школы или начальной школы . Он является стандартной частью национальной программы по математике начальной школы в Англии и Уэльсе с конца 1990-х годов. ^[3]

Оба множителя разбиваются («разделяются») на сотни, десятки и единицы, а затем произведения частей вычисляются явно на относительно простом этапе умножения, после чего эти вклады суммируются для получения окончательного ответа на отдельном этапе сложения.

Например, вычисление 34 × 13 можно выполнить с помощью сетки:

 300 40 90 + 12 ———— 442

затем складываем, чтобы получить 442, либо в виде единой суммы (см. справа), либо путем формирования итогов по строкам (300 + 40) + (90 + 12) = 340 + 102 = 442.

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

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

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

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

Наконец, просуммируйте по диагональным путям и перенесите по мере необходимости, чтобы получить ответ.

Решеточное или сито, умножение алгоритмически эквивалентно длинному умножению. Оно требует подготовки решетки (сетки, нарисованной на бумаге), которая направляет вычисления и отделяет все умножения от сложений . Оно было введено в Европу в 1202 году в Liber Abaci Фибоначчи . Фибоначчи описал операцию как умственную, используя свою правую и левую руки для выполнения промежуточных вычислений. Матракчи Насух ​​представил 6 различных вариантов этого метода в этой книге 16-го века Umdet-ul Hisab. Он широко использовался в школах Эндерун по всей Османской империи. ^[4] Кости Напьера или стержни Напьера также использовали этот метод, как опубликовано Напьером в 1617 году, в год его смерти.

Как показано в примере, множимое и множитель записаны выше и справа от решетки или решета. Это встречается в «Арифметике» Мухаммада ибн Мусы аль-Хорезми , одном из источников Леонардо, упомянутом Сиглером, автором «Fibonacci's Liber Abaci», 2002. ^{[ необходима цитата ]}

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

Пример

На рисунках справа показано, как вычислить 345 × 12 с помощью решетчатого умножения. В качестве более сложного примера рассмотрим рисунок ниже, на котором показано вычисление 23 958 233, умноженного на 5 830 (множитель); результат равен 139 676 498 390. Обратите внимание, что 23 958 233 находится вдоль верхней части решетки, а 5 830 — вдоль правой стороны. Произведения заполняют решетку, а сумма этих произведений (по диагонали) находится вдоль левой и нижней сторон. Затем эти суммы суммируются, как показано.

Русское крестьянское умножение

Двоичный метод также известен как крестьянское умножение, потому что он широко использовался людьми, которые классифицируются как крестьяне и, таким образом, не запомнили таблицу умножения, необходимую для умножения в столбик. ^{[5] [ не удалось проверить ]} Алгоритм использовался в Древнем Египте. ^[6] Его основные преимущества в том, что ему можно быстро обучиться, он не требует запоминания и может быть выполнен с использованием жетонов, таких как фишки для покера , если бумага и карандаш недоступны. Недостатком является то, что он требует больше шагов, чем длинное умножение, поэтому он может быть громоздким для больших чисел.

Описание

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

Примеры

В этом примере используется крестьянский метод умножения для умножения 11 на 3, в результате чего получается 33.

Десятичный: Двоичный:11 3 1011 115 6 101 1102 12 10 11001 24 1 11000 —— —————— 33 100001

Подробно описываем шаги:

• 11 и 3 написаны сверху
• 11 делится пополам (5,5), а 3 удваивается (6). Дробная часть отбрасывается (5,5 становится 5).
• 5 делится пополам (2,5), а 6 удваивается (12). Дробная часть отбрасывается (2,5 становится 2). Число в левом столбце (2) четное , поэтому число в правом столбце (12) отбрасывается.
• 2 делится пополам (1), а 12 удваивается (24).
• Все невычеркнутые значения суммируются: 3 + 6 + 24 = 33.

Метод работает, поскольку умножение является распределительным , поэтому:

${\displaystyle {\begin{aligned}3\times 11&=3\times (1\times 2^{0}+1\times 2^{1}+0\times 2^{2}+1\times 2^{3})\\&=3\times (1+2+8)\\&=3+6+24\\&=33.\end{aligned}}}$

Более сложный пример, использующий цифры из предыдущих примеров (23 958 233 и 5 830):

Десятичный: Двоичный:5830 23958233 1011011000110 10110110110010010110110012915 47916466 101101100011 101101101100100101101100101457 95832932 10110110001 101101101100100101101100100728 191665864 1011011000 1011011011001001011011001000
364 383331728 101101100 10110110110010010110110010000
182 766663456 10110110 10110110110010010110110010000091 1533326912 1011011 101101101100100101101100100000045 3066653824 101101 1011011011001001011011001000000022 6133307648 10110 10110110110010010110110010000000011 12266615296 1011 10110110110010010110110010000000005 24533230592 101 101101101100100101101100100000000002 49066461184 10 101101101100100101101100100000000000
1 98132922368 1 1011011011001001011011001000000000000 ————————————— 1022143253354344244353353243222210110 (до переноса) 139676498390 10000010000101010111100011100111010110

Умножение четверти квадрата

Эту формулу можно использовать в некоторых случаях для облегчения выполнения задач на умножение:

${\displaystyle {\frac {\left(x+y\right)^{2}}{4}}-{\frac {\left(x-y\right)^{2}}{4}}={\frac {1}{4}}\left(\left(x^{2}+2xy+y^{2}\right)-\left(x^{2}-2xy+y^{2}\right)\right)={\frac {1}{4}}\left(4xy\right)=xy.}$

В случае, когда и являются целыми числами, имеем, что ${\displaystyle x}$ ${\displaystyle y}$

${\displaystyle (x+y)^{2}\equiv (x-y)^{2}{\bmod {4}}}$

потому что и либо оба четные, либо оба нечетные. Это означает, что ${\displaystyle x+y}$ ${\displaystyle x-y}$

${\displaystyle {\begin{aligned}xy&={\frac {1}{4}}(x+y)^{2}-{\frac {1}{4}}(x-y)^{2}\\&=\left((x+y)^{2}{\text{ div }}4\right)-\left((x-y)^{2}{\text{ div }}4\right)\end{aligned}}}$

и достаточно (предварительно) вычислить целую часть квадратов, деленных на 4, как в следующем примере.

Примеры

Ниже приведена таблица соответствия квадратов четвертей с отброшенным остатком для цифр от 0 до 18; это позволяет умножать числа до 9×9 .

Если, например, вы хотите умножить 9 на 3, вы увидите, что сумма и разность составляют 12 и 6 соответственно. Поиск обоих этих значений в таблице дает 36 и 9, разность которых составляет 27, что является произведением 9 и 3.

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

В доисторические времена умножение на четверть квадрата включало функцию возведения в степень ; некоторые источники ^{[7] [8]} приписывают это вавилонской математике (2000–1600 гг. до н.э.).

Антуан Вуазен опубликовал таблицу четвертных квадратов от 1 до 1000 в 1817 году в качестве помощи при умножении. Более крупная таблица четвертных квадратов от 1 до 100000 была опубликована Сэмюэлем Лонди в 1856 году, ^[9] а таблица от 1 до 200000 — Джозефом Блатером в 1888 году. ^[10]

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

В 1980 году Эверетт Л. Джонсон предложил использовать метод четверти квадрата в цифровом умножителе. ^[11] Например, чтобы сформировать произведение двух 8-битных целых чисел, цифровое устройство формирует сумму и разность, ищет обе величины в таблице квадратов, берет разность результатов и делит на четыре, сдвигая два бита вправо. Для 8-битных целых чисел таблица четвертных квадратов будет иметь 2 ⁹ −1=511 записей (одна запись для всего диапазона 0..510 возможных сумм, разности используют только первые 256 записей в диапазоне 0..255) или 2 ⁹ −1=511 записей (для отрицательных разностей используется техника 2-дополнения и 9-битного маскирования, которая позволяет избежать проверки знака разностей), каждая запись имеет ширину 16 бит (значения записей находятся в диапазоне от (0²/4)=0 до (510²/4)=65025).

Техника множителя четверть квадрата принесла пользу 8-битным системам, которые не поддерживают аппаратный множитель. Чарльз Патни реализовал это для 6502. ^[12 ]

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

Нерешенная проблема в информатике :

Какой самый быстрый алгоритм умножения двузначных чисел? ${\displaystyle n}$

(еще нерешенные проблемы в информатике)

Направление исследований в области теоретической информатики посвящено числу однобитовых арифметических операций, необходимых для умножения двухбитовых целых чисел. Это известно как вычислительная сложность умножения. Обычные алгоритмы, выполняемые вручную, имеют асимптотическую сложность , но в 1960 году Анатолий Карацуба обнаружил, что возможна и лучшая сложность (с помощью алгоритма Карацубы ). ${\displaystyle n}$ ${\displaystyle O(n^{2})}$

В настоящее время алгоритмом с лучшей вычислительной сложностью является алгоритм 2019 года Дэвида Харви и Йориса ван дер Хувена , который использует стратегии использования теоретико-числовых преобразований, введенных в алгоритме Шёнхаге–Штрассена, для умножения целых чисел с использованием только операций. ^[13] Предполагается, что это наилучший возможный алгоритм, но нижние границы неизвестны. ${\displaystyle O(n\log n)}$ ${\displaystyle \Omega (n\log n)}$

Умножение Карацубы

Умножение Карацубы — это алгоритм «разделяй и властвуй» с трудоёмкостью O( n ^{log ₂ 3} ) ≈ O( n ^1,585 ), который использует рекурсию для объединения подвычислений.

Переписывая формулу, можно сделать подвычисления / рекурсию. Выполняя рекурсию, можно решить это быстро.

Пусть и будут представлены как -значные строки в некотором основании . Для любого положительного целого числа, меньшего , можно записать два заданных числа как ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle n}$ ${\displaystyle B}$ ${\displaystyle m}$ ${\displaystyle n}$

${\displaystyle x=x_{1}B^{m}+x_{0},}$

${\displaystyle y=y_{1}B^{m}+y_{0},}$

где и меньше . Произведение тогда равно ${\displaystyle x_{0}}$ ${\displaystyle y_{0}}$ ${\displaystyle B^{m}}$

${\displaystyle {\begin{aligned}xy&=(x_{1}B^{m}+x_{0})(y_{1}B^{m}+y_{0})\\&=x_{1}y_{1}B^{2m}+(x_{1}y_{0}+x_{0}y_{1})B^{m}+x_{0}y_{0}\\&=z_{2}B^{2m}+z_{1}B^{m}+z_{0},\\\end{aligned}}}$

где

${\displaystyle z_{2}=x_{1}y_{1},}$

${\displaystyle z_{1}=x_{1}y_{0}+x_{0}y_{1},}$

${\displaystyle z_{0}=x_{0}y_{0}.}$

Эти формулы требуют четырех умножений и были известны Чарльзу Бэббиджу . ^[14] Карацуба заметил, что можно вычислить всего за три умножения, за счет нескольких дополнительных сложений. С и как и прежде можно заметить, что ${\displaystyle xy}$ ${\displaystyle z_{0}}$ ${\displaystyle z_{2}}$

${\displaystyle {\begin{aligned}z_{1}&=x_{1}y_{0}+x_{0}y_{1}\\&=x_{1}y_{0}+x_{0}y_{1}+x_{1}y_{1}-x_{1}y_{1}+x_{0}y_{0}-x_{0}y_{0}\\&=x_{1}y_{0}+x_{0}y_{0}+x_{0}y_{1}+x_{1}y_{1}-x_{1}y_{1}-x_{0}y_{0}\\&=(x_{1}+x_{0})y_{0}+(x_{0}+x_{1})y_{1}-x_{1}y_{1}-x_{0}y_{0}\\&=(x_{1}+x_{0})(y_{0}+y_{1})-x_{1}y_{1}-x_{0}y_{0}\\&=(x_{1}+x_{0})(y_{1}+y_{0})-z_{2}-z_{0}.\\\end{aligned}}}$

Из-за накладных расходов на рекурсию умножение Карацубы выполняется медленнее, чем длинное умножение для малых значений n ; поэтому типичные реализации переключаются на длинное умножение для малых значений n .

Общий случай с умножением N чисел

Исследуя закономерности после расширения, можно увидеть следующее:

${\displaystyle (x_{1}B^{m}+x_{0})(y_{1}B^{m}+y_{0})(z_{1}B^{m}+z_{0})(a_{1}B^{m}+a_{0})=}$
${\displaystyle a_{1}x_{1}y_{1}z_{1}B^{4m}+a_{1}x_{1}y_{1}z_{0}B^{3m}+a_{1}x_{1}y_{0}z_{1}B^{3m}+a_{1}x_{0}y_{1}z_{1}B^{3m}}$
${\displaystyle +a_{0}x_{1}y_{1}z_{1}B^{3m}+a_{1}x_{1}y_{0}z_{0}B^{2m}+a_{1}x_{0}y_{1}z_{0}B^{2m}+a_{0}x_{1}y_{1}z_{0}B^{2m}}$
${\displaystyle +a_{1}x_{0}y_{0}z_{1}B^{2m}+a_{0}x_{1}y_{0}z_{1}B^{2m}+a_{0}x_{0}y_{1}z_{1}B^{2m}+a_{1}x_{0}y_{0}z_{0}B^{m}}$
${\displaystyle +a_{0}x_{1}y_{0}z_{0}B^{m}+a_{0}x_{0}y_{1}z_{0}B^{m}+a_{0}x_{0}y_{0}z_{1}B^{m}+a_{0}x_{0}y_{0}z_{0}}$

Каждое слагаемое связано с уникальным двоичным числом от 0 до , например , и т. д. Кроме того, в этой двоичной строке B возводится в степень числа 1, умноженного на m. ${\displaystyle 2^{N+1}-1}$ ${\displaystyle a_{1}x_{1}y_{1}z_{1}\longleftrightarrow 1111,\ a_{1}x_{0}y_{1}z_{0}\longleftrightarrow 1010}$

Если выразить это меньшим количеством терминов, то получим:

${\displaystyle \prod _{j=1}^{N}(x_{j,1}B^{m}+x_{j,0})=\sum _{i=1}^{2^{N+1}-1}\prod _{j=1}^{N}x_{j,c(i,j)}B^{m\sum _{j=1}^{N}c(i,j)}=\sum _{j=0}^{N}z_{j}B^{jm}}$, где означает цифру в числе i на позиции j. Обратите внимание, что ${\displaystyle c(i,j)}$ ${\displaystyle c(i,j)\in \{0,1\}}$

${\displaystyle z_{0}=\prod _{j=1}^{N}x_{j,0}}$
${\displaystyle z_{N}=\prod _{j=1}^{N}x_{j,1}}$
${\displaystyle z_{N-1}=\prod _{j=1}^{N}(x_{j,0}+x_{j,1})-\sum _{i\neq N-1}^{N}z_{i}}$

История

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

Тоом-Кук

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

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

Шёнхаге–Штрассен

Демонстрация умножения 1234 × 5678 = 7006652 с использованием быстрых преобразований Фурье (БПФ). Используются преобразования теории чисел в целых числах по модулю 337, выбирая 85 как корень восьмой степени из единицы. Основание 10 используется вместо основания 2 ^w для иллюстративных целей.

Каждое число в системе счисления B можно записать в виде многочлена:

${\displaystyle X=\sum _{i=0}^{N}{x_{i}B^{i}}}$

Более того, умножение двух чисел можно рассматривать как произведение двух многочленов:

${\displaystyle XY=(\sum _{i=0}^{N}{x_{i}B^{i}})(\sum _{j=0}^{N}{y_{i}B^{j}})}$

Потому что для : у нас есть свертка. ${\displaystyle B^{k}}$ ${\displaystyle c_{k}=\sum _{(i,j):i+j=k}{a_{i}b_{j}}=\sum _{i=0}^{k}{a_{i}b_{k-i}}}$

Используя быстрое преобразование Фурье (БПФ) с правилом свертки, мы можем получить

${\displaystyle {\hat {f}}(a*b)={\hat {f}}(\sum _{i=0}^{k}{a_{i}b_{k-i}})={\hat {f}}(a)}$● . То есть; ● , где — соответствующий коэффициент в пространстве Фурье. Это также можно записать как: fft(a * b) = fft(a) ● fft(b). ${\displaystyle {\hat {f}}(b)}$ ${\displaystyle C_{k}=a_{k}}$ ${\displaystyle b_{k}}$ ${\displaystyle C_{k}}$

У нас есть тот же коэффициент из-за линейности при преобразовании Фурье, а также потому, что эти полиномы состоят только из одного уникального члена на коэффициент:

${\displaystyle {\hat {f}}(x^{n})=\left({\frac {i}{2\pi }}\right)^{n}\delta ^{(n)}}$ и ${\displaystyle {\hat {f}}(a\,X(\xi )+b\,Y(\xi ))=a\,{\hat {X}}(\xi )+b\,{\hat {Y}}(\xi )}$

Правило свертки: ● ${\displaystyle {\hat {f}}(X*Y)=\ {\hat {f}}(X)}$ ${\displaystyle {\hat {f}}(Y)}$

Мы свели нашу задачу свертки к задаче произведения с помощью БПФ.

Находя ifft (полиномиальную интерполяцию) для каждого , получаем искомые коэффициенты. ${\displaystyle c_{k}}$

Алгоритм использует стратегию «разделяй и властвуй», чтобы разделить проблему на подзадачи.

Его временная сложность составляет O( n  log( n ) log(log( n ))).

История

Алгоритм был изобретен Штрассеном (1968). Он был реализован на практике, а теоретические гарантии были предоставлены в 1971 году Шёнхаге и Штрассеном, что привело к появлению алгоритма Шёнхаге–Штрассена . ^[16]

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

В 2007 году швейцарский математик Мартин Фюрер из Университета штата Пенсильвания улучшил асимптотическую сложность целочисленного умножения до n  log( n ) 2 ^{Θ( log * ( n ))} с помощью преобразований Фурье над комплексными числами , ^[17] где log ^* обозначает итерированный логарифм . Аниндья Де, Чандан Саха, Пиюш Курур и Рампрасад Саптариши в 2008 году предложили аналогичный алгоритм с использованием модульной арифметики, достигнув того же времени выполнения. ^[18] В контексте вышеизложенного материала, то, чего достигли эти последние авторы, заключается в том, что они нашли N, намного меньшее, чем 2 ^{3 k} + 1, так что Z / NZ имеет корень степени (2 m ) из единицы. Это ускоряет вычисления и снижает временную сложность. Однако эти последние алгоритмы быстрее, чем алгоритм Шёнхаге–Штрассена, только для непрактично больших входных данных.

В 2014 году Харви, Йорис ван дер Хувен и Лесерф ^[19] предложили новый алгоритм, который достигает времени выполнения , делая явной подразумеваемую константу в показателе степени. Они также предложили вариант своего алгоритма, который достигает , но справедливость которого основана на стандартных предположениях о распределении простых чисел Мерсенна . В 2016 году Кованов и Томе предложили алгоритм целочисленного умножения, основанный на обобщении простых чисел Ферма , который предположительно достигает границы сложности . Это соответствует условному результату Харви, ван дер Хувена и Лесерф 2015 года, но использует другой алгоритм и опирается на другую гипотезу. ^[20] В 2018 году Харви и ван дер Хувен использовали подход, основанный на существовании коротких векторов решетки, гарантированных теоремой Минковского, чтобы доказать безусловную границу сложности . ^[21] ${\displaystyle O(n\log n\cdot 2^{3\log ^{*}n})}$ ${\displaystyle O(\log ^{*}n)}$ ${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$ ${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$ ${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$

В марте 2019 года Дэвид Харви и Йорис ван дер Хувен объявили об открытии алгоритма умножения O ( n log n ) . ^[22] Он был опубликован в Annals of Mathematics в 2021 году. ^[23] Поскольку Шёнхаге и Штрассен предсказали, что n  log( n ) является «наилучшим возможным» результатом, Харви сказал: «...  ожидается, что наша работа станет концом пути для этой проблемы, хотя мы пока не знаем, как это строго доказать». ^[24]

Нижние границы

Существует тривиальная нижняя граница Ω ( n ) для умножения двух n -битных чисел на одном процессоре; неизвестен ни один алгоритм сопоставления (на обычных машинах, то есть на машинах, эквивалентных Тьюрингу), ни какая-либо более точная нижняя граница. Умножение лежит за пределами AC ⁰ [ p ] для любого простого числа p , что означает, что не существует семейства схем постоянной глубины, полиномиального (или даже субэкспоненциального) размера, использующих вентили AND, OR, NOT и MOD _{p ,} которые могут вычислять произведение. Это следует из сведения MOD _q к умножению с постоянной глубиной. ^[25] Нижние границы для умножения также известны для некоторых классов ветвящихся программ . ^[26]

Умножение комплексных чисел

Сложное умножение обычно включает четыре умножения и два сложения.

${\displaystyle (a+bi)(c+di)=(ac-bd)+(bc+ad)i.}$

Или

${\displaystyle {\begin{array}{c|c|c}\times &a&bi\\\hline c&ac&bci\\\hline di&adi&-bd\end{array}}}$

Как заметил Питер Унгар в 1963 году, можно сократить количество умножений до трех, используя по сути те же вычисления, что и в алгоритме Карацубы . ^[27] Произведение ( a  +  bi ) · ( c  +  di ) можно вычислить следующим образом.

к ₁ = с · ( а + б )

к ₂ = а · ( д − с )

к ₃ = б · ( с + d )

Действительная часть = k ₁ − k ₃

Мнимая часть = k ₁ + k ₂ .

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

Для быстрых преобразований Фурье (БПФ) (или любого линейного преобразования ) комплексные умножения производятся на постоянные коэффициенты c  +  di (называемые вращательными факторами в БПФ), в этом случае два сложения ( d − c и c + d ) могут быть предварительно вычислены. Следовательно, требуется только три умножения и три сложения. ^[28] Однако, замена умножения на сложение таким образом может быть невыгодной с современными блоками с плавающей точкой . ^[29]

Умножение полиномов

Все вышеперечисленные алгоритмы умножения также могут быть расширены для умножения многочленов . В качестве альтернативы можно использовать технику подстановки Кронекера для преобразования задачи умножения многочленов в одно двоичное умножение. ^[30]

Методы длинного умножения можно обобщить, чтобы обеспечить умножение алгебраических формул:

14ac - 3ab + 2 умножить на ac - ab + 1

14ac -3ab 2 ac-ab 1 ———————————————————— 14а 2 в 2 -3а 2 бв 2ак -14а 2 бс 3 а 2 б 2 -2аб 14ac -3ab 2 ——————————————————————————————————————— 14а 2 в 2 -17а 2 бв 16ак 3а 2 б 2 -5аб +2 ====================================== [31]

В качестве еще одного примера умножения столбиком рассмотрим умножение 23 длинных тонн (т), 12 центнеров (ц) и 2 квартеров (квартеров) на 47. В этом примере используются меры эвердьюпойс : 1 т = 20 ц, 1 ц = 4 квартера.

 т цвт кварта 23 12 2 47 х ———————————————— 141 94 94 940 470 29 23 ———————————————— 1110 587 94 ———————————————— 1110 7 2 ================= Ответ: 1110 тонн 7 центнеров 2 кварты

Сначала умножьте четверти на 47, результат 94 записывается в первую рабочую область. Затем умножьте cwt 12*47 = (2 + 10)*47, но пока не складывайте частичные результаты (94, 470). Аналогично умножьте 23 на 47, что дает (141, 940). Столбец quarters суммируется, и результат помещается во вторую рабочую область (тривиальный ход в этом случае). 94 quarters — это 23 cwt и 2 qtr, поэтому поместите 2 в ответ, а 23 — в следующий столбец слева. Теперь сложите три записи в столбце cwt, что дает 587. Это 29 t 7 cwt, поэтому запишите 7 в ответ, а 29 — в столбец слева. Теперь сложите столбец tons. Никаких корректировок вносить не нужно, поэтому результат просто копируется вниз.

Эту же схему и методы можно использовать для любых традиционных единиц измерения и недесятичных валют, таких как старая британская система фунтов стерлингов (£sd) .

Смотрите также

• Двоичный множитель
• Множитель Дадда
• Алгоритм деления
• Схема Горнера для оценки полинома
• Логарифм
• Алгоритм умножения матриц
• Устный счет
• Теоретико-числовое преобразование
• Простаферез
• Логарифмическая линейка
• система Трахтенберга
• Система остаточных чисел § Умножение для другого быстрого алгоритма умножения, особенно эффективного, когда много операций выполняются последовательно, например, в линейной алгебре.
• Дерево Уоллеса

Ссылки

1. "Умножение". www.mathematische-basteleien.de . Получено 2022-03-15 .
2. Брент, Ричард П. (март 1978 г.). «Пакет арифметики с множественной точностью на Фортране». Труды ACM по математическому программному обеспечению . 4 : 57–70. CiteSeerX 10.1.1.117.8425 . doi :10.1145/355769.355775. S2CID  8875817. 
3. Исон, Гэри (13 февраля 2000 г.). «Назад в школу для родителей». BBC News .
   Eastaway, Rob (10.09.2010). «Почему родители сегодня не умеют считать». BBC News.
4. Corlu, MS; Burlbaw, LM; Capraro, RM; Corlu, MA; Han, S. (2010). «Османская дворцовая школа Эндерун и человек с множественными талантами, Матракчи Насух». Журнал Корейского общества математического образования. Серия D: Исследования в области математического образования . 14 (1): 19–31.
5. Богомольный, Александр . «Крестьянское умножение». www.cut-the-knot.org . Получено 04.11.2017 .
6. Уэллс, Д. (1987). Словарь любопытных и интересных чисел Penguin . Penguin Books. стр. 44. ISBN 978-0-14-008029-2.
7. Макфарланд, Дэвид (2007), Возвращение к четвертным таблицам: более ранние таблицы, разделение труда при построении таблиц и более поздние реализации в аналоговых компьютерах, стр. 1
8. Робсон, Элеанор (2008). Математика в Древнем Ираке: Социальная история . Princeton University Press. стр. 227. ISBN 978-0691201405.
9. «Обзоры», Журнал гражданского инженера и архитектора : 54–55, 1857.
10. Холмс, Невилл (2003), «Умножение на четвертные квадраты», The Mathematical Gazette , 87 (509): 296–299, doi :10.1017/S0025557200172778, JSTOR  3621048, S2CID  125040256.
11. Эверетт Л., Джонсон (март 1980 г.), «Цифровой множитель четверти квадрата», IEEE Transactions on Computers , т. C-29, № 3, Вашингтон, округ Колумбия, США: IEEE Computer Society, стр. 258–261, doi : 10.1109/TC.1980.1675558, ISSN  0018-9340, S2CID  24813486
12. Патни, Чарльз (март 1986 г.). «Самое быстрое умножение 6502 на сегодняшний день». Сборочная линия Apple . 6 (6).
13. Харви, Дэвид; ван дер Хувен, Йорис (2021). "Целочисленное умножение за время O ( n log ⁡ n ) {\displaystyle O(n\log n)} " (PDF) . Анналы математики . Вторая серия. 193 (2): 563–617. doi :10.4007/annals.2021.193.2.4. MR  4224716. S2CID  109934776.
14. Чарльз Бэббидж, Глава VIII – Об аналитической машине, Рассмотрение больших чисел, Отрывки из жизни философа, Longman Green, Лондон, 1864; стр. 125.
15. Д. Кнут, Искусство программирования , т. 2, раздел 4.3.3 (1998)
16. Шёнхаге, А.; Штрассен, В. (1971). «Шнелле Умножение большого Залена». Вычисление . 7 (3–4): 281–292. дои : 10.1007/BF02242355. S2CID  9738629.
17. Фюрер, М. (2007). "Быстрое целочисленное умножение" (PDF) . Труды тридцать девятого ежегодного симпозиума ACM по теории вычислений, 11–13 июня 2007 г., Сан-Диего, Калифорния, США . стр. 57–66. doi :10.1145/1250790.1250800. ISBN 978-1-59593-631-8. S2CID  8437794.
18. Де, А.; Саха, К.; Курур, П.; Саптариши, Р. (2008). «Быстрое целочисленное умножение с использованием модульной арифметики». Труды 40-го ежегодного симпозиума ACM по теории вычислений (STOC) . стр. 499–506. arXiv : 0801.1416 . doi : 10.1145/1374376.1374447. ISBN 978-1-60558-047-0. S2CID  3264828.
19. Харви, Дэвид; ван дер Хувен, Йорис; Лесерф, Грегуар (2016). «Еще быстрее целочисленное умножение». Журнал сложности . 36 : 1–30. arXiv : 1407.3360 . дои : 10.1016/j.jco.2016.03.001. МР  3530637.
20. Кованов, Святослав; Томе, Эммануэль (2019). «Быстрое целочисленное умножение с использованием обобщенных простых чисел Ферма». Math. Comp. 88 (317): 1449–1477. arXiv : 1502.02800 . doi :10.1090/mcom/3367. S2CID  67790860.
21. Харви, Д.; ван дер Хувен, Дж. (2019). «Быстрое целочисленное умножение с использованием коротких решетчатых векторов». Серия открытых книг . 2 : 293–310. arXiv : 1802.07932 . doi : 10.2140/obs.2019.2.293. S2CID  3464567.
22. Хартнетт, Кевин (2019-04-11). «Математики открывают идеальный способ умножения». Журнал Quanta . Получено 2019-05-03 .
23. Харви, Дэвид; ван дер Хувен, Йорис (2021). "Целочисленное умножение за время O ( n log ⁡ n ) {\displaystyle O(n\log n)} " (PDF) . Анналы математики . Вторая серия. 193 (2): 563–617. doi :10.4007/annals.2021.193.2.4. MR  4224716. S2CID  109934776.
24. Гилберт, Лаклан (2019-04-04). «Математический гений решает 48-летнюю задачу по умножению». UNSW . Получено 2019-04-18 .
25. Арора, Санджив; Барак, Боаз (2009). Вычислительная сложность: современный подход. Cambridge University Press. ISBN 978-0-521-42426-4.
26. Аблаев, Ф.; Карпински, М. (2003). "Нижняя граница для целочисленного умножения в рандомизированных упорядоченных однократно читающих ветвящихся программах" (PDF) . Информация и вычисления . 186 (1): 78–89. doi :10.1016/S0890-5401(03)00118-4.
27. Кнут, Дональд Э. (1988), Искусство программирования, том 2: Получисленные алгоритмы , Эддисон-Уэсли , стр. 519, 706
28. Дюамель, П.; Веттерли, М. (1990). «Быстрые преобразования Фурье: учебный обзор и современное состояние» (PDF) . Обработка сигналов . 19 (4): 259–299 См. раздел 4.1. doi :10.1016/0165-1684(90)90158-U.
29. Джонсон, С.Г.; Фриго, М. (2007). «Модифицированное БПФ с разделенным основанием и меньшим количеством арифметических операций» (PDF) . IEEE Trans. Signal Process . 55 (1): 111–9 См. раздел IV. Bibcode :2007ITSP...55..111J. doi :10.1109/TSP.2006.882087. S2CID  14772428.
30. фон Цур Гатен, Иоахим ; Герхард, Юрген (1999), Современная компьютерная алгебра, издательство Кембриджского университета, стр. 243–244, ISBN 978-0-521-64176-0.
31. Касл, Фрэнк (1900). Workshop Mathematics. Лондон: MacMillan and Co. стр. 74.

Дальнейшее чтение

• Уоррен-младший, Генри С. (2013). Hacker's Delight (2-е изд.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.
• Savard, John JG (2018) [2006]. "Advanced Arithmetic Techniques". quadibloc . Архивировано из оригинала 2018-07-03 . Получено 2018-07-16 .
• Йоханссон, Кенни (2008). Маломощные и малосложные вычисления на основе сдвига и сложения (PDF) (диссертация). Исследования Линчёпинга в области науки и технологий (1-е изд.). Линчёпинг, Швеция: Кафедра электротехники, Университет Линчёпинга . ISBN 978-91-7393-836-5. ISSN  0345-7524. № 1201. Архивировано (PDF) из оригинала 2017-08-13 . Получено 2021-08-23 .(x+268 страниц)

Внешние ссылки

Основная арифметика

• Множество способов арифметики в повседневной математике UCSMP
• Презентация PowerPoint о древней математике
• Флэш-видео по умножению решеток

Расширенные алгоритмы

• Алгоритмы умножения, используемые GMP