Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Алгоритмічні основи криптології
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет ″Львівська політехніка″
Звіт
про виконання лабораторної роботи №2
з курсу “ АЛГОРИТМІЧНІ ОСНОВИ КРИПТОЛОГІЇ ”
на тему: “ ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ ”
Мета роботи: вивчити алгоритми множення та ділення довгих чисел та навчитися розробляти програмне забезпечення для реалізації цих алгоритмів на комп’ютері; дослідити швидкодію алгоритмів множення довгих чисел.
Завдання:
Домашня підготовка до роботи
1) Вивчити основні алгоритми множення та ділення довгих чисел, а також способи підвищення швидкодії виконання мультиплікативних операцій з довгими числами.
2) Скласти блок-схеми алгоритмів та програми для реалізації операцій множення (стовпчиком, швидке множення, множення з використанням перетворення Фур’є) або ділення довгих чисел. Варіанти представлення довгих чисел та способи заповнення невикористаних розрядів беруться з лабораторної роботи №1. Дані для роботи беруться за вказівкою викладача.
3) Дослідити швидкість виконання мультиплікативних операцій для розрядності довгих чисел від 50 до 200. Накреслити графіки відповідних залежностей і порівняти одержані результати.
№
з/п
Операції з довгими числами
2
Швидке множення
Робота в лабораторії
1) Ввести в комп'ютер програми згідно з отриманим завданням.
2) Відлагодити програми. При необхідності скоригувати блок-схеми алгоритмів та програми у відповідності з виявленими логічними та синтаксичними помилками.
3) Остаточні версії блок-схем, програм та отримані результати занести у звіт з лабораторної роботи.
4) Здати звіт з лабораторної роботи.
Блок -схема головної програми
Блок-схема алгоритму швидкого множення
Список ідентифікаторів констант, змінних і функцій, використаних у
головній програмі і підпрограмах , та їх пояснення
MaxDigit – константа що вказує на максимальну довжину масиву;
Osn – константа що вказує на основу;
Input() ввід довгого числа з клавіатури;
Output() вивід довгого числа на екран;
Quick()швидке множення двох довгих чисел ;
ch – елемент типу CHAR;
masCh – массив елементів типу CHAR;
a[] – массив, що представляє довге число;
b[]– массив, що представляє довге число;
c[]– массив, що представляє довге число;
i, j, k – цілі змінні, що використовуються в циклі.
Остаточна версія програми
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <ctype.h>
#define MaxDig 100
#define Osn 10000
using namespace std;
long int *Input( char masivCh[])
{
long int *a,a22;
char ch;
a = (long int*)malloc(MaxDig*sizeof(int));
int i=0, j=0;
for(i=0; i<MaxDig; i++)
{
a[i]=0;
}
a[0]=1;
for(j=0; masivCh[j] != NULL; j++)
{ch=masivCh[j];
if (isdigit(ch))
{
for (i=a[0]; i>=1; i--)
{
a[i+1]=a[i+1]+(a[i]*10)/Osn;
a[i]=a[i]*10%Osn;
}
a22=atoi(&ch);
a[1]=a[i+1]+a22;
if (a[a[0]+1]>0)
a[0]++;
}
}
return a;
}
void Output(long int *b)
{
long int result;
int k=0, r=1,p,b_Osn=b[0],i=0;
for(i=b[0]; i>=1; i--)
{
k=b[i];
if (k==0)
r=0;
for (p=1; k>0; p=p*10)
{
k=k/10;
}
while (Osn-p!=0)
{
if (b[0]==i)
break;
printf("%c",'0');
p=p*10;
}
if (r==1)
{
result=b[i];
printf("%d",result);
}
r=1; k=0;
}
}
bool parne(long int* b)
{
bool c;
if(b[b[0]]%2==0)
c=true;
else
c=false;
return c;
}
long int* dil(long int*b)
{
long int Ost,B;
int i;
Ost=0;
for(i=1; i<MaxDig;i++)
{B=Ost*10+b[i];
b[i]=B/2;
Ost=B%2;
}return b; }
bool more(long int* a,long int* b)
{int i;
if(a[0]<b[0]) return false;
else if (a[0]>b[0])return true;
else
{i=a[0];
while(i>0 && a[i]==b[i]) i--;
if (i==0)return false;
else if (a[i]>b[i])return true;
else return false; } }
int chekEquality(long int* a, long int* b)
{
int e;
if (a[0]==b[0])
{e=1; }
else
{e=0; }
for (long i=a[0]; i>=1; i--)
{if (a[i]==b[i])
{continue; }
else
if (a[i]==b[i])
{e=1; }
else
{e=0; } }
return e; }
long int* Sub(long int a[MaxDig],int sp=0)
{int i,j,e;
int minus=0;
long int* ta,*tb,*c,*b;
c=(long int*)malloc(MaxDig*sizeof(int));
b=(long int*)malloc(MaxDig*sizeof(int));
for (i=0; i<MaxDig;i++)
b[i]=0; b[0]=1; b[1]=1;
if(more(a,b)==0)
{ minus=0;ta=a;
tb=b; } else
{e=chekEquality(a,b);
if (e)
{for(i=0;i<MaxDig;i++)
c[i]=0; }
Else {
minus=1;
ta=b;
tb=a; } }
for(i=0;i<MaxDig;i++)
c[i]=a[i];
for (i=1;i<=b[0];i++)
c[i+sp]-=b[i];
j=i;
while(c[j+sp]<0 && j<=c[0])
{ c[j+sp]+=Osn;
c[j+sp+1]--;
j++; }
if(minus==1)
cout<<"-";
i=c[0];
while (i>1 && c[i]==0)i--;
c[0]=i; return c; }
long int *Sum(long int a[], long int b[])
{
int k,i;
long int *c;
c=(long int*)malloc(MaxDig*sizeof(int));
for( i=0; i<MaxDig; i++)
{c[i]=0; }
if(a[0]>b[0])
{k=a[0];
} else
{k=b[0];
} for(i=1; i<=k; i++)
{c[i+1]=(c[i]+a[i]+b[i])/Osn;
c[i]=(c[i]+a[i]+b[i])%Osn; }
if (c[k+1]==1)
{c[0]=k+1; }
Else { c[0]=k;
} return c; }
long int* Quick(long int* a,long int* b)
{
int i;
long int *s;
s=(long int*)malloc(sizeof(int)*MaxDig);
for(i=0;i<MaxDig;i++)
s[i]=0;
s[0]=1;
if(b[0]>0 && b[0]!=1)
{if(parne(b))
{a=Sum(a,a);
b=dil(b);
}
else
{s=Sum(s,a);
b=Sub(b);
}
}
else
return s;
}
int main()
{
long int *a=0,*c=0,*b=0;
for(;;) {do {
print(); s = getch(); printf("\n");
} while(!isdigit(s));
switch(s)
case '1': printf("multiplication\n\n");
char masivCh1[100];char masivCh2[100];
cout<<"enter first long number :";
cin>>masivCh1;
a = Input(masivCh1);
cout<<"\n enter second long number :";
cin>>masivCh2;
b = Input(masivCh2);
c=Quick(a,b);
Output(c);
break;
case '0': exit(0); break; }
printf("\n\n"); }
return 0; } }
Результати виконання програми:
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора