Как реализована длинная арифметика в mpl

В.Гольдштейн

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

Тип в Borland Pascal

переменой этого типа

Longint (или Integer)

unsigned long long

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

Если вы работаете с переменной типа integer (int) и число, которое хранится в переменной становиться больше 2147483647 или меньше -2147483648, то произойдет переполнение. В C++ и на Pascal (при выключенном ключе компиляции <$Q->) программа продолжит свое выполнение, но число в переменной будет записано неверное. Если в начале программы на Pascal написать <$Q+>, то при возникновении такой ошибки программа аварийно прекратит свое выполнение. Эта возможность помогает искать ошибки связанные с переполнением. В C++ такая возможность не предусмотрена.

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

Стандартных типов для хранений чисел состоящих из 20 и более цифр в рассматриваемых нами языках программирования нет, поэтому первое, что нужно обсудить — это каким образом мы будем хранить наше число в памяти. Самый естественный и удобный способ — это хранить цифры числа в массиве. Одна цифра — это число от 0 до 9, а значит, ее можно хранить в переменной любого размера. При таком способе хранения мы можем работать с числами произвольного размера. В ячейке номер 0, будем хранить количество цифр в данном числе.

Каждый из нас уже сталкивался с подобной ситуацией еще в первом классе. Выучив таблицу сложения, мы совершенно не умели складывать двузначные числа. Для решения этой проблемы нас научили складывать числа «столбиком». Сначала складываются младшие разряды. Если сумма оказывается больше 9, то мы запоминаем «один в уме», то есть, прибавляем единицу в старший разряд. В результат записывается последняя цифра суммы.

При сложении «столбиком» двух чисел с разным количеством цифр, числа записываются так, чтобы последние цифры стояли друг под другом. Если мы храним число в массиве, то нам достаточно неудобно передвигать число с меньшим количеством знаков таким образом, чтобы младшие разряды стояли на одинаковых позициях. Кроме всего прочего результат сложения может состоять из большего количества цифр, чем каждое из слагаемых. В связи с этим нам может потребоваться записать цифру в самое начало (т. е. перед первой). Так как первая цифра записана в ячейке номер 1, то придется сдвинуть все число на одну позицию вправо и только после этого записать старшую цифру. В таком случае реализация становиться очень запутанной с большим количеством случаев и частыми сдвигами числа по массиву. Все это может привести к замедлению программы и большому количеству ошибок при реализации. Чтобы избежать этих трудностей, лучше хранить число «перевернутым», то есть, в первой ячейке массива будет записана младшая цифра (единицы), во второй будут записаны десятки и так далее. Это решает сразу все перечисленные проблемы. Во-первых, все числа теперь записаны так, что их последние цифры находятся друг под другом, во-вторых, чтобы добавить к числу цифру слева, нужно просто дописать ее в конец массива.

Перейдем от слов к делу.

Реализация сложения на языке Pascal.

thuge = array [0..DMAX] of integer;

procedure add(var a, b : thuge);

if a[0] < b[0] then a[0] := b[0];

for i := 1 to a[0] do

if a[i] >= 10 then

end else begin

if r > 0 then

Реализация сложения на языке С++.

#define DMAX 100

typedef int thuge[DMAX];

void add(thuge &a, thuge &b)<

//функция прибавляет к числу a число b

if (a[0] < b[0]) a[0] = b[0];

//складывать нужно до размера большего числа

/*r — обозначает сколько у нас «в уме»

при сложение младших цифр в уме у нас 0*/

for(int i = 1; i <= a[0]; ++i) <

//сумма очередных цифр и переноса

//случай, когда происходит перенос в следующий разряд

//случай, когда переноса не происходит

//если после сложения остался еще перенос, то нужно добавить еще одну цифру

Существуют разные системы счисления. В принципе мы можем работать в любой из них. Но нужно помнить, что перенос происходит, если сумма стала больше или равна основания системы счисления. Чтобы работать в системе счисления base, нужно заменить в программе все 10 на base. (В таком случае желательно завести константу base.) Для достижения максимальной скорости программы нужно выбирать основание системы исчисления равное некоторой степени двойки. При таком выборе можно реализовать более быстрые операции, связанные с base. Но в таком случае возникают некоторые трудности при вводе и выводе числа. Для ввода и вывода придется переводить число из одной системы счисления в другую. Это достаточно трудоемкая операция, поэтому для нас будут представлять интерес системы счисления с основанием 10K (для некоторого натурального числа K). Такая система счисления, фактически, означает, что в одной ячейке массива будет храниться не одна, а сразу K цифр. Очевидно, что операция сложения будет работать в K раз быстрее, так как в числах будет в K раз меньше цифр.

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

Реализация вычитания на языке Pascal.

procedure subtract(var a, b : thuge);

for i := 1 to a[0] do

if a[i] < 0 then

end else begin

поэтому нужно при необходимости уменьшить количество цифр>

while (a[0] > 1) and (a[a[0]] = 0) do

Реализация вычитания на языке С++.

void subtract(thuge &a, thuge &b) <

//функция вычитает из числа a число b

//r — обозначает был ли заем единицы из текущего разряда

//заем из младшего разряда отсутствует

for(int i = 1; i <= a[0]; ++i) <

//разность очередных цифр с учетом заема

//случай, когда происходит заем из следующего разряда

//случай, когда заем не происходит

/*Разность может содержать меньше цифр,

поэтому нужно при необходимости уменьшить количество цифр*/

Сложение и вычитание работает за длину наибольшего числа. Числа, которые встречаются в процессе вычислений, не превосходят по модулю 2 * base. Значит в одной ячейке массива при использовании типа longint (int) можно хранить до 9 десятичных цифр (то есть основание системы исчисления может быть до 109).

Сравнение чисел

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

function compare(var a, b : thuge) : integer;

if a[0] < b[0] then

if a[0] > b[0] then

for i:= a[0] downto 1 do

if a[i] < b[i] then

if a[i] > b[i] then

int compare(thuge &a, thuge &b) <

//сравнение по количеству цифр

/*сравнение в случае одинакового количества цифр*/

for(int i = a[0]; i >= 1; —i) <

Ввод и вывод длинного числа

Так как введенный нами тип thuge не является стандартным, то его нельзя прочитать, используя просто функцию read и выводить с помощью функции write. Для того, чтобы вывести число, записанное в десятичной системе исчисления достаточно последовательно вывести цифры последовательно, начиная со старшей. Если число записано в системе исчисления 10K, то это не совсем верно. Число 109 в 100-ричной системе исчисления состоит из двух цифр: 1 и 9. Поэтому нужно быть внимательным при выводе цифр состоящих из маленького количества цифр, так как к таким цифрам при выводе необходимо дописать лидирующие нули. Обратите внимание, что к самой первой цифре приписывать лидирующие нули не нужно.

const digit = 4;

procedure writeHuge(var a : thuge);

for i:= a[0] — 1 downto 1 do

while length(s) < digit do s := ‘0’ + s;

const char * digitFormat = «%.4d»;

/*формат вывода числа ровно из 4 цифр,

недостающие цифры дополняются нулями*/

void writeHuge(thuge &a) <

for(int i = a[0] — 1; i >= 1; —i) <

При чтении длинного числа нужно помнить, что цифры записываются в обратном порядке. Но в случае системы исчисления большей 10, «десятичные цифры» внутри цифры большей системы исчисления идут в прямом порядке. Например, число 12345678 в 100-ричной системе исчисления будет записано как: 78, 56, 34, 122.

procedure readHuge(var a : thuge);

i, j, pos : integer;

read(s); //чтение строки

fillchar(a, sizeof(a), 0);

a[0] := (length(s) — 1) div digit + 1;

for i:= 1 to a[0] do

for j:= digit — 1 downto 0 do

pos := length(s) — (i — 1) * digit — j;

if pos > 0 then

a[i] := a[i] * 10 + ord(s[pos]) — ord(‘0’);

const int digit = 4;

/*количество цифр в одной ячейке массива*/

void readHuge(thuge &a) <

char s[DMAX * digit + 1];

scanf(«%s», s);//чтение строки

memset(a, 0, sizeof(a));

int len = strlen(s);

a[0] = (len — 1) / digit + 1;

/*вычисление количества цифр в нужной системе исчисления*/

for(int i = 1; i <= a[0]; ++i) <

/*вычисление iтой цифры*/

for(int j = digit; j >= 1; —j) <

int pos = len — (i — 1) * digit — j;

/*вычисление позиции, из которой нужно дописать к iтой цифре. Помните, что массив s индексирован с 0*/

a[i] = a[i] * 10 + (s[pos] — ‘0’);

Умножение длинного числа на короткое

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

procedure multiply(var a : thuge; b : integer);

for i := 1 to a[0] do

Может потребоваться добавить несколько цифр, если число b больше base>

while r > 0 do

a[a[0]] := r mod base;

r := r div base;

void multiply(thuge &a, int b) <

//функция умножает число a на короткое число b

//r — обозначает перенос в текущий разряд

//перенос в младший разряд отсутствует

for(int i = 1; i <= a[0]; ++i) <

//произведение очередной цифры и короткого числа с учетом переноса в текущий разряд

//вычисление переноса в следующий разряд

//оставляем только часть произведения меньшую base

/*Если после умножения остался еще перенос, то нужно добавить еще цифру.

Может потребоваться добавить несколько цифр, если число b больше base*/

while (r > 0) <

Деление длинного числа на короткое

В младших классах в школе, все мы так же изучали деление столбиком. Мы будем рассматривать деление на короткое число b. При делении столбиком сначала выписывается старшая цифра, эту цифру делят на b. Частное дописывают к результату, а остаток пишут ниже. После этого к остатку приписывают следующую цифру, полученное значение делят на b. Аналогично, частное дописывают к ответу, а остаток пишут ниже. Процесс продолжается пока все цифры не будут использованы.

Остаток, к которому уже нельзя приписать цифру, будет остатком от деления.

function divide(var a : thuge; b : integer) : integer;

for i := a[0] downto 1 do

a[i] := r div b;

r := r mod b;

поэтому нужно при необходимости уменьшить количество цифр>

while (a[0] > 1) and (a[a[0]] = 0) do

int divide(thuge &a, int b) <

/*функция делит число a на короткое число b и возвращает остаток от деления*/

/*r — обозначает текущий остаток, к которому будет приписана очередная цифра*/

//изначально остаток 0

for(int i = a[0]; i >= 1; —i) <

/*цикл от старших цифр к младшим*/

//приписывание очередной цифры

//запись частного в результат

/*Частное может содержать меньше цифр,

поэтому нужно при необходимости уменьшить количество цифр*/

При умножении двух длинных чисел в столбик, первое число последовательно умножается на каждую цифру. Результат умножения на i-тую цифру прибавляется к общему результату со сдвигом на i — 1.

procedure multiplyHuge(var a, b : thuge);

fillchar(c, sizeof(c), 0); //заполнение массива 0

for i:= 1 to a[0] do

while (j <= b[0]) or (r > 0) do

inc(c[i + j — 1], a[i] * b[j] + r);

поэтому нужно прибавлять, а не присваивать>

r := c[i + j — 1] div base;

dec(c[i + j — 1], r * base);

move(c, a, sizeof(c));

//но цифр может оказаться меньше

while (a[0] > 1) and (a[a[0]] = 0) do

void multiply(thuge &a, thuge &b) <

//функция умножает число a на число b

memset(c, 0, sizeof(c)); //заполнение массива 0

/*c — результат умножения. В данном случае нельзя записывать результат в тот же массив.*/

for(int i = 1; i <= a[0]; ++i) <

for(j = 1; j <= b[0] || r > 0; ++j) <

//пока есть перенос или в b есть еще цифры

c[i + j — 1] += a[i] * b[j] + r;

/*при умножении на предыдущие цифры в c уже записано

некоторое значение,поэтому нужно прибавлять, а не

r = c[i + j — 1] / base;

c[i + j — 1] -= r * base;

//максимально возможное количество цифр в ответе

memmove(a, c, sizeof(c)); //переместим ответ в массив a

//но цифр может оказаться меньше

Выбирая основание системы исчисления, нужно добиваться максимальной скорости работы, т. е. брать как можно большую систему исчисления, с одной стороны и не забывать о том, что стандартные типы представляют ограниченное множество чисел. Например, если в вашей программе используется умножение длинных чисел то, чтобы избежать переполнения число должно (base — 1) * base должно помещаться в базовый тип. При делении или умножении на короткое число b, число b * base + base должно помещаться в базовый тип. Не трудно заметить, что деление длинного числа на короткое и умножение длинного числа на короткое работает за линейное время относительно длины числа. Умножение длинных чисел работает за время пропорциональное произведению их длин.

Квадратный корень

Вычисление квадратного корня это достаточно сложная операция. Здесь под квадратным корнем числа y мы будем подразумевать наибольшее число x, такое, что x2 <= y. Мы делаем так, потому что работаем только с целыми числами. Функция x2 монотонно возрастает, т. е. чем больше x, тем больше x2. Поэтому для нахождения квадратного корня можно применить бинарный поиск. Рассмотрим середину m отрезка [l, r], в котором мы производим поиск (изначально можно выбрать отрезок [0, y]). Если m2 > y, то дальнейший поиск нужно проводить в отрезке [l, m — 1], иначе в отрезке [m, r]. Для реализации вычисление квадратного корня нам потребуется: сложение длинных чисел, деление длинного числа на короткое (эти операции нужны для нахождения середины отрезка), а так же произведение длинных чисел (для вычисления m2) и сравнение длинных чисел. Время работы этого алгоритма можно оценить как куб длины числа y. Если длина числа y равна l, то выполниться порядка l шагов бинарного поиска, в каждом из которых будет выполнено произведение двух длинных чисел длины порядка l.

Алгоритм Евклида

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

· Оба числа четны (2n, 2k)

· Оба числа нечетны (2n + 1, 2k + 1)

· Числа разной четности (2n, 2k + 1)

В первом случае воспользуемся соображением НОД(2n, 2k) = 2 * НОД(n, k). Во втором случае НОД(2n + 1, 2k + 1) = НОД(2n — 2k, 2k + 1). В третьем случае НОД(2n, 2k + 1) = НОД(n, 2k + 1). Как мы видим при таком способе нахождения НОД нам потребуются только операции: деление на короткое (точнее на 2), вычитание, умножение на короткое (точнее на 2). Пункты 1 и 3 уменьшают хотя бы одно из чисел в 2 раза, а это может произойти не больше чем log этого числа. Log числа пропорционален его длине. Пункт 2 сразу же приводит нас в ситуацию 3, поэтому можно говорить, что каждые 2 шага алгоритма одно из чисел уменьшиться вдвое. На каждом шаге выполняется операция, требующая линейное время. Следовательно, время работы алгоритма пропорционально квадрату длины чисел.

План дальнейшего развития:

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

2) Вычитание из большего меньшее.

3) Умножение на короткое

4) Деление на короткое

5) Умножение длинных

6) *Извлечение квадратного корня двоичным поиском.

7) ** Извлечение квадратного корня за квадрат длины числа.

8) Быстрое возведение в степень.

9) Поиск наибольшего общего делителя. Алгоритм Евклида. Бинарный алгоритм поиска НОД.

6) Сложная штука, я бы поставил звездочку.

7) Этого не было в ЛКШ, хотим ли мы это? Это еще сложней. Но это иногда рассказывают в школе. Так руками корень извлекают.

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

Размещено на Allbest.ru

Подобные документы

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

курсовая работа [1,3 M], добавлен 16.01.2012

Описание алгоритма решения задачи графическим способом. Ввод элементов исходного массива в цикле. Нахождение определённых элементов. Сортировка элементов с помощью пузырькового метода. Разработка программы на языке Pascal. Поиск наибольшего элемента.

лабораторная работа [123,5 K], добавлен 15.01.2014

Модифицированный шифр Цезаря. Особенности алгоритмов Энигма и Виженера. Алгоритм рекурсивного вычисления наибольшего общего делителя. Генератор псевдослучайной последовательности. Шифрование мультипликативным ключом. Вычисление первообразного корня.

лабораторная работа [1,0 M], добавлен 04.11.2014

Составление алгоритма и программы для факторизации целого числа N с помощью ро-метода Полларда. Краткое описание данного метода: составление последовательности, вычисление разности и наибольшего общего делителя. Алгоритм работы и листинг программы.

курсовая работа [12,1 K], добавлен 24.06.2010

Разработка и реализация компьютерной игры «Змейка» с помощью языка программирования Pascal и модуля CRT. Составление общего алгоритма программы, выделение ее функциональных частей. Разработка тестовых примеров. Использование типизированных файлов.

Длинная арифметика

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

Содержание

Применение

Длинная арифметика применяется в следующих областях:

для процессоров (микроконтроллеров) низкой разрядности. Например, микроконтроллеры серии AVR имеют АЦП с разрядностью 10 бит и регистры с разрядностью 8 бит . Этого недостаточно для обработки информации с АЦП; без длинной арифметики не обойтись; . Большинство систем подписывания и шифрования данных используют целочисленную арифметику по модулю m, где m — очень большое натуральное число, не обязательно простое. Например, при реализации метода шифрованияRSA, криптосистемы Рабина или схемы Эль-Гамаля требуется обеспечить точность результатов умножения и возведения в степень порядка 10 309 ;
• математическое (см. список ПО) и финансовое ПО. Результат вычисления на бумаге должен совпадать с результатом работы компьютера с точностью до последнего разряда. В частности, калькулятор Windows (начиная с Windows 95) проводит четыре арифметических действия с намного большей точностью, чем позволяет процессор x86. Для научных и инженерных расчётов длинная арифметика применяется редко, так как ошибки во входных данных обычно намного больше, чем ошибки округления;
• стандартная тема в спортивном программировании.

Необходимые аппаратные средства для работы с длинной арифметикой

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

. Операции «сложить/вычесть с переносом», «циклический сдвиг через бит переноса».
• Косвенная адресация с автоинкрементом и автодекрементом (индексный регистр после операции увеличивается или уменьшается).
• Умножение w · w = 2w (умножение слова на слово, результат — двойное слово), деление 2w / w = w (с возможным переполнением).

Реализация в языках программирования

Языки программирования имеют встроенные типы данных, размер которых, в основном, не превышает 64 бита (около 10 19 ). Десятичная длинная арифметика была реализована в советских языках программирования АЛМИР-65 на ЭВМ МИР-1 и АНАЛИТИК на ЭВМ МИР-2. Для работы с большими числами, в современных языках программирования существует довольно много готовых оптимизированных библиотек для длинной арифметики.

Большинство функциональных языков позволяют переключаться с обычной арифметики на длинную без необходимости изменения кода арифметических расчётов. Например, Erlang и Scheme всегда представляют точные числа длинными. В Standard ML реализации всех разновидностей целых чисел определяются на основании сигнатуры INTEGER , позволяя выбирать необходимую размерность,— в том числе присутствует модуль IntInf , реализующий целые числа произвольной точности; в реализации PolyML этот модуль используется по умолчанию.

Встроенные библиотеки работы с большими числами есть в PascalABC.NET, Ruby, Python и Java.

Алгоритмы

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

Для описания алгоритмов обычно используется следующее представление целых чисел. Выбирается основание [math]\displaystyle< \beta \gt 1 >[/math] . Тогда целое число длины [math]\displaystyle< n >[/math] можно представить в виде [1] :

[math]\displaystyle < A=a_\cdot \beta^ + . + a_1 \cdot \beta + a_0, >[/math]

Базовый

Представляет собой алгоритм по школьному методу «в столбик». Занимает время [math]\displaystyle< O(n \cdot m), >[/math] где [math]\displaystyle< n, m >[/math]  — размеры перемножаемых чисел.

Алгоритм может быть представлен в виде [1] [2] :

Algorithm 1 BasecaseMultiply
Input: [math]\displaystyle< A=\sum\nolimits_^ a_i \beta^i, B=\sum\nolimits_^ b_j \beta^j >[/math]
Output: [math]\displaystyle< C=AB:=\sum\nolimits_^ c_k \beta^k >[/math]
[math]\displaystyle< 1: C \gets A\cdot b_0 >[/math]
[math]\displaystyle< 2: >[/math] for [math]\displaystyle< j >[/math] from [math]\displaystyle< 1 >[/math] to [math]\displaystyle< n-1 >[/math] do
[math]\displaystyle< 3:

C \gets C + \beta^j(A \cdot b_j) >[/math]
[math]\displaystyle< 4: return

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

Метод умножения Карацубы относится к парадигме «разделяй и властвуй». Вычислительная сложность алгоритма:

Данный алгоритм представляет собой простую реализацию [3] идеи разделения входных данных, которая стала базисной для нижеперечисленных алгоритмов. Идея заключается в разделении одной операции умножения над [math]\displaystyle< n >[/math] -значными числами на три операции умножения над числами длины [math]\displaystyle< n/2 >[/math] плюс [math]\displaystyle< O(n) >[/math] [1] .

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

C:=C_0+(C_0+C_1-s_As_BC_2) \beta^k + C_1 \beta^ <2k>>[/math]

Нужно вычислить три промежуточных коэффициента:

Алгоритм Тоома

Этот алгоритм является обобщением алгоритма Карацубы и работает быстрее. Для двух данных целых чисел [math]\displaystyle< A >[/math] и [math]\displaystyle< B >[/math] алгоритм Toom-a делит их на [math]\displaystyle< k >[/math] меньших частей, длина каждой из которых равна длине машинного слова, и производит операции над этими частями. Сложность вычисления алгоритма: [math]\displaystyle< O(n^<\ln(2k-1)/\ln(k)>). >[/math]

Алгоритм Тоома-3

Идея впервые была предложена А. Л. Тоомом в 1963 году [4] , и заключается в разделении входных данных (множителей) на 3 равные части (для простоты все части считаем равными). Toom-3 сокращает число элементарных операций умножения с 9 до 5. Сложность алгоритма [math]\displaystyle< O(n^<1.465>). >[/math]

Рассмотрим данный алгоритм на следующем примере. Пусть дано два числа [math]\displaystyle< Y >[/math] и [math]\displaystyle< X >[/math] . Пусть определены операции над числами, размер которых равен 1/3 от размеров исходных чисел (см. рисунок). Предположим также, что числа занимают равную память и делятся ровно на 3 части, в противном случае дополним оба числа нулями до необходимых размеров.

Затем происходит отображение (параметризация) этих частей на полиномы 2 степени.

Введем [math]\displaystyle< b >[/math] , по определению такую, что значения многочленов [math]\displaystyle< X(b),

Y(b) >[/math] соответственно равны входным числам [math]\displaystyle< x >[/math] и [math]\displaystyle< y >[/math] . Для битового представления чисел это число равно двойке в степени, равной длине каждой из частей в битах.

Также введем полином:

После того как будут определены элементы [math]\displaystyle< w_i >[/math]  — коэффициенты многочлена [math]\displaystyle< W(t) >[/math] , они будут использованы в целях получения [math]\displaystyle< w=W(b) >[/math] , так как [math]\displaystyle< x \cdot y=X(b) \cdot Y(b)=W(b) >[/math] . Размер коэффициентов [math]\displaystyle< w_i >[/math] в 2 раза больше (по памяти), чем разбиение [math]\displaystyle< x_i >[/math] или [math]\displaystyle< y_i >[/math] . Конечное число, равное произведению [math]\displaystyle< x \cdot y >[/math] можно найти, складывая [math]\displaystyle< w_i >[/math] со сдвигом, как показано на рисунке ниже.

Коэффициенты [math]\displaystyle< w_i >[/math] могут быть вычислены следующим образом: [math]\displaystyle< w_4=x_2 \cdot y_2, w_3=x_2 \cdot y_1+x_1 \cdot y_2,

w_2=x_2 \cdot y_0+x_1 \cdot y_1+x_0 \cdot y_2 >[/math] и так далее, но это потребует все 9 перемножений: [math]\displaystyle< x_i \cdot y_j >[/math] для i, j=0,1,2, и будет эквивалентно простому перемножению.

Вместо этого был использован иной подход. [math]\displaystyle< X(t),Y(t) >[/math] вычисляются в (1) в 5 точках при разных [math]\displaystyle< t >[/math] .

В таблице, представленной ниже, приведены значения полиномов в равенстве (1)

Параметр [math]\displaystyle< t=\infty >[/math] условный. Он означает банальное равенство коэффициентов при [math]\displaystyle< t^4 >[/math] , тем самым мы получим значение [math]\displaystyle< w_4 >[/math] сразу. Данная система линейна относительно 5 неизвестных. При её разрешении мы получаем неизвестные [math]\displaystyle< w_i >[/math] . Далее получаем значение многочлена, как было описано выше.

Алгоритм Тоома-4

Сложность алгоритма [math]\displaystyle< O(n^<1.404>). >[/math] Представляет собой 7 элементарных операций умножения. Toom-4 разделяет входные данные на 4 части.

По такому же принципу как и в Toom-3 строим два полинома:

[math]\displaystyle< X(t) >[/math] и [math]\displaystyle< Y(t) >[/math] вычисляются в 7 разных точках, также вычисляется значение [math]\displaystyle< W(t) >[/math] в этих точках.

Количество операций сложения и умножения для Toom-4 намного больше, чем для Toom-3. Но некоторые выражения встречаются по нескольку раз. Например, [math]\displaystyle< x_2+x_0 >[/math] вычисляется для [math]\displaystyle< t=1 >[/math] и для [math]\displaystyle< t=-1 >[/math] [5] .

Алгоритм Тоома для произвольного разбиения

Алгоритм Тоома для разделения входных чисел на n операндов эквивалентен описанному выше. В общем случае разделение двух одинаково длинных операндов на [math]\displaystyle< r >[/math] частей приводит к вычислению значений в [math]\displaystyle< 2r-1 >[/math] точках. В качестве точек для решения системы, обычно берут [math]\displaystyle < 0, \infty, +1, -1 , \pm 2^i, \pm 2^<-i>>[/math] .

Перемножение методом Фурье

Данный алгоритм перемножения используется для больших и очень больших чисел [6] .

Этот алгоритм перемножает два числа за время [math]\displaystyle< O(n \cdot \log n), >[/math] где [math]\displaystyle< n >[/math]  — количество значащих цифр в перемножаемых числах (предполагая их равными). Создание приписывается Кули (Coolet) и Тюки (Tukey) — 1965 г. Также есть предположения, что данный алгоритм был известен и раньше, но не имел большой важности до того как изобрели первые компьютеры. Вероятными кандидатами на авторство изобретения данного алгоритма также называют Рунг (Runge) и Кёниг (Konig) — 1924 г., а также Гаусса — 1805 г.

Пусть имеется число, представим его в виде многочлена, как мы делали ранее. Назовем этот многочлен [math]\displaystyle< A(x). >[/math] Также введем дискретное преобразование Фурье многочлена как вектор, с координатами [math]\displaystyle< \left (b_1, b_2, b_3, b_4, \dots b_\right ) >[/math] . Где [math]\displaystyle< b[i] >[/math] определены как [math]\displaystyle< w^n[i] >[/math]  — комплексный корень [math]\displaystyle< n >[/math] -ой степени из 1, не равный 1. Дело в том, что комплексный корень из 1 определен с точностью до фазового множителя, количество этих корней — [math]\displaystyle< n >[/math] . Преобразование Фурье применено для того, чтобы свертку коэффициентов многочленов [math]\displaystyle< A >[/math] и [math]\displaystyle< B >[/math] : [math]\displaystyle< (A(x) \cdot B(x)) >[/math]  — заменить на произведение их Фурье образов.

где под умножением [math]\displaystyle< F(A)\cdot F(B) >[/math] подразумевается скалярное произведение векторов.

Предположим, что [math]\displaystyle< n >[/math] есть степень двойки.

Нахождение [math]\displaystyle< F(A) >[/math] производится рекурсивным методом (разделяй и властвуй). Идея заключается в разбиении исходного многочлена [math]\displaystyle< A (x) = a_0 x_0 + a_1 x_1 + . + a_x_ >[/math] на два многочлена,

Заметим, что среди всех чисел [math]\displaystyle< \left (w^n_i\right )^2 (0 \leq i \lt n) >[/math] , только [math]\displaystyle< \frac <2>>[/math] различных. Поэтому, ДПФ [math]\displaystyle< A0 >[/math] и [math]\displaystyle< A1 >[/math] будут [math]\displaystyle< \frac <2>>[/math] -элементными. А так как ДПФ [math]\displaystyle< A0 >[/math] и [math]\displaystyle< A1 >[/math] состоит из [math]\displaystyle< \frac <2>>[/math] элементов, то комплексным корнем из 1 там будет корень степени [math]\displaystyle< \frac <2>>[/math] .

[math]\displaystyle< A(w^n_k) = A0(w^n_<2k>) + w^n_k \cdot A1(w^n_<2k>) = A0(w^\frac<2>_k) + w^n_k \cdot A1(w^\frac<2>_k), >[/math]

где [math]\displaystyle< 0 \leq k \lt n / 2 >[/math] и

Мы использовали свойства комплексных чисел: различных корней степени [math]\displaystyle< n >[/math] всего [math]\displaystyle< n >[/math] . [math]\displaystyle< w^n_<2>> = w^n_k \cdot e^ \cdot \frac<2>> = w^n_k \cdot e^ = — w^n_k >[/math] .