Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКТА
Факультет:
ЗІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Алгоритмічні основи криптології
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ, МОЛОДІ ТА СПОРТУ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ІКТА
З В І Т
до лабораторної роботи №2
з курсу: «Алгоритмічні основи криптології»
на тему: «ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ»
Варіант № 9
Львів – 2013р.
Мета роботи - вивчити алгоритми множення та ділення довгих чисел та навчитися розробляти програмне забезпечення для реалізації цих алгоритмів на комп’ютері; дослідити швидкодію алгоритмів множення довгих чисел.
Завдання
2.1. Домашня підготовка до роботи
1) Вивчити основні алгоритми множення та ділення довгих чисел, а також способи підвищення швидкодії виконання мультиплікативних операцій з довгими числами.
2) Скласти блок-схеми алгоритмів та програми для реалізації операцій множення (стовпчиком, швидке множення, множення з використанням перетворення Фур’є) або ділення довгих чисел. Варіанти представлення довгих чисел та способи заповнення невикористаних розрядів беруться з лабораторної роботи №1. Дані для роботи беруться за вказівкою викладача.
3) Дослідити швидкість виконання мультиплікативних операцій для розрядності довгих чисел від 200 до 500. Накреслити графіки відповідних залежностей і порівняти одержані результати.
2.2. Робота в лабораторії
1) Ввести в комп'ютер програми згідно з отриманим завданням.
2) Відлагодити програми. У випадку необхідності скоригувати блок-схеми алгоритмів та програми у відповідності з виявленими логічними та синтаксичними помилками.
3) Остаточні версії блок-схем, програм та отримані результати занести у звіт з лабораторної роботи.
4) Здати звіт з лабораторної роботи.
Блок-схеми алгоритму програми
Блок-схема алгоритму швидкого множення довгих чисел.
Список ідентифікаторів констант, змінних, функцій,
використаних у блок-схемі алгоритму і програмі,
та їх пояснення
a, b, c, d – одновимірні масиви типу integer.
s – змінна типу string, що використовується для зчитування довгих чисел з файлів;
Vvedennia_Chysla – метод який не має аргументів, забезпечує зчитування довгих чисел з файлів;
Vyvedennia_Chysla(int[] d, string st)– метод який реалізовує виведення довгого числа d, а також він виводить на екран значення змінної st;
Rivnist(int[] q1, int[] q2)- метод, який перевіряє рівність двох довгих чисел q1 s q2, даний метод повертає значення типу boolean(true або false);
Bilshe(int[] q1, int[] q2) - метод, що перевіряє чи число q1 є більшим за q2, повертає значення типу bool;
Dodavannia(int[] q1, int[] q2) - метод, що здійснює додавання двох довгих чисел q1 і q2.
Текст програми
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication3
{
class Program
{
static void Main(string[] args)
{
dovge_Chyslo t = new dovge_Chyslo();
Console.ReadLine();
}
}
class dovge_Chyslo
{
string s;
bool flag;
int[] a, b, c, d;
int i, j, n, g, osn, k, temp, f;
public dovge_Chyslo()
{
flag = true;
k = 4;
osn = 10000;
Zchytuvannia_a_b();
Shvydke_mn(a, b);
Vyvedennia_Chysla(d, "a*b: ");
}
void Vvedennia_Chysla()
{
FileStream stream = new FileStream(s + ".txt", FileMode.Open);
StreamReader reader = new StreamReader(stream);
s = reader.ReadToEnd();
stream.Close();
n = s.Length / k;
g = s.Length % k;
if (g != 0) n++;
c = new int[n + 1];
c[0] = n;
s.ToCharArray();
for (i = s.Length - 1; i >= g; i -= k)
{
for (j = 0, temp = 0; j < k; j++)
temp += (Convert.ToInt32(s[i - j]) - 48) * Convert.ToInt32(Math.Pow(10, j));
c[n] = temp;
n--;
}
if (g != 0)
{
for (j = 0, temp = 0; j < g; j++)
temp += (Convert.ToInt32(s[g - j - 1]) - 48) * Convert.ToInt32(Math.Pow(10, j));
c[n] = temp;
}
}
void Zchytuvannia_a_b()
{
s = "a";
Vvedennia_Chysla();
a = new int[c[0] + 1];
for (i = 0; i < c[0] + 1; a[i] = c[i], i++) ;
s = "b";
Vvedennia_Chysla();
b = new int[c[0] + 1];
for (i = 0; i < c[0] + 1; b[i] = c[i], i++) ;
Vyvedennia_Chysla(a, "a ");
Vyvedennia_Chysla(b, "b ");
}
void Vyvedennia_Chysla(int[] d, string st)
{
Console.Write("{0}{1}", st, d[1]);
for (i = 2; i < d[0] + 1; i++)
{
n = d[i];
for (j = 4; n != 0; n /= 10, j--) ;
for (g = 0; g < j; g++) Console.Write("0");
if (d[i] != 0) Console.Write(d[i]);
}
Console.WriteLine();
}
bool Rivnist(int[] q1, int[] q2)
{
if (q1[0] != q2[0]) return false;
for (i = 1; i < q1[0] + 1; i++)
if (q1[i] != q2[i]) return false;
return true;
}
bool Bilshe(int[] q1, int[] q2)
{
if (q1[0] < q2[0]) return false;
else if (q1[0] > q2[0]) return true;
for (i = 1; i < q1[0] + 1; i++)
if (q1[i] < q2[i]) return false;
else if (q1[i] > q2[i]) return true;
return false;
}
void Dodavannia(int[] q1, int[] q2)
{
if (Bilshe(q1, q2)) n = q1[0] + 1;
else n = q2[0] + 1;
c = new int[n + 1];
c[0] = n;
for (i = 1; i < n + 1; c[i] = 0, i++) ;
for (i = c[0], j = q1[0], f = q2[0]; i > 0; i--, j--, f--)
{
g = 0;
if (j > 0) g += q1[j];
if (f > 0) g += q2[f];
c[i] += g % osn;
if (i > 1) c[i - 1] = g / osn;
}
g = 0;
if (c[1] == 0)
{
n--;
g += 1;
}
d = new int[n + 1];
d[0] = n;
for (i = 1; i < n + 1; i++)
d[i] = c[i + g];
}
bool Vidnimannia(int[] q1, int[] q2)
{
if (Rivnist(q1, q2))
{
d = new int[2];
d[0] = 1;
d[1] = 0;
return true;
}
else if (Bilshe(q1, q2))
{
flag = true;
Vidnimannia_2(q1, q2);
}
else
{
flag = false;
Vidnimannia_2(q2, q1);
}
return flag;
}
void Vidnimannia_2(int[] q1, int[] q2)
{
n = q1[0];
c = new int[n + 1];
c[0] = n;
for (i = 1; i < n + 1; c[i] = 0, i++) ;
for (i = c[0], j = q1[0], f = q2[0], g = 0; i > 0; i--, j--, f--)
{
if (j > 0) g += q1[j];
if (f > 0) g -= q2[f];
if (g < 0)
{
c[i] = osn + g;
if (i > 1) g = -1;
}
else
{
c[i] = g;
g = 0;
}
}
g = 0;
if (c[1] == 0)
{
n--;
g += 1;
}
d = new int[n + 1];
d[0] = n;
for (i = 1; i < n + 1; i++)
d[i] = c[i + g];
}
void Shvydke_mn(int[] q1, int[] q2)
{
int te1 = 0, te2 = 0;
int[] q3 = new int[2];
q3[0] = 1;
q3[1] = 0;
int[] s = new int[q1[0] + q2[0] + 1];
s[0] = q1[0] + q2[0];
for (i = 1; i < s[0] + 1; s[i] = 0, i++) ;
while (Bilshe(q2, q3))
if (q2[q2[0]] % 2 == 0)
{
Dodavannia(q1, q1);
q1 = new int[d[0] + 1];
for (i = 0; i < d[0] + 1; q1[i] = d[i], i++) ;
for (i = 1; i < q2[0] + 1; i++)
{
q2[i] = q2[i] + te2 * osn;
te1 = q2[i] / 2;
te2 = q2[i] % 2;
q2[i] = te1;
}
}
else
{
Dodavannia(s, q1);
for (i = d[0]; i > 0; s[i] = d[i], i--) ;
q3[1] = 1;
Vidnimannia(q2, q3);
q2 = new int[d[0] + 1];
for (i = 0; i < d[0] + 1; q2[i] = d[i], i++) ;
q3[1] = 0;
}
for (j = 1; s[j] == 0; j++) ;
d = new int[s[0] - j + 2];
d[0] = s[0] - j + 1;
for (i = s[0], f = d[0]; f > 0; i--, f--)
d[f] = s[i];
}
}
}
Результати роботи програми
31.05.2014 14:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора