Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Дослідження швидкодії виконання мультиплікативних операцій з довгими числами
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Захист інформації
Інформація про роботу
Рік:
2009
Тип роботи:
Інші
Предмет:
Алгоритмічні основи криптології
Варіант:
2
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет ″Львівська політехніка″
Кафедра захисту інформації
Звіт
про виконання лабораторної роботи №2
з курсу “ АЛГОРИТМІЧНІ ОСНОВИ КРИПТОЛОГІЇ ”
на тему: “ Дослідження швидкодії виконання мультиплікативних операцій з довгими числами ”
Виконав: ст. гр. ІБ-44
Перевірив:
Лагун А.Е.
Львів 2009
Мета роботи: вивчити алгоритми множення та ділення довгих чисел та навчитися розробляти програмне забезпечення для реалізації цих алгоритмів на комп’ютері; дослідити швидкодію алгоритмів множення довгих чисел.
Завдання:
Домашня підготовка до роботи
1) Вивчити основні алгоритми множення та ділення довгих чисел, а також способи підвищення швидкодії виконання мультиплікативних операцій з довгими числами.
2) Скласти блок-схеми алгоритмів та програми для реалізації операцій множення (стовпчиком, швидке множення, множення з використанням перетворення Фур’є) або ділення довгих чисел. Варіанти представлення довгих чисел та способи заповнення невикористаних розрядів беруться з лабораторної роботи №1. Дані для роботи беруться за вказівкою викладача.
3) Дослідити швидкість виконання мультиплікативних операцій для розрядності довгих чисел від 50 до 200. Накреслити графіки відповідних залежностей і порівняти одержані результати.
Робота в лабораторії
1) Ввести в комп'ютер програми згідно з отриманим завданням.
2) Відлагодити програми. При необхідності скоригувати блок-схеми алгоритмів та програми у відповідності з виявленими логічними та синтаксичними помилками.
3) Остаточні версії блок-схем, програм та отримані результати занести у звіт з лабораторної роботи.
4) Здати звіт з лабораторної роботи.
Блок -схема головної програми
Output(c)
а*b=
b = Input(masivCh2)
a = Input(masivCh1)
початок
Vvedit first chuslo: a=
masivCh1
Vvedit first chuslo: b=
masivCh2
c = MultiLongLong(a,b)
кінець
Список ідентифікаторів констант, змінних і функцій, використаних у
головній програмі і підпрограмах , та їх пояснення
MaxDigit – константа що вказує на максимальну довжину масиву;
Osn – константа що вказує на основу;
Input() ввід довгого числа з клавіатури;
Output() вивід довгого числа на екран;
MultiLongLong() множення двох довгих чисел способом стовпчика;
ch – елемент типу CHAR;
masCh – массив елементів типу CHAR;
a[] – массив, що представляє довге число;
b[]– массив, що представляє довге число;
c[]– массив, що представляє довге число;
i, j, k – цілі змінні, що використовуються в циклі.
Остаточна версія програми
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MaxDigit 100
#define osn 10000
int*Input( char masCh[])
{
int *a;
char ch;
a = (int*)malloc(MaxDigit*sizeof(int));
int i = 0;
int j = 0;
for(i = 0; i < MaxDigit; 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(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;
}
}
int* MultiLongLong(int a[], int b[])
{
int *tt, *c; int j = 0, i = 0, k = 0;
tt = new int[MaxDigit]; c = new int[MaxDigit];
for(i = 0; i < MaxDigit; i++)
{
tt[i] = 0;
}
c[0] = a[0];
for(i = 1; i <= b[0]; i = i+1)
{
for(j = 1; j <= c[0]; j++ )
{
c[j] = 0;
}
for(j = 1, k = i; j <= a[0]; j = j+1, k = k+1)
{
c[j+1] = (a[j]*b[i] + c[j] + tt[k])/osn;
c[j] = (a[j]*b[i] + c[j] + tt[k])%osn;
}
if(c[j] != 0) c[0] = c[0]+1;
for(j = i, k = 1; j <= c[0]; j= j+1, k = k+1)
{
tt[j] = c[k]; } tt[0] = c[0];
}
for(i = 1; i <= c[0]; i = i+1)
{
c[i] = tt[i];
}
return c;
}
int main()
{
int *a = 0, *b =0, *c = 0;
char masCh1[100] , masCh2[100];
printf("Vvedit first chuslo: a=");
gets(masCh1);
a = Input(masCh1);
printf("Vvedit second chuslo: b=");
gets(masCh2);
b = Input(masCh2);
c = MultiLongLong(a,b);
printf("a*b=");
Output(c);
printf("\n");
system("PAUSE");
return 0;
}
Результат роботи програми
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора