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

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

Метод сетки [ править ]

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

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

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

 300 40 90 + 12 ———— 442

×	30	4
10	300	40
3	90	12

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

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

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

Длинное умножение [ править ]

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

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

Пример [ править ]

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

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

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

Оптимизация космической сложности [ править ]

В этом разделе не процитировать любые источники . Пожалуйста, помогите улучшить этот раздел , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален . ( Сентябрь 2012 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Пусть п будет общее количество цифр в двух входных чисел в базовой D . Если результат необходимо сохранить в памяти, то сложность пространства тривиально равна ( n ). Однако в некоторых приложениях нет необходимости хранить весь результат в памяти, и вместо этого цифры результата можно передавать в потоковом режиме по мере их вычисления (например, в системную консоль или файл). В этих сценариях длинное умножение имеет то преимущество, что его можно легко сформулировать как алгоритм пространства журнала ; то есть алгоритм, которому требуется только рабочее пространство, пропорциональное логарифму количества цифр во входных данных ( Θ (log  n )). Это двойнойлогарифм умножаемых чисел (log log  N ). Обратите внимание, что сами операнды по-прежнему необходимо хранить в памяти, и их пространство Θ ( n ) не рассматривается в этом анализе.

Метод основан на наблюдении, что каждую цифру результата можно вычислить справа налево, зная только перенос из предыдущего шага. Пусть a _i и b _i будут i-й цифрой операнда, с дополнениями a и b слева нулями, чтобы иметь длину n , r _i - i-я цифра результата, а c _i - перенос, сгенерированный для r _i (i = 1 - самая правая цифра), то

${\ displaystyle {\ begin {align} r_ {i} & = \ left (c_ {i-1} + \ sum _ {j + k = i + 1} a_ {j} b_ {k} \ right) \ mod D \\ c_ {i} & = \ left \ lfloor (c_ {i-1} + \ sum _ {j + k = i} a_ {j} b_ {k}) / D \ right \ rfloor \\ c_ { 0} & = 0 \ end {выровнено}}}$

или же

${\ displaystyle c_ {i} = \ left (\ sum _ {m = 0} ^ {i-2} \ sum _ {j + k = im} a_ {j} b_ {k} \ right) / D.}$

Простой индуктивный аргумент показывает, что перенос никогда не может превышать n, а общая сумма для r _i никогда не может превышать D * n : перенос в первый столбец равен нулю, а для всех остальных столбцов в столбце не более n цифр. , и перенос не более n из предыдущего столбца (по предположению индукции). Сумма не превосходит D * n , а перенос в следующий столбец не превышает D * n / D или n . Таким образом, оба этих значения могут быть сохранены в O (log n ) цифрах.

В псевдокоде алгоритм лог-пространства:

multiply ( a [ 1 .. p ] ,  b [ 1 .. q ] ,  base )  // Операнды, содержащие крайние правые цифры с индексом 1  tot  =  0  для  ri  =  1  до  p  +  q  -  1  // Для каждой цифры результата  для  bi  =  MAX ( 1 ,  ri  -  p  +  1 )  до  MIN ( ri ,  q ) // Цифры из b, которые необходимо учитывать  ai  =  ri  -  bi  +  1  // Цифры из следующей "симметрии"  tot  =  tot  +  ( a [ ai ]  *  b [ bi ])  product [ ri ]  =  tot  mod  base  tot  =  этаж ( общий  /  базовый )  продукт [ p + q ]  =  общий  мод.  базовый // Последняя цифра результата берется из последнего  возвращенного  продукта переноса

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

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

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

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

Умножение решетки [ править ]

Решетчатое или решетчатое умножение алгоритмически эквивалентно длинному умножению. Это требует подготовки решетки (сетки, нарисованной на бумаге), которая направляет вычисления и отделяет все умножения от сложений . Он был введен в Европе в 1202 году в фибоначчиевого «s Liber Abaci . Фибоначчи описал эту операцию как мысленную, используя свою правую и левую руки для выполнения промежуточных вычислений. Матракчи Насух представил 6 различных вариантов этого метода в своей книге XVI века «Умдет-уль Хисаб». Он широко использовался в школах Эндеруна по всей Османской империи. ^[3] Кости Непьера или стержни Непьера. также использовал этот метод, опубликованный Нэпиром в 1617 году, в год его смерти.

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

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

Пример [ править ]

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

 2 3 9 5 8 2 3 3 + --- + --- + --- + --- + --- + --- + --- + --- + - | 1 / | 1 / | 4 / | 2 / | 4 / | 1 / | 1 / | 1 / | | / | / | / | / | / | / | / | / | 5 01 | / 0 | / 5 | / 5 | / 5 | / 0 | / 0 | / 5 | / 5 | + --- + --- + --- + --- + --- + --- + --- + --- + - | 1 / | 2 / | 7 / | 4 / | 6 / | 1 / | 2 / | 2 / | | / | / | / | / | / | / | / | / | 8 02 | / 6 | / 4 | / 2 | / 0 | / 4 | / 6 | / 4 | / 4 | + --- + --- + --- + --- + --- + --- + --- + --- + - | 0 / | 0 / | 2 / | 1 / | 2 / | 0 / | 0 / | 0 / | | / | / | / | / | / | / | / | / | 3 17 | / 6 | / 9 | / 7 | / 5 | / 4 | / 6 | / 9 | / 9 | + --- + --- + --- + --- + --- + --- + --- + --- + - | 0 / | 0 / | 0 / | 0 / | 0 / | 0 / | 0 / | 0 / | | / | / | / | / | / | / | / | / | 0 24 | / 0 | / 0 | / 0 | / 0 | / 0 | / 0 | / 0 | / 0 | + --- + --- + --- + --- + --- + --- + --- + --- + - 26 15 13 18 17 13 09 00

 01 002 0017 00024 000026 0000015 00000013 000000018 0000000017 00000000013 000000000009 0000000000000 ————————————— 139676498390

= 139 676 498 390

Двоичное или крестьянское умножение [ править ]

Бинарный метод также известен как крестьянское умножение, потому что он широко использовался людьми, которых относили к крестьянам и, следовательно, не запомнили таблицы умножения, необходимые для длительного умножения. ^{[4] [ неудачная проверка ]} Алгоритм использовался в Древнем Египте. ^{[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 {align} 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 {align}}}$

Более сложный пример с использованием цифр из предыдущих примеров (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

Двоичное умножение в компьютерах [ править ]

Это разновидность крестьянского умножения.

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

Сдвинуть и добавить [ редактировать ]

Исторически сложилось так, что компьютеры использовали алгоритм «сдвиг и сложение» для умножения небольших целых чисел. Обе базы 2 длинного умножение и основание 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 ^ {п}}$${\ displaystyle 2 ^ {n} \ pm 1}$

Эти типы последовательностей всегда должны использоваться для компьютеров, которые не имеют инструкции «умножения» ^[7], а также могут использоваться путем расширения чисел с плавающей запятой, если заменить сдвиги вычислением 2 * x как x + x , поскольку они логически эквивалентны.

Умножение на четверть квадрата [ править ]

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

${\displaystyle \left\lfloor {\frac {\left(x+y\right)^{2}}{4}}\right\rfloor -\left\lfloor {\frac {\left(x-y\right)^{2}}{4}}\right\rfloor ={\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.}$

Если один из x + y и x - y нечетный, другой также нечетный; это означает, что дроби, если таковые имеются, будут сокращаться, а отбрасывание остатков не вносит никаких ошибок. Ниже приведена справочная таблица четверть квадратов с отброшенным остатком для цифр от 0 до 18; это позволяет умножать числа до 9 × 9 .

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

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

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

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

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

Алгоритмы быстрого умножения для больших входных данных [ править ]

Алгоритм сложного умножения [ править ]

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

${\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}}}$

Но есть способ уменьшить количество умножений до трех. ^[14]

Произведение ( a  +  bi ) · ( c  +  di ) можно рассчитать следующим образом.

k ₁ = c · ( a + b )

k ₂ = a · ( d - c )

k ₃ = b · ( c + d )

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

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

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

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

Умножение Карацубы [ править ]

Для систем, которым необходимо умножать числа в диапазоне нескольких тысяч цифр, таких как системы компьютерной алгебры и библиотеки bignum , длинное умножение выполняется слишком медленно. Эти системы могут использовать умножение Карацубы , которое было открыто в 1960 г. (опубликовано в 1962 г.). Суть метода Карацубы заключается в наблюдении, что двузначное умножение может быть выполнено только с тремя, а не с четырьмя умножениями, которые обычно требуются. Это пример того, что сейчас называется алгоритмом «разделяй и властвуй» . Предположим, мы хотим умножить два двузначных числа с основанием m : x ₁ m + x ₂ и y ₁м + у ₂ :

1. вычислить x ₁ · y ₁ , назвать результат F
2. вычислить x ₂ · y ₂ , назвать результат G
3. вычислить ( x ₁ + x ₂ ) · ( y ₁ + y ₂ ), назвать результат H
4. вычислить H - F - G , назвать результат K ; это число равно x ₁ · y ₂ + x ₂ · y ₁
5. вычислить Р · м ² + К · м + G .

Чтобы вычислить эти три произведения m -значных чисел, мы можем снова применить тот же трюк, эффективно используя рекурсию . После того, как числа вычислены, нам нужно сложить их вместе (шаги 4 и 5), что потребует примерно n операций.

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

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

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

1. вычислить b · d , назвать результат F
2. вычислить a · c , назвать результат G
3. вычислить ( a + b ) · ( c + d ), назвать результат H
4. мнимая часть результата K = H - F - G = a · d + b · c
5. действительная часть результата G - F = a · c - b · d

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

Тоом – Кук [ править ]

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

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

Методы преобразования Фурье [ править ]

Основная идея Штрассена (1968) заключается в использовании быстрого полиномиального умножения для выполнения быстрого целочисленного умножения. Алгоритм был реализован на практике, и в 1971 году Шёнхаге и Штрассен предоставили теоретические гарантии, что привело к созданию алгоритма Шёнхаге-Штрассена . ^[18] Детали следующие: Мы выбираем наибольшее целое число w , которое не вызовет переполнения во время процесса, описанного ниже. Затем мы разбиваем два числа на m групп по w битов следующим образом:

${\displaystyle a=\sum _{i=0}^{m-1}{a_{i}2^{wi}}{\text{ and }}b=\sum _{j=0}^{m-1}{b_{j}2^{wj}}.}$

Мы смотрим на эти числа как на многочлены от x , где x = 2 ^w , чтобы получить,

${\displaystyle a=\sum _{i=0}^{m-1}{a_{i}x^{i}}{\text{ and }}b=\sum _{j=0}^{m-1}{b_{j}x^{j}}.}$

Тогда мы можем сказать, что

${\displaystyle ab=\sum _{i=0}^{m-1}\sum _{j=0}^{m-1}a_{i}b_{j}x^{(i+j)}=\sum _{k=0}^{2m-2}c_{k}x^{k}.}$

Ясно, что вышеупомянутая установка реализуется полиномиальным умножением двух полиномов a и b . Решающим шагом сейчас является использование быстрого умножения Фурье многочленов, чтобы реализовать указанные выше умножения быстрее, чем за наивное время O ( m ² ).

Чтобы оставаться в модульной установке преобразований Фурье, мы ищем кольцо с корнем (2 m ) -й степени из единицы. Следовательно, мы выполняем умножение по модулю N (и, следовательно, в кольце Z / NZ ). Кроме того, N должно быть выбрано так, чтобы не было «циклического перехода», по сути, никаких сокращений по модулю N не происходило. Таким образом, выбор N имеет решающее значение. Например, это можно сделать так:

${\displaystyle N=2^{3m}+1.}$

Кольцо Z / NZ , таким образом, будет иметь корень (2 m ) -й степени из единицы, а именно 8. Кроме того, можно проверить, что c _k < N , и, таким образом, циклического перехода не произойдет.

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

В марте 2019 года Дэвид Харви и Джорис ван дер Ховен ( де ) выпустили документ, описывающий алгоритм умножения O ( n log n ) . ^{[21] [22] [23] [24]}

Использование теоретико-числовых преобразований вместо дискретных преобразований Фурье позволяет избежать проблем с ошибками округления за счет использования модульной арифметики вместо арифметики с плавающей запятой . Чтобы применить разложение, которое позволяет БПФ работать, длина преобразования должна быть факторизована для малых простых чисел и должна быть множителем N - 1 , где N - размер поля. В частности, вычисление с использованием поля Галуа GF ( k ² ), где k - простое число Мерсенна , позволяет использовать преобразование со степенью 2; например , к = 2 ³¹ - 1поддерживает преобразование размеров до 2 ³² .

Нижние границы [ править ]

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

Умножение полиномов [ править ]

Все вышеупомянутые алгоритмы умножения также могут быть расширены до умножения многочленов . Например, алгоритм Штрассена может использоваться для умножения полиномов ^{[27]. В} качестве альтернативы можно использовать метод подстановки Кронекера для преобразования задачи умножения полиномов в одно двоичное умножение. ^[28]

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

 14ac - 3ab + 2, умноженное на ac - ab + 1

 14ac -3ab 2 ac -ab 1 ———————————————————— 14a 2 c 2 -3a 2 bc 2ac -14a 2 bc 3 a 2 b 2 -2ab 14ac -3ab 2 ———————————————————————————————————————— 14a 2 c 2 -17a 2 bc 16ac 3a 2 b 2 -5ab +2 ======================================= [29]

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

 t cwt qtr 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 .

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Уоррен-младший, Генри С. (2013). Восторг хакера (2-е изд.). Эддисон Уэсли - ISBN Pearson Education, Inc.  978-0-321-84268-8.
• Савард, Джон Дж. Г. (2018) [2006]. «Продвинутые арифметические методы» . квадиблок . Архивировано 3 июля 2018 года . Проверено 16 июля 2018 .

Внешние ссылки [ править ]

Основы арифметики [ править ]

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

Расширенные алгоритмы [ править ]

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