Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Алгоритмічні основи криптології
Група:
ІБ – 44
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет ″Львівська політехніка″
Звіт
про виконання лабораторної роботи №2
з курсу “ АЛГОРИТМІЧНІ ОСНОВИ КРИПТОЛОГІЇ ”
на тему: “ ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ ”
Мета роботи: вивчити алгоритми множення та ділення довгих чисел та навчитися розробляти програмне забезпечення для реалізації цих алгоритмів на комп’ютері; дослідити швидкодію алгоритмів множення довгих чисел.
Завдання:
Домашня підготовка до роботи
1) Вивчити основні алгоритми множення та ділення довгих чисел, а також способи підвищення швидкодії виконання мультиплікативних операцій з довгими числами.
2) Скласти блок-схеми алгоритмів та програми для реалізації операцій множення (стовпчиком, швидке множення, множення з використанням перетворення Фур’є) або ділення довгих чисел. Варіанти представлення довгих чисел та способи заповнення невикористаних розрядів беруться з лабораторної роботи №1. Дані для роботи беруться за вказівкою викладача.
3) Дослідити швидкість виконання мультиплікативних операцій для розрядності довгих чисел від 50 до 200. Накреслити графіки відповідних залежностей і порівняти одержані результати.
№
з/п
Операції з довгими числами
2
Швидке множення
Робота в лабораторії
1) Ввести в комп'ютер програми згідно з отриманим завданням.
2) Відлагодити програми. При необхідності скоригувати блок-схеми алгоритмів та програми у відповідності з виявленими логічними та синтаксичними помилками.
3) Остаточні версії блок-схем, програм та отримані результати занести у звіт з лабораторної роботи.
4) Здати звіт з лабораторної роботи.
Блок-схема алгоритму швидкого множення
Список ідентифікаторів констант, змінних і функцій, використаних у
головній програмі і підпрограмах , та їх пояснення
MaxDigit – константа що вказує на максимальну довжину масиву;
Osn – константа що вказує на основу;
Input() ввід довгого числа з клавіатури;
Output() вивід довгого числа на екран;
FastMul ()швидке множення двох довгих чисел ;
a[] – массив, що представляє довге число, множник;
b[]– массив, що представляє довге число, множник;
c[]– массив, що представляє довге число, результат;
i, j, k – цілі змінні, що використовуються в циклі.
Остаточна версія програми
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEN 100
#define OSN 10000
void InputNum(const char *str, long a[MAX_LEN])
{
int j,i=strlen(str);
char *tmp=(char*)malloc(i+1);
strcpy(tmp, str); j=0;
do
{
tmp[i]=0; i-=4; if(i<0) i=0;
sscanf(&tmp[i], "%ld", &a[MAX_LEN - ++j]);
} while (i);
while (j<MAX_LEN) a[MAX_LEN - ++j]=-1;
free(tmp);
}
void OutputNum(long a[MAX_LEN])
{
int i,fn=0;
while (fn<MAX_LEN && a[fn]==-1) fn++;
if(fn==MAX_LEN) return;
for (i=fn;i<MAX_LEN; i++)
printf((i==fn) ? "%d" : "%04d", a[i]);
}
int Less(long a[MAX_LEN], long b[MAX_LEN])
{
int i=-1;
while (++i<MAX_LEN)
if (a[i]==b[i]) continue;
else return a[i]<b[i] ? 1 : -1;
return 0;
}
int FindFirstNum(const long a[MAX_LEN])
{
int ret=MAX_LEN-1; while(a[ret]!=-1 && ret>=0) ret--; return ret+1;
}
void Div2(long a[MAX_LEN])
{
long i, fAdd=0, tmp, fNum;
fNum = FindFirstNum(a);
for(i = fNum; i<MAX_LEN; ++i)
{
tmp=a[i]+fAdd;
fAdd = (tmp & 1) ? OSN : 0;
tmp>>=1; if(tmp==0 && i==fNum && i!=MAX_LEN-1) {a[i]=-1; continue;}
a[i] = tmp;
}
}
void Mul2(long a[MAX_LEN])
{
int i=MAX_LEN; long fAdd=0,tmp;
while(a[--i]!=-1)
{
tmp=a[i]; tmp=(tmp<<1) + fAdd; fAdd=0;
if(tmp>=OSN) fAdd=1, tmp-=OSN;
a[i]=tmp;
}
if(fAdd) a[i]=fAdd, a[i-1]=-1;
}
void AddToNum(long a[MAX_LEN], const long b[MAX_LEN])
{
int to,i,j; long tmp,ta,tb,fAdd=0;
i = FindFirstNum(a), j = FindFirstNum(b);
to = (i>j) ? j : i;
for (i=MAX_LEN-1; i>=to; --i)
{
ta=a[i]; if(ta<0) ta=0;
tb=b[i]; if(tb<0) tb=0;
tmp = ta+tb+fAdd; fAdd=0;
if(tmp>=OSN) fAdd=1, tmp-=OSN;
a[i]=tmp;
}
if(fAdd) a[i]=fAdd, a[i-1]=-1;
}
void FastMul(long ta[MAX_LEN], long tb[MAX_LEN], long c[MAX_LEN])
{
long *a,*b;
int i;
if(Less(ta,tb)==1) a=tb, b=ta; else a=ta, b=tb;
for (i=0;i<MAX_LEN;i++) c[i]=-1; c[i-1]=0;
while(!(b[MAX_LEN-2]==-1 && b[MAX_LEN-1]==0))
{
if(b[MAX_LEN-1] & 1) AddToNum(c,a);
Mul2(a); Div2(b);
}
}
int SubNum(long ta[MAX_LEN], long tb[MAX_LEN], long c[MAX_LEN])
{
long *a, *b, tmp; int j,i,to=MAX_LEN-1,minus=0;
if (Less(ta,tb)==1) a=tb, b=ta, minus=1; else a=ta, b=tb;
for (i=0;i<MAX_LEN;i++) c[i]=a[i];
for (i=MAX_LEN-1; ; i--)
{
if (b[i]==-1) break;
tmp=c[i]-b[i];
if(tmp<0)
{
tmp+=OSN, j=i;
while (c[j-1]-1<0 && j>0) c[j-1]+=-1+OSN, j--;
c[j-1]--;
}
c[i]=tmp;
}
i=0; while (c[i]<=0 && i<MAX_LEN-1) c[i++]=-1;
return minus;
}
int main()
{
char *na,*szA=(char*)malloc(5000);
char *nb,*szB=(char*)malloc(5000);
long a[MAX_LEN], b[MAX_LEN], c[MAX_LEN]; int minus=0;
printf("a = "), scanf("%s", szA); na=szA;
printf("b = "), scanf("%s", szB); nb=szB;
if(*szA=='-') na++, minus=!minus;
if(*szB=='-') nb++, minus=!minus;
InputNum(na,a), InputNum(nb,b);
FastMul(a,b,c);
printf(minus ? "a * b = -" : "a * b = ");
OutputNum(c);
free(szA), free(szB);
return 0;
}
Результати виконання програми:
a = 1236673
b = 7563792
a * b = 9353937344016
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора