Автор работы: Пользователь скрыл имя, 03 Апреля 2012 в 20:48, курсовая работа
обзор алгоритмов перемножения длинных чисел, анализ алгоритмов перемножения длинных чисел, разработка программы на языке C++ для перемножения длинных чисел
Введение 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
Рисунок 3.1 – Прогноз и реальные результаты
для квадратичного алгоритма
умножения
Рисунок
3.2– Прогноз и реальные результаты для
алгоритма умножения через
быстрое преобразование Фурье
Вид прогностической функции для алгоритма БПФ:
где
Вид прогностической функции для алгоритма Карацубы:
где .
Видпрогностическойфункциидляал
Сравнительный анализ алгоритмов перемножения представлен в таблице 3.1.
Таблица 3.1 – Сравнительный анализ алгоритмов
Размерность |
Умножение в столбик |
Умножение Карацубы |
БПФ-умножение |
4 |
0,00162587192476968 |
0,00240031231233407 |
0,00851884426320828 |
8 |
0,0039537219786182 |
0,0287811032922321 |
0,019130036240187 |
16 |
0,0157016656355891 |
0,0766695983688746 |
0,043332430574363 |
32 |
0,0602070790191871 |
0,202916968215336 |
0,0931004154804746 |
64 |
0,259066160759332 |
0,679030237594688 |
0,206186827629497 |
128 |
0,938712327551147 |
2,04396556955788 |
0,442499839224364 |
256 |
3,62650959264436 |
6,65423184118447 |
0,945043717386322 |
512 |
14,5613044293461 |
19,7729893308382 |
2,10876494420859 |
1024 |
57,8214991897814 |
60,6707831268008 |
4,47910052598542 |
2048 |
231,504524815153 |
186,637212268223 |
9,66548251259258 |
Полученные результаты в целом говорят о том, что в условиях современной аппаратной поддержки арифметики с плавающей точкой умножение через БПФ показывает наилучшие результаты на всех разумных размерностях применения.
Несмотря на кажущуюся однозначность полученных результаты, на сегодняшний день ответ на вопрос о выборе того или иного алгоритма для умножения длинных целых чисел не является однозначным. Ответ на него, в первую очередь, зависит от способа реализации длинной целочисленной арифметики, а также сферы применения. Так, реализация классического алгоритма Штрассена-Шёнхаге, опирающаяся на возможность быстрого выполнения модульных вычислений, становится неэффективной в случае, если основание цифр числа не представляет собой некоторую степень двойки – в этом случае более предпочтительным оказывается алгоритм БПФ-умножения.
Разработанное приложение было написано на языке программирования C++. Оно реализует три метода перемножения длинных чисел: метод Карацубы, быстрый метод Карацубы и перемножение длинных чисел «в столбик». Так как язык программирования C++ является объектно-ориентированным, разработанная программа состоит из отдельных модулей называемых функциями.
Метод Карацубы реализован в следующей функции:
void
karatsuba(int *a, int *b, int *ret, int d) {
int i;
int *ar = &a[0]; // low-order half of a
int *al = &a[d/2]; // high-order half of a
int *br = &b[0]; // low-order half of b
int *bl = &b[d/2]; // high-order half of b
int *asum = &ret[d * 5]; // sum of a's halves
int *bsum = &ret[d * 5 + d/2]; // sum of b's halves
int *x1 = &ret[d * 0]; // ar*br's location
int *x2 = &ret[d * 1]; // al*bl's location
int *x3 = &ret[d * 2]; // asum*bsum's location
if(d <= KARAT_CUTOFF) {
gradeSchool(a, b, ret, d);
return;
}
for(i = 0; i < d / 2; i++) {
asum[i] = al[i] + ar[i];
bsum[i] = bl[i] + br[i];
}
karatsuba(ar, br, x1, d/2);
karatsuba(al, bl, x2, d/2);
karatsuba(asum, bsum, x3, d/2);
for(i = 0; i < d; i++) x3[i] = x3[i] - x1[i] - x2[i];
for(i = 0; i < d; i++) ret[i + d/2] += x3[i];}
В метод в качестве аргументов посылаются: указатель на первое длинное число *a, указатель на второе длинное число *b, указатель на переменную, в которой после окончания подсчетов будет храниться результат *ret, максимально возможная длина числа d.
Быстрый метод
Карацубы реализован в функции, описание
которой схоже с обычным
void gradeSchool(int *a, int *b, int *ret, int d)
{
int i, j;
for(i = 0; i < 2 * d; i++) ret[i] = 0;
for(i = 0; i < d; i++) {
for(j = 0; j < d; j++) ret[i + j] += a[i] * b[j];
}
}
Метод перемножения в столбик реализован в следующей функции:
char * multiply(char [],char[]);
{
static char mul[MAX];
char c[MAX];
char temp[MAX];
intla,lb;
inti,j,k=0,x=0,y;
longint r=0;
long sum = 0;
la=strlen(a)-1;
lb=strlen(b)-1;
for(i=0;i<=la;i++){
a[i] = a[i] - 48;
}
for(i=0;i<=lb;i++){
b[i] = b[i] - 48;
}
for(i=lb;i>=0;i--){
r=0;
for(j=la;j>=0;j--){
temp[k++] = (b[i]*a[j] + r)%10;
r = (b[i]*a[j]+r)/10;
}
temp[k++] = r;
x++;
for(y = 0;y<x;y++){
temp[k++] = 0;
}
}
k=0;
r=0;
for(i=0;i<la+lb+2;i++){
sum =0;
y=0;
for(j=1;j<=lb+1;j++){
if(i <= la+j){
sum = sum + temp[y+i];
}
y += j + la + 1;
}
c[k++] = (sum+r) %10;
r = (sum+r)/10;
}
c[k] = r;
j=0;
for(i=k-1;i>=0;i--){
mul[j++]=c[i] + 48;
}
mul[j]='\0';
returnmul;
}
В функцию в качестве аргументов передаются два массива символов, которые являются длинными числами, разбитыми на разряды.
Помимо основных функций перемножения в программе присутствуют дополнительные функции: по вводу чисел, выводу результата, подсчету времени затраченного на вычисления методом.
voidgetNum(int *a, int *d_a)
{
int c;
int i;
*d_a = 0;
while(1) {
c = getchar();
if(c == '\n' || c == EOF) break;
if(*d_a>= MAX_DIGITS) {
fprintf(stderr, "using only first %d digits\n", MAX_DIGITS);
while(c != '\n' && c != EOF) c = getchar();
}
a[*d_a] = c - '0';
++(*d_a);
}
// reverse the number so that the 1's digit is first
for(i = 0; i * 2 < *d_a - 1; i++) {
c = a[i], a[i] = a[*d_a - i - 1], a[*d_a - i - 1] = c;
}
voidprintNum(int *a, int d)
{
int i;
for(i = d - 1; i > 0; i--) if(a[i] != 0) break;
for(; i >= 0; i--) printf("%d", a[i]);
}
voiddoCarry(int *a, int d)
{
int c;
int i;
c = 0;
for(i = 0; i < d; i++) {
a[i] += c;
if(a[i] < 0) {
c = -(-(a[i] + 1) / 10 + 1);
} else {
c = a[i] / 10;
}
a[i] -= c * 10;
}
if(c != 0) fprintf(stderr, "Overflow %d\n", c);
}
После запуска программа предлагает ввести исходные данные для вычисления, как показано на рисунке 4.2.1:
Рисунок 4.2.1 – Приглашение ввода исходных данных
После того как данные введены, начинается расчет результата по двум методам: методу Карацубы и быстрому методу Карацубы, как показано на рисунке 4.2.2:
Рисунок 4.2.2 – Результат вычисления по первым двум алгоритмам
Результат выведен в двух строках, которые состоят из полученного произведения двух длинных чисел, времени, за которое было произведено вычисление и количество итераций. Далее программа предлагает вести данные для подсчета следующим алгоритмом «в столбик», как показано на рисунке 4.2.3:
Рисунок 4.2.3 – Приглашение ввода исходных данных
Для сравнения во второй алгоритм вводятся те же числа, что и в первом. После ввода всех данных производится расчет и вывод результатов, как показано на рисунке 4.2.4:
Рисунок 4.2.4 – Вывод результатов перемножения «в столбик»
Полученные результаты в целом говорят о том, что метод Карацубы быстрее выполняет перемножение длинных чисел большой размерности, чем метод перемножения «в столбик», но числа с меньшей размерностью алгоритм перемножения «в столбик» вычисляет быстрее. Обычный метод Карацубы выполняет больше итерация, чем быстрый метод Карацубы, но за меньшее время.
Перемножение длинных
чисел можно выполнять
В данной курсовойработе рассматривались существующие алгоритмы перемножения длинных чисел такие как: алгоритм Карацубы, алгоритм перемножения длинных чисел «в столбик», алгоритм быстрого преобразования Фурье и другие.Был произведен анализ алгоритмов перемножения с точки зрения их эффективности при работе с разными числами.
На языке программирования С++ была разработана программа перемножения длинных чисел реализующая алгоритм перемножения «в столбик» и алгоритм Карацубы.
Разработанная программа способна перемножать как длинные числа (до 6000 цифр в числе) так и небольшие числа (1,2,3…)
В результате выполнения курсовой работы были выполнены следующие задачи:
Листинг программы
#include<stdlib.h>
#include <stdio.h>
#include <time.h>
#include<math.h>
#include<string.h>
#define MAX 1024
#define MAX_DIGITS 1024
#define KARAT_CUTOFF 4
voidkaratsuba(int *a, int *b, int *ret, int d);
voidgradeSchool(int *a, int *b, int *ret, int d);
voiddoCarry(int *a, int d);
voidgetNum(int *a, int *d_a);
voidprintNum(int *a, int d);
char * multiply(char [],char[]);
int
main() {
int a[MAX_DIGITS]; // first multiplicand
int b[MAX_DIGITS]; // second multiplicand
int r[6 * MAX_DIGITS]; // result goes here
intd_a; // length of a
intd_b; // length of b
int d; // maximum length
int i; // counter
clock_t start; // for timing
clock_t stop; // for timing
charsa[MAX];
charsb[MAX];
char *sc;
printf("Karatsuba's method :\n");
printf("Enter two numbers to multiply\n");
getNum(a, &d_a);
getNum(b, &d_b);
if(d_a< 0 || d_b< 0) {
printf("0\n");
exit(0);
return 0;
}
i = (d_a>d_b) ?d_a :d_b;
for(d = 1; d < i; d *= 2);
for(i = d_a; i < d; i++) a[i] = 0;
for(i = d_b; i < d; i++) b[i] = 0;
start = clock();
stop = start + CLOCKS_PER_SEC;
for(i = 0; clock() < stop; i++) {
karatsuba(a, b, r, d); // compute product w/o regard to carry
doCarry(r, 2 * d); // now do any carrying
}
start = clock() - start;
printNum(r, 2 * d);
printf(" %fms (%d trials)\n", 1000 * (double) start / CLOCKS_PER_SEC / i, i);
start = clock();
stop = start + CLOCKS_PER_SEC;
for(i = 0; clock() < stop; i++) {
gradeSchool(a, b, r, d); // compute product in old way
doCarry(r, 2 * d); // now do any carrying
}
start = clock() - start;
printNum(r, 2 * d);
printf(" %fms (%d trials)\n", 1000 * (double) start / CLOCKS_PER_SEC / i, i);
printf("Multiplication of a column:\n");
scanf("%s",sa);
scanf("%s",sb);
printf("Multiplication of two numbers : ");
sc = multiply(sa,sb);
printf("%s",sc);
scanf("%s",sa);
}
void
karatsuba(int *a, int *b, int *ret, int d) {
int i;
int *ar = &a[0]; // low-order half of a
int *al = &a[d/2]; // high-order half of a
int *br = &b[0]; // low-order half of b
int *bl = &b[d/2]; // high-order half of b
int *asum = &ret[d * 5]; // sum of a's halves
int *bsum = &ret[d * 5 + d/2]; // sum of b's halves
int *x1 = &ret[d * 0]; // ar*br's location
int *x2 = &ret[d * 1]; // al*bl's location
int *x3 = &ret[d * 2]; // asum*bsum's location
if(d <= KARAT_CUTOFF) {
gradeSchool(a, b, ret, d);
return;
}
for(i = 0; i < d / 2; i++) {
asum[i] = al[i] + ar[i];
bsum[i] = bl[i] + br[i];
}
karatsuba(ar, br, x1, d/2);
karatsuba(al, bl, x2, d/2);
karatsuba(asum, bsum, x3, d/2);
// combine recursive steps
for(i = 0; i < d; i++) x3[i] = x3[i] - x1[i] - x2[i];
for(i = 0; i < d; i++) ret[i + d/2] += x3[i];
}
void
gradeSchool(int *a, int *b, int *ret, int d) {
int i, j;
for(i = 0; i < 2 * d; i++) ret[i] = 0;
for(i = 0; i < d; i++) {
for(j = 0; j < d; j++) ret[i + j] += a[i] * b[j];
}
}
void
doCarry(int *a, int d) {
int c;
int i;
c = 0;
for(i = 0; i < d; i++) {
a[i] += c;
if(a[i] < 0) {
c = -(-(a[i] + 1) / 10 + 1);
} else {
c = a[i] / 10;
}
a[i] -= c * 10;
}
if(c != 0) fprintf(stderr, "Overflow %d\n", c);
}
void
getNum(int *a, int *d_a) {
int c;
int i;
*d_a = 0;
while(1) {
c = getchar();
if(c == '\n' || c == EOF) break;
if(*d_a>= MAX_DIGITS) {
fprintf(stderr, "using only first %d digits\n", MAX_DIGITS);
while(c != '\n' && c != EOF) c = getchar();
}
a[*d_a] = c - '0';
++(*d_a);
}
// reverse the number so that the 1's digit is first
for(i = 0; i * 2 < *d_a - 1; i++) {
c = a[i], a[i] = a[*d_a - i - 1], a[*d_a - i - 1] = c;
}
}
void
printNum(int *a, int d) {
int i;
for(i = d - 1; i > 0; i--) if(a[i] != 0) break;
for(; i >= 0; i--) printf("%d", a[i]);
}
char * multiply(char a[],char b[]){
static char mul[MAX];
char c[MAX];
char temp[MAX];
intla,lb;
inti,j,k=0,x=0,y;
longint r=0;
long sum = 0;
la=strlen(a)-1;
lb=strlen(b)-1;
for(i=0;i<=la;i++){
a[i] = a[i] - 48;
}
for(i=0;i<=lb;i++){
b[i] = b[i] - 48;
}
for(i=lb;i>=0;i--){
r=0;
for(j=la;j>=0;j--){
temp[k++] = (b[i]*a[j] + r)%10;
r = (b[i]*a[j]+r)/10;
}
temp[k++] = r;
x++;
for(y = 0;y<x;y++){