WikiDer > Алгоритм умножения - Википедия

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

Сеточный метод

В сеточный метод (или квадратный метод) - это вводный метод многозначного умножения, который часто преподается ученикам в Начальная школа или же Начальная школа. С конца 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, но современные процессоры оптимизировали схему для быстрого умножения с использованием более эффективных алгоритмов за счет более сложной аппаратной реализации. Человек, выполняющий долгое умножение на бумаге, запишет все произведения и сложит их вместе; ан счеты-пользователь суммирует продукты, как только вычисляется каждый из них.

Пример

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

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

Оптимизация сложности пространства

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

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

Метод основан на наблюдении, что каждая цифра результата может быть вычислена справа налево, зная только перенос из предыдущего шага. Позволять а_я и б_я быть я-я цифра операнда, с а и б дополненный слева нулями, чтобы быть длиной п, р_я быть я-я цифра результата и c_я быть переносом, сгенерированным для р_я (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 = i-m} a_ {j} b_ {k} right) / D.}$

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

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

умножать(а[1..п], б[1..q], основание)                  // Операнды, содержащие крайние правые цифры в индексе 1    малыш = 0    за ри = 1 к п + q - 1                       // Для каждой цифры результата        за би = МАКСИМУМ(1, ри - п + 1) к MIN(ри, q) // Цифры от b, которые необходимо учитывать            ай = ри − би + 1                      // Цифры из следующей "симметрии"            малыш = малыш + (а[ай] * б[би])        товар[ри] = малыш мод основание        малыш = этаж(малыш / основание)    товар[п+q] = малыш мод основание                   // Последняя цифра результата берется из последнего переноса    возвращаться товар

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

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

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

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

Решетчатое умножение

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

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

Решетчатое или решетчатое умножение алгоритмически эквивалентно длинному умножению. Это требует подготовки решетки (сетки, нарисованной на бумаге), которая направляет вычисления и отделяет все умножения от дополнения. В Европу он был завезен в 1202 г. Фибоначчис 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  1011011011001001011011001000364  383331728       101101100  10110110110010010110110010000182  766663456       10110110  10110110110010010110110010000091  1533326912       1011011  101101101100100101101100100000045  3066653824       101101  1011011011001001011011001000000022  6133307648       10110  10110110110010010110110010000000011 12266615296       1011  10110110110010010110110010000000005  24533230592       101  101101101100100101101100100000000002  49066461184       10  1011011011001001011011001000000000001  98132922368       1  1011011011001001011011001000000000000  ———————————— 1022143253354344244353353243222210110 (до переноски) 139676498390 10000010000101010111100011100111010110

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

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

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

В базе 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 * х в качестве х + х, поскольку они логически эквивалентны.

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

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

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

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

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

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

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

В 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 n}$-цифровые числа? (больше нерешенных проблем в информатике)

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

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

${ 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]

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

k₁ = c · (а + б)

k₂ = а · (d − c)

k₃ = б · (c + d)

Реальная часть = k₁ − k₃

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

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

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

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

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

1. вычислить Икс₁ · у₁, назовите результат F
2. вычислить Икс₂ · у₂, назовите результат грамм
3. вычислить (Икс₁ + Икс₂) · (у₁ + у₂), назовем результат ЧАС
4. вычислить ЧАС − F − грамм, назовите результат K; это число равно Икс₁ · у₂ + Икс₂ · у₁
5. вычислить F · м² + K · м + грамм.

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

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

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

В 1963 году Питер Ангар предложил установить м к я чтобы получить аналогичное сокращение в алгоритме комплексного умножения.^[14] Умножить (а + б я) · (c + d я), Следуй этим шагам:

1. вычислить б · d, назовите результат F
2. вычислить а · c, назовите результат грамм
3. вычислить (а + б) · (c + d), назовем результат ЧАС
4. мнимая часть результата K = ЧАС − F − грамм = а · d + б · c
5. реальная часть результата грамм − F = а · c − б · d

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

Тоом – Кук

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 14ac -3ab 2 ac -ab 1 ———————————————————— 14а2c2  -3a2bc 2ac -14a2bc 3 a2б2  -2ab 14ac -3ab 2 ——————————————————————————————————————— 14а2c2 -17a2bc 16ac 3a2б2    -5ab +2 =========================================[29]

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

    t cwt qtr 23 12 2 47 x ———————————————— 161 84 94 920 480 29 23 ———————————————— 1110 587 94 ———————————————— 1110 7 2 ================= Ответ: 1110 тонн 7 центнеров 2 кварты

Сначала умножьте четверти на 2, результат 94 записывается в первую рабочую область. Затем умножьте 12 x 47, но пока не складывайте частичные результаты (84, 480). Аналогичным образом умножьте 23 на 47. Колонка четвертей суммируется, а результат помещается во вторую рабочую область (в данном случае тривиальный ход). 94 четверти - это 23 центнера и 2 четверти, поэтому поместите 2 в ответ, а 23 в следующий столбец слева. Теперь сложите три записи в столбце cwt, получив 587. Это 29 t 7 cwt, поэтому запишите 7 в ответ и 29 в столбец слева. Теперь сложите столбец тонн. Никакой регулировки не требуется, поэтому результат просто копируется.

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

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

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

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

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

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

внешняя ссылка

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

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

Продвинутые алгоритмы

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