МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ Лабораторна робота № 2 Варіант № 3 Перевірив: Львів – 2010 Мета роботи: вивчити алгоритми множення та ділення довгих чисел та навчитися розробляти програмне забезпечення для реалізації цих алгоритмів на комп’ютері. Завдання: 1. Вивчити основні алгоритми множення та ділення довгих чисел, а також способи підвищення швидкодії виконання мультиплікативних операцій з довгими числами. 2. Скласти блок-схеми алгоритмів та програми для реалізації операцій множення (стовпчиком, швидке множення, множення з використанням перетворення Фур’є) або ділення довгих чисел. 3. Дослідити швидкість виконання мультиплікативних операцій для розрядності довгих чисел від 50 до 200. Накреслити графіки відповідних залежностей і порівняти одержані результати. № п/п Варіант представлення числа Заповнення невикористаних розрядів Операції з довгими числами  3. 3 використати лічильник множення довгих чисел з використанням перетворення Фур’є   Список ідентифікаторів констант, змінних і функцій, використаних у головній програмі і підпрограмах та їх пояснення MaxDig – константа що вказує на максимальну довжину масиву; оsn – константа що вказує на основу; Input()- ввід довгого числа з клавіатури; Output()- вивід довгого числа на екран; fft() – знаходження ШПФ від числа; bfft()-знаходження ДПФ від числа; transf()-здійснює відповідні перенесення; scal_mult()-здійснює скалярне множення двох векторів; mult_fft()-множення двох довгих чисел; ch – елемент типу CHAR; masCh – масив елементів типу CHAR; a[] – масив, що представляє довге число; b[]– масив, що представляє довге число; c[]– масив, що представляє довге число; y[][]-двовимірний масив, що представляє довге число; y1[][]-двовимірний масив, що представляє довге число; y2[][]-двовимірний масив, що представляє довге число; i, j, k – цілі змінні, що використовуються в циклі; malloc()-функція, яка надає змінній динамічну пам’ять; N, NN, p, k, tt-змінні, що використовуються у підпрограмах. Програма #include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <conio.h> #include <math.h> #define MaxDig 100 #define osn 10000 #define Pi 3.141592653589793 void input(long a[MaxDig]); void output(long a[MaxDig]); void fft(long a[MaxDig], double y[MaxDig][2], int N); void mult_fft(long a[MaxDig], long b[MaxDig], long c[MaxDig]); void scal_mult(double y1[MaxDig][2], double y2[MaxDig][2], double y[MaxDig][2]); void transf(long c[MaxDig]); long round(double x); void bfft(double y[MaxDig][2], long c[MaxDig], int N); long int*Input( char masCh[]) { long int *a; char ch; a = (long int*)malloc(MaxDig*sizeof(int)); int i = 0; int j = 0; for(i = 0; i < MaxDig; i++) { a[i] = 0; } for(j = 0; masCh[j] != NULL; j++) { if ( isdigit(masCh[j]) ) { for (i = a[0]; i >= 1; i--) { a[i + 1] = a[i + 1] + (a[i] * 10) / osn; a[i] = a[i] * 10 % osn; } ch = masCh[j]; int a22 = atoi(&ch); a[1] = a[i+1] + a22; if (a[a[0] + 1] > 0) a[0]++; } } return a; } void Output(long int *b) { int N = 0; int NN = 1; int p; int b_Osn = b[0]; int i = 0; for(i = b[0]; i>=1 ; i--) { N = b[i]; if (N == 0) NN = 0; for (p = 1; N > 0; p = p*10) { N = N / 10; } while (osn - p != 0) { if (b[0] == i) break; printf("%c",'0'); p = p*10; } if (NN == 1) { int result = b[i]; printf("%d",result); } NN = 1; N = 0; } } void fft(long a[MaxDig], double y[MaxDig][2], int N) { int i,j,k; for(i=0;i<MaxDig;i++) for(j=0;j<2;j++) y[i][j]=0; for(j=0;j<N;j++) { for(i=0;i<a[0];i++) { y[j][0]=y[j][0]+a[a[0]-i]*cos(2*Pi*i*j/N); y[j][1]=y[j][1]+a[a[0]-i]*sin(2*Pi*i*j/N); } } } long round(double x) { if(x>=0) return ((long)(x+0.5)); else return ((long)(x-0.5)); } void bfft(double y[MaxDig][2], long c[MaxDig], int N) { int i,j; double t=0; for(i=0;i<MaxDig;i++) c[i]=0; for(j=0;j<N;j++) { for(i=0;i<N;i++) { t=t+(y[i][0]*cos(2*Pi*i*j/N)-y[i][1]*sin(-2*Pi*i*j/N)); } c[j]=round(t/N); t=0; } } void mult_fft(long a[MaxDig], long b[MaxDig], long c[MaxDig]) { double y1[MaxDig][2]; double y2[MaxDig][2]; double y[MaxDig][2]; int i; int N; i=1; do { N=pow(2,i); i++; } while((a[0]+b[0])>N); fft(a,y1,N); fft(b,y2,N); scal_mult(y1,y2,y); bfft(y,c,N); for(i=0;i<MaxDig;i++) printf("%ld ",c[i]); printf("\n"); transf(c); } void scal_mult(double y1[MaxDig][2], double y2[MaxDig][2], double y[MaxDig][2]) { int i,j; long t; for(i=0;i<MaxDig;i++) for(j=0;j<2;j++) y[i][j]=0; for(i=0;i<MaxDig;i++) { y[i][0]=y1[i][0]*y2[i][0]-y1[i][1]*y2[i][1]; y[i][1]=y1[i][0]*y2[i][1]+y1[i][1]*y2[i][0]; } } void transf(long c[MaxDig]) { int i,j; long t,Osn; Osn=pow(10,Osn); for(i=0;i<MaxDig-1;i++) { t=c[i]/Osn; c[i+1]=c[i+1]+t; c[i]=c[i]-t*Osn; } j=0; for(i=MaxDig-1;(i>=0)&&(c[i]==0);i--) j++; j=MaxDig-j; for(i=j;i>=round(j*1.0/2);i--) { t=c[i]; c[i]=c[j-i]; c[j-i]=t; } c[0]=j; } long int main() { clrscr(); long int *a = 0, *b =0, *c = 0; char masCh1[100] , masCh2[100]; printf("Vvedit pershe chuslo: a="); gets(masCh1); a = Input(masCh1); printf("Vvedit druge chuslo: b="); gets(masCh2); b = Input(masCh2); c = mult_fft(a,b); printf("a*b="); Output(c); printf("\n"); system("PAUSE"); getch(); return 0; } Результат роботи програми
Блок-схема алгоритму програми Висновок: на даній лабораторній роботі я вивчила алгоритми множення та ділення довгих чисел та навчитися розробляти програмне забезпечення для реалізації цих алгоритмів на комп’ютері.