Задача перемножения длинных чисел

 

 

 

 

 

 

Задача перемножения длинных чисел

Курсовая работа

 

 

 

СОДЕРЖАНИЕ

 

Введение 3

1 Представление длинных чисел 4

1.1 Представление длинных чисел в компьютере 4

1.2 Примеры представления длинных чисел на С++ 4

2 Обзор существующих алгоритмов перемножения длинных чисел 8

2.1 Умножение «столбиком» 8

2.2 Метод Карацубы 9

2.3 Метод Тоома – Кука третьего порядка 10

2.4 Метод Ш. Винограда 11

2.5 Алгоритмы быстрого умножения целых чисел многократной точности 11

2.6 Дискретное преобразование Фурье 12

2.7 Быстрое преобразование Фурье 13

2.8 Обратное быстрое преобразование Фурье 15

3 Анализ алгоритмов перемножения 17

4 Разработка программы 22

4.1 Описание структуры программы 22

4.2 Описание работы программы 25

Заключение 28

Список использованных источников 29

Приложение 30

 

Введение

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

Существуют методы, позволяющие  значительно сократить затраты времени и ресурсов при работе с длинными числами. Для операции умножения используют алгоритмы быстрого умножения полиномов. Наиболее широкое применение получили алгоритмы FastFourierTransforms (сокращенно FFT) и умножение Карацубы.

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

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

1. обзор алгоритмов перемножения длинных чисел;
2. анализ алгоритмов перемножения длинных чисел;
3. разработка и реализация программы на языке C++ для перемножения длинных чисел;
4. тестирование и анализ программы для перемножения длинных чисел.

1. Представление длинных чисел

1. Представление длинных чисел в компьютере

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

30! = 265252859812191058636308480000000,

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

Числа, для представления  которых в стандартных компьютерных типах данных не хватает количества двоичных разрядов, называются "длинными".

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

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

2. Примеры представления длинных чисел на С++

Обычно, неотрицательное  целое число N длины n представляется в виде

 

где BASE – основание системы  счисления, все коэффициенты 0 ≤ < BASE.

Например, число в этой интерпретации будет иметь вид

= 5 + 4*10 + 3*+ 2*+ 1*( BASE=10 ).

Длинное число хранится в  массиве, где i-й элемент соответствует  коэффициенту числа при.

В качестве примера, рассматривается массив для: (5, 4, 3, 2, 1). Как видно, цифры хранятся в обратном порядке. Это – некая “заготовка на будущее”: дело в том,что реализации алгоритмов при этом имеют более естественный вид.Такое представление N является частным случаем многочлена n-й степени

P(x) = ,

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

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

Основание системы счисления BASE обычно зависит от максимального  размера базового типаданных на компьютере, и выбирается, исходя из следующих соображений:

• Основание должно подходить под один из базовых типов данных
• BASE должно быть как можно больше, чтобы уменьшить размер представлениядлинного числа и увеличить скорость операций с ними, но достаточно малого размера,чтобы все операции с коэффициентами использовали базовый тип данных.
• Для удобства можно выбрать BASE как степень 10 (вывод информации, отладка).BASE - степень двойки позволяет проводить быстрые операции на низком уровне.

В качестве разумного компромисса  можно взять

#define BASE 10000

Это позволит понять функции  в общем виде, не вдаваясь в тонкости битовых операций.

Число 20! = 243,2902,0081,7664,0000 представляется по этому основанию как

20! = 0 + 7664*BASE+ 81*+ 2902*+ 243*.

Объявляется класс длинного числа с простейшими операциями:

classBigInt {

public:

// к этим членам можно  закрыть доступ

ulong Size, SizeMax; // Size – текущаядлина

// SizeMax – максимальная  длина

short *Coef; // Массив коэффициентов

// в этом случае здесь  также должны быть описаны  дружественные функции

// операций над большими  числами, которые будут разобраны  ниже.

BigInt();

BigInt(ulong);

BigInt(constBigInt&);

virtual ~BigInt();

void zero(); // Обнулитьчисло

void update();

BigInt& operator=(constBigInt&);

operatorlong(); // ОператорпреобразованияBigIntктипуlong

};

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

BigInt::BigInt() {

SizeMax = Size = 0; // ОбъявлениевидаBigInt A;

Coef = NULL; // Создается полностью  пустое число

}

BigInt::BigInt(ulongMaxLen) {

Coef = new short[MaxLen]; // ОбъявлениевидаBigInt A(10);

SizeMax = MaxLen; // Выделяет память  под MaxLen цифр

Size = 0;

}

BigInt::BigInt(constBigInt&A) { // Конструкторкопирования

SizeMax = A.SizeMax; // Создает B, равное A

Size = A.Size;

Coef = new short[SizeMax];

for(ulong i=0; i<SizeMax; i++) Coef[i] = A.Coef[i];

}

BigInt::~BigInt() {

deleteCoef;

}

voidBigInt::zero() { // A.zero() – обнулитьчисло

for(ulong i=0; i<SizeMax; i++) Coef[i]=0;

Size=1;

}

Оператор long вычисляет число  в “обычном виде” 

N = Coef[0] + Coef[1]BASE + ... + Coef[n-1],

он может быть весьма полезен  при отладке, когда BASE = 10, а числа  небольшие.

BigInt::operatorlong() {

longtmp=0; // при вычислениях  может произойти переполнение

for(ushort i=0; i<Size; i++) tmp += Coef[i]*(long)pow( BASE, (real)i);

returntmp;

}

Несколько более интересен  оператор присваивания. Для его правильной работы необходимо разобрать случай A=A и при необходимости выделить дополнительную память под коэффициенты.

inlineBigInt&BigInt::operator=(constBigInt&A) {

const short *a = A.Coef;

if (this == &A) return *this; // Еслиприсваиваниевида A=A - выйти

if( SizeMax<A.Size ) { // Если размера  не хватает – переинициализация

if (Coef) delete Coef;

Coef = new short[A.Size];

SizeMax = Size = A.Size;

} else Size = A.Size;

for(ulong l=0; l<Size; l++)

Coef[l] = a[l];

return *this;

}

Возвращение this необходимо, чтобы работали присваивания вида A=B=C (они интерпретируются как A=(B=C) ).

2. Обзор существующих алгоритмов перемножения длинных чисел

1. Умножение «столбиком»

Предположим, что мы имеем  дело с неотрицательными целыми числами.

Алгоритм 1.Умножение неотрицательных целых чисел. Заданы два целых числа по основанию b - первое число , второе число . Алгоритм вырабатывает их произведение.

Шаг 1.Начальная установка.

Установить все значения равным нулю.

Установить j=m (индекс цифры второго сомножителя).

Шаг 2.Учет нулевого множителя.

Если , установить и передать управление на Шаг 6.

Шаг 3.Начальная установка для индекса цифры первого сомножителя.

Установить i=n (индекс цифры второго числа), k=0(цифра переноса).

Шаг 4.Умножить и сложить.

Установить , затем установить .

Шаг 5.Цикл по индексу i.

Уменьшитьi на единицу. Если i>0, то вернуться в Шаг 4; в противномслучае установить .

Шаг 6.Цикл по индексу  j.

Уменьшить jна единицу. Если j>0, то вернуться в Шаг 2; в противном случае закончить выполнение алгоритма.

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

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

Умножение «в столбик» длинных  чисел С = А*В длины n цифр

1) C:= 0; (достаточно обнулить n младших цифр)

2) для i = 0 … n-1 выполнить  шаги 3-8;

3) d:=0;

4) для j = 0 … n-1 выполнить  шаги 3-5;

5) T: =Ci+j + Ai*Bi +d;

6) Ci+j: = LODIGIT(T);

7) d := HIDIGIT(T);

8) Ci+n: =d;

9) конец.

Результат операции умножения  в общем случае в 2 раза длиннее  сомножителей, то есть имеет длину 2n цифр. Нетрудно видеть, что описанный алгоритм требует выполнения n операций умножения и еще некоторого количества операций сложения. И именно так умножали люди с давних времен, пока 39 лет назад московским математиком А.А. Карацубой не было совершено неожиданное открытие. Он придумал куда более эффективный метод.

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

2. Метод Карацубы

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

При этом получим 

,

где k=max(m,n)/2, m - число цифр по основаниюb в числеA, а n- число цифр по основаниюb в числе B.

Теперь произведение C=A*B можно вычислить с помощью лишь трех умножений целых чисел длиной kили меньше плюс несколько сдвигов и сложений, используя формулу

,

где  .

Выигрыш в трудоемкости получается за счет замены «трудоемких» операций умножения операциями сложения и сдвига.

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

Алгоритм 4.Умножение двух целых чисел по методу А. Карацубы. Пусть и A и B– два целых числа. Ищется число C=A*B.

Шаг 1.Произведение двух «коротких» чисел. Если числа  A и Bпредставляются с помощью чисел длиной меньше Nцифр (N - число цифр для обменной точкиалгоритма, когда классический алгоритм становится менее эффективным чем быстрый алгоритм), то ищется произведение чисел  A и Bклассическим способом.

Шаг 2.Соревнование в скорости с классическим алгоритмом. Разбить каждое из сомножителей на две части, старшую и младшую

.

После этого вычислить  частичные произведения

,, ,

рекурсивно обращаясь  к данному алгоритму.

Шаг 3.Получить результат C=A*B, комбинируя для частичных результатов операции сложения и сдвига. Конец алгоритма.

Теорема.Трудоемкость рассмотренного алгоритма умножения можно оценить величиной , гдеn - количество цифр в перемножаемых числах.

3. Метод Тоома – Кука третьего порядка

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

Метод Тоома – Кука третьего порядка позволяет свести исходную задачу к пяти умножениям в три  раза меньшей разрядности, одному короткому  умножению на 3, двум операциям деления на 3, 13 операциям сдвига и 25 операциям суммирования и разности. Кроме 5 произведений, все остальные операции обладают линейной трудоемкостью. Рекурсивная реализация данного метода дает асимптотическую сложность O(n1,465).

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

4. Метод Ш. Винограда

Вышеприведенные методы ориентированы  на реализацию умножения в тех  случаях, когда операнды обладают близкой  разрядностью. Однако существуют методы, ориентированные именно на реализацию умножения в случае операндов различного размера. Одним из таких методов является метод Ш. Винограда. Данный метод ориентирован на умножение в тех случаях, когда один операнд на треть короче другого. Метод Ш. Винограда позволяет осуществить исходное умножение c помощью десяти операций суммирования, четырех умножений с операндами половинного размера по сравнению с исходным коротким множителем и двух сдвигов.

5. Алгоритмы быстрого умножения целых чиселмногократной точности

Приведенный выше алгоритм представляет собой просто первый (r=1) модифицированный алгоритм из бесконечной последовательности алгоритмов

В алгоритме разбиваем сомножители на r частей таким образом, что

, ,

где k=max(m,n)/(r+1).

Нетрудно получить обобщение  вычислительных формул для предлагаемых алгоритмов.

Теорема. Трудоемкость рассмотренного алгоритма умножения можно оценить величиной

,

гдеn - количество цифр в перемножаемых числах.

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

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

6. Дискретное преобразование Фурье

Изобретение Быстрого преобразования Фурье приписывается Кули (Coolet) и  Таки (Tukey) — 1965 г. На самом деле быстрое преобразование Фурье неоднократно изобреталось до этого, но важность его в полной мере не осознавалась до появления современных компьютеров. Некоторые исследователи приписывают открытие быстрого преобразования Фурье Рунге (Runge) и Кёнигу (Konig) в 1924 г. Наконец, открытие этого метода приписывается ещё Гауссу (Gauss) в 1805 г.

Пусть имеется многочлен  -ой степени:

 

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

Из теории функций комплексного переменного известно, что комплексных корней -ой степени из единицы существует ровно . Обозначив эти корни через , известно, что . Кроме того, один из этих корней (называемый главным значением корня -ой степени из единицы) таков, что все остальные корни являются его степенями: .

Тогда дискретным преобразованием Фурье (ДПФ) (discreteFouriertransform, DFT) многочлена (или, что то же самое, ДПФ вектора его коэффициентов ) называются значения этого многочлена в точках , т.е. это вектор:

DFT((A(

Аналогично определяется и обратное дискретное преобразование Фурье (InverseDFT). Обратное дискретное преобразование Фурье для вектора значений многочлена — это вектор коэффициентов многочлена :

InverseDFT(

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

Рассмотрим применение дискретного  преобразования Фурье для умножения полиномов. Даны два многочлена и . Посчитав дискретное преобразование Фурье для каждого из них: и — это два вектора-значения многочленов.

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

 

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

 

Наконец, применяя обратное дискретное преобразование Фурье, получается:

 

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

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

7. Быстрое преобразование Фурье

Быстрое преобразование Фурье (fastFouriertransform) — это метод, позволяющий вычислять ДПФ за время . Этот метод основывается на свойствах комплексных корней из единицы (а именно, на том, что степени одних корней дают другие корни).

Основная идея быстрого преобразования Фурье заключается в разделении вектора коэффициентов на два вектора, рекурсивном вычислении дискретного преобразования Фурье для них, и объединении результатов в одно быстрое преобразование Фурье.

Итак, пусть имеется многочлен  степени , где — степень двойки, и :

 

Необходимо разделить его на два многочлена, один — с чётными, а другой — с нечётными коэффициентами:

 

 

Нетрудно убедиться, что:

 

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

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

Во-первых, вспоминая (1), сразу получаются значения для первой половины коэффициентов:

-1.

Для второй половины коэффициентов  после преобразований также получается простая формула:

=

(Здесь использовалось (1), а также тождествами , .)

Итак, в результате получились формулы для вычисления всего вектора :

1,

 

(эти формулы, т.е. две  формулы вида  и , иногда называют "преобразование бабочки" ("butterflyoperation"))

8. Обратное быстрое преобразование Фурье

Итак, пусть дан вектор — значения многочлена степени в точках . Требуется восстановить коэффициенты многочлена. Эта известная задача называется интерполяцией, для этой задачи есть и общие алгоритмы решения, однако в данном случае будет получен очень простой алгоритм (простой тем, что он практически не отличается от прямого быстрого преобразования Фурье).

Дискретное преобразование Фурье  можно записать, согласно его определению, в матричном виде:

Тогда вектор можно найти, умножив вектор на обратную матрицу к матрице, стоящей слева (которая называется матрицей Вандермонда):

Непосредственной проверкой  можно убедиться в том, что  эта обратная матрица такова:

Таким образом, получаем формулу:

Сравнивая её с формулой для :

 

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

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

3. Анализ алгоритмов перемножения

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

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

Под алгоритмом  понимается правило или способ вычисления, не формализуя это понятие. Считать, что числа записаны в двоичной системе счисления, знаки которой 0 и 1 называются битами.

Определение 1.Запись знаков 0, 1 , плюс, минус, скобка; сложение, вычитание и умножение двух битов называется одной элементарной или битовой операцией.

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

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

Первые постановки задач  о сложности вычислений (1956 г.) принадлежат А. Н. Колмогорову, который в то же время подчёркивал, что «цикл моих работ по теории информации был создан под большим влиянием публикаций Норберта Винера и Клода Шеннона».

Прежде чем ввести понятие  сложности вычисления, необходимо определить, что значит вычислить функцию в заданной точке. Рассмотрим наиболее простой пример вычисления вещественной функции y = f(x) вещественного переменного x, a ≤ x ≤ b. Пусть f(x) на (a,b) удовлетворяет условию Липшица порядка α, 0 < α <1, так что при x1, x2 ∊ (a,b):

|f(x1) – f(x2)| ≤ |x1 – x2|α. 

Пусть n — натуральное  число.

Определение 2. Вычислить функцию y = f(x) в точке x = x0 ∊ (a,b) с точностью до n знаков, значит найти число A, что

|f(x0) – A| ≤ 2–n.

Определение 3. Количество битовых операций, достаточное для вычисления функции f(x) в точке x = x0 с точностью до n знаков посредством данного алгоритма, называется сложностью вычисления f(x) в точке x = x0.

Таким образом, сложность  вычисления f(x) в точке x = x0 есть функция n; а также f(x) и x = x0. Эту функцию  обозначают символом

Sf(n) = Sf,x0(n).

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

Вопрос о поведении Sf(n) при n → ∞ для класса функций  или конкретной функции f, был впервые поставлен А. Н. Колмогоровым около 1956 года. Поскольку при вычислениях в первую очередь используются четыре арифметических действия: сложение, вычитание, умножение и деление, то прежде всего нужно знать количество битовых операций, достаточное для выполнения этих действий. Из определений 2 и 3 следует, что числа x0 и A можно представить в виде целой части и n двоичных знаков после запятой, т.е.

A = [A] + 0,ν1ν2ν3 ... νn,

x0 = [x0] + 0,μ1μ2μ3 ... μn,

где νj, μj = 0 или 1, j = 1, 2, ... , n.

Так как целые части [A], [x0] — фиксированные величины, а n → ∞, то действия производятся по существу с n-значными числами. Отсюда прежде всего  возникает вопрос о сложности  вычисления суммы, разности, произведения и частного двух n-значных чисел a и b.

Функция сложности умножения  получила специальное обозначение M(n).

Перемножая два n-значных  числа обычным школьным способом «в столбик», при этом фактически складывается n n-значных чисел. Так что для сложности этого «школьного» или «обычного» метода мы имеем оценку сверху M(n) = O(n2).

В 1956 г. А. Н. Колмогоров высказал гипотезу, что нижняя оценка M(n) при  любом методе умножения есть также  величина порядка n2 (так называемая «гипотеза n2 Колмогорова»). На правдоподобность «гипотезы n2» указывал тот факт, что метод умножения «в столбик» известен не менее 4-х тысячелетий (например, этим методом пользовались шумеры), и если бы был более быстрый метод умножения, то он, вероятно, уже был бы найден.

В 1960 А. А. Карацубанашёл новый метод умножения двух n-значных чисел с оценкой сложности

M(n) = O(nlog23),   log23 = 1,5849... ,

и тем самым опроверг «гипотезу n2». Этот метод впоследствии был  назван «DivideandConquer» («Разделяй и властвуй»); другие, используемые в настоящее время названия этого метода — «BinarySplitting», «Принцип Дихотомии» и т. п.

С момента появления «DivideandConquer»  начала развиваться теория быстрых  вычислений. Исследования с целью  поиска алгоритма умножения со сложностью, близкой к оптимальной, были продолжены рядом авторов (среди них были Тоом, Кук, Шёнхаге), и в 1971 г. Шёнхаге и Штрассен построили алгоритм с наилучшей на настоящее время оценкой для M(n),

M(n) = O(n log n loglog n).

При построении этого алгоритма  кроме "DivideandConquer" они использовали идею выполнения арифметических действий по модулю чисел Ферма 22n+ 1, а также быстрое преобразование Фурье.

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

В результате теоретического анализа были выведены функции трудоемкости для алгоритмов, выражающие зависимость количества базовых операций от длины входа. Если решать, что время решения задачи прямо пропорционально количеству затрачиваемых базовых операций, то  эмпирическим путем найдя среднее время на базовую операцию можно построить функции временных прогнозов. Функцию временного прогноза для алгоритма перемножения «в столбик» можно увидеть на рисунке 3.1, функцию временного прогноза для алгоритма быстрого преобразования Фурье можно увидеть на рисунке 3.2.