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

 

 

 

 

 

 

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

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

 

 

 

СОДЕРЖАНИЕ

 

Введение 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).

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