Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних технологій, автоматики та метрології
Факультет:
Інформаційна безпека
Кафедра:
Кафедра захисту інформації
Інформація про роботу
Рік:
2009
Тип роботи:
Лабораторна робота
Предмет:
Алгоритмічні основи криптології
Група:
ІБ-44
Варіант:
3
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ
Лабораторна робота № 2
Варіант № 3
Виконала: студентка групи ІБ-44
Перевірив:
Львів – 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;
}
Результат роботи програми
Блок-схема алгоритму програми
Висновок: на даній лабораторній роботі я вивчила алгоритми множення та ділення довгих чисел та навчитися розробляти програмне забезпечення для реалізації цих алгоритмів на комп’ютері.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора