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

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

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

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

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

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

Пример

В этом примере используется длинное умножение для умножения 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 00000000——————————————— 139676498390

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

умножить ( a [ 1 .. p ] , b [ 1 .. q ] , base ) // Операнды, содержащие самые правые цифры в индексе 1    Product = [ 1 .. p + q ] // Выделение места для результата    for b_i = от 1 до q // для всех цифр в b       перенос = 0   for 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 ] базовый мод             Product [ b_i + p ] = перенос // последняя цифра взята из окончательного переноса      возврат продукта 

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

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

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

Первоначально компьютеры использовали алгоритм, очень похожий на длинное умножение по основанию 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 различных вариантов этого метода в книге XVI века «Умдет-уль-Хисаб». Он широко использовался в школах Эндеруна по всей Османской империи. ^[4] Кости Непера или стержни Непьера также использовали этот метод, как опубликовано Непером в 1617 году, в год его смерти.

Как показано в примере, множимое и множитель записываются выше и справа от решетки или сита. Он встречается в ^« Арифметике» Мухаммада ибн Мусы аль-Хорезми , одном из источников Леонардо, упомянутом Сиглером, автором «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 до 100 000 была опубликована Сэмюэлем Лаунди в 1856 году ^[9] , а таблица от 1 до 200 000 - Йозефом Блатером в 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] и, таким образом, может рассматриваться как отправная точка для теории быстрых умножений.

Тум-Кук

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

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

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

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

Любое число по основанию 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)}$

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

Находя 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] Оно было опубликовано в «Анналах математики» в 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 ) можно вычислить следующим образом.

k ₁ знак равно c · ( а + б )

k ₂ знак равно а · ( d - c )

k ₃ знак равно б · ( c + d )

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

Мнимая часть знак равно k ₁ + k ₂ .

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

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

Полиномиальное умножение

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

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

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

14ac -3ab 2 переменный ток -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 кварты.

 т cwt квартал 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). В столбце четвертей суммируется результат, и результат помещается во вторую рабочую область (в данном случае это тривиальный ход). 94 четверти — это 23 центнера и 2 четверти, поэтому поместите 2 в ответ, а 23 — в следующий столбец слева. Теперь сложите три записи в столбце cwt и получите 587. Это 29 t 7 cwt, поэтому впишите 7 в ответ и 29 в столбец слева. Теперь сложите столбец тонн. Никакой настройки не требуется, поэтому результат просто копируется.

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

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

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

Рекомендации

1. «Умножение». www.mathematische-basteleien.de . Проверено 15 марта 2022 г.
2. Брент, Ричард П. (март 1978 г.). «Арифметический пакет множественной точности на Фортране». Транзакции ACM в математическом программном обеспечении . 4 : 57–70. CiteSeerX 10.1.1.117.8425 . дои : 10.1145/355769.355775. S2CID  8875817. 
3. Исон, Гэри (13 февраля 2000 г.). «Снова в школу для родителей». Новости BBC .
   Истауэй, Роб (10 сентября 2010 г.). «Почему родители сегодня не могут заниматься математикой». Новости BBC.
4. Чорлу, М.С.; Берлбоу, LM; Капраро, РМ; Корлу, Массачусетс; Хан, С. (2010). «Школа Османского дворца Эндерун и человек с множеством талантов, Матракчи Насух». Журнал Корейского общества математического образования, серия D: Исследования в области математического образования . 14 (1): 19–31.
5. Богомольный, Александр . «Крестьянское умножение». www.cut-the-knot.org . Проверено 4 ноября 2017 г.
6. Уэллс, Д. (1987). Словарь любопытных и интересных чисел Penguin . Книги о пингвинах. п. 44. ИСБН 978-0-14-008029-2.
7. Макфарланд, Дэвид (2007), Возвращение к четвертным таблицам: более ранние таблицы, разделение труда при построении таблиц и более поздние реализации в аналоговых компьютерах, стр. 1
8. Робсон, Элеонора (2008). Математика в древнем Ираке: социальная история . Издательство Принстонского университета. п. 227. ИСБН 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 на компьютерах , том. С-29, нет. 3, Вашингтон, округ Колумбия, США: Компьютерное общество IEEE, стр. 258–261, номер документа : 10.1109/TC.1980.1675558, ISSN  0018-9340, S2CID  24813486.
12. Путни, Чарльз (март 1986 г.). «Самое быстрое умножение 6502». Сборочная линия Apple . 6 (6).
13. Харви, Дэвид; ван дер Хувен, Йорис (2021). «Умножение целых чисел за время О ( п журнал ⁡ п ) {\displaystyle O(n\log n)}» (PDF) . Анналы математики . Вторая серия. 193 (2): 563–617. дои : 10.4007/анналы.2021.193.2.4. MR  4224716. S2CID  109934776.
14. Чарльз Бэббидж, Глава VIII - Об аналитической машине, обработка больших чисел, отрывки из жизни философа, Лонгман Грин, Лондон, 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. дои : 10.1145/1250790.1250800. ISBN 978-1-59593-631-8. S2CID  8437794.
18. Де, А.; Саха, К.; Курур, П.; Саптариши, Р. (2008). «Быстрое умножение целых чисел с использованием модульной арифметики». Материалы 40-го ежегодного симпозиума ACM по теории вычислений (STOC) . стр. 499–506. arXiv : 0801.1416 . дои : 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). «Быстрое умножение целых чисел с использованием обобщенных простых чисел Ферма». Математика. Комп. 88 (317): 1449–1477. arXiv : 1502.02800 . дои : 10.1090/mcom/3367. S2CID  67790860.
21. Харви, Д.; ван дер Хувен, Дж. (2019). «Быстрое умножение целых чисел с использованием коротких векторов решетки». Серия «Открытая книга» . 2 : 293–310. arXiv : 1802.07932 . дои : 10.2140/obs.2019.2.293. S2CID  3464567.
22. Хартнетт, Кевин (11 апреля 2019 г.). «Математики открывают идеальный способ умножения». Журнал Кванта . Проверено 3 мая 2019 г.
23. Харви, Дэвид; ван дер Хувен, Йорис (2021). «Умножение целых чисел за время О ( п журнал ⁡ п ) {\displaystyle O(n\log n)}» (PDF) . Анналы математики . Вторая серия. 193 (2): 563–617. дои : 10.4007/анналы.2021.193.2.4. MR  4224716. S2CID  109934776.
24. Гилберт, Лахлан (4 апреля 2019 г.). «Математический гений решает 48-летнюю задачу на умножение». УНЮУ . Проверено 18 апреля 2019 г.
25. Арора, Санджив; Барак, Вооз (2009). Вычислительная сложность: современный подход. Издательство Кембриджского университета. ISBN 978-0-521-42426-4.
26. Аблаев, Ф.; Карпински, М. (2003). «Нижняя граница умножения целых чисел в рандомизированных упорядоченных ветвящихся программах с однократным чтением» (PDF) . Информация и вычисления . 186 (1): 78–89. дои : 10.1016/S0890-5401(03)00118-4.
27. Кнут, Дональд Э. (1988), Искусство компьютерного программирования, том 2: Получисловые алгоритмы , Аддисон-Уэсли , стр. 519, 706.
28. Дюамель, П.; Веттерли, М. (1990). «Быстрое преобразование Фурье: обзор учебного пособия и современное состояние» (PDF) . Обработка сигнала . 19 (4): 259–299 См. раздел 4.1. дои : 10.1016/0165-1684(90)90158-U.
29. Джонсон, СГ; Фриго, М. (2007). «Модифицированное БПФ с разделением системы счисления с меньшим количеством арифметических операций» (PDF) . IEEE Транс. Сигнальный процесс . 55 (1): 111–9 См. раздел IV. Бибкод : 2007ITSP...55..111J. дои :10.1109/TSP.2006.882087. S2CID  14772428.
30. фон цур Гатен, Иоахим ; Герхард, Юрген (1999), Современная компьютерная алгебра, издательство Кембриджского университета, стр. 243–244, ISBN 978-0-521-64176-0.
31. Касл, Фрэнк (1900). Практикум Математика. Лондон: MacMillan and Co. p. 74.

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

• Уоррен младший, Генри С. (2013). Хакерское наслаждение (2-е изд.). Аддисон Уэсли - ISBN Pearson Education, Inc.  978-0-321-84268-8.
• Савард, Джон Дж. Г. (2018) [2006]. «Продвинутые арифметические методы». четырехблок . Архивировано из оригинала 3 июля 2018 г. Проверено 16 июля 2018 г.
• Йоханссон, Кенни (2008). Вычисления на основе сдвига и сложения малой мощности и низкой сложности (PDF) (Диссертация). Линчёпингские исследования в области науки и технологий (1-е изд.). Линчёпинг, Швеция: Факультет электротехники, Университет Линчёпинга . ISBN 978-91-7393-836-5. ISSN  0345-7524. № 1201. Архивировано (PDF) из оригинала 13 августа 2017 г. Проверено 23 августа 2021 г.(x+268 страниц)

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

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

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

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

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