Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКТА
Факультет:
СІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2016
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Алгоритмічні основи криптології
Група:
БІ 21
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ІКТА
кафедра БІТ
Звіт
до лабораторної роботи № 2
з дисципліни "Алгоритмічні основи криптології"
по темі : " ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ"
Львів – 2016
Мета роботи - вивчити алгоритми множення та ділення довгих чисел та навчитися розробляти програмне забеспечення для реалізації цих алгоритмів на ком'ютері; дослідити швиткодію алгоритмів множення довгих чисел.
1. Завданння
1) Вивчити основні алгоритми множення та ділення довгих чисел, а також способи підвищення швидкодії виконання мультиплікативних операцій з довгими числами
2) Скласти блок-схеми алгоритмів та програми для реалізації операцій множення (стовпчиком, швидке множення, множення з використанням перетворення Фур'є) або ділення довгих чисел. Варіанти представлення довгих чисел та способи заповнення невикористаних розрядів беруться з лабораторної роботи № 1. Дані для роботи беруться за вказівкою викладача.
3) Дослідити швидкість виконання мультиплікативних операцій для розрядності довгих чисел від 200 до 500. Накреслити графіки відповідних залежностей і порівняти одержані результати.
Алгоритм швидкого множення.
2. Блок-схеми алгоритмів
Main() FastMult()
HowZeros() Show()
DivTwo()
AplusA()
SplusA()
ElvestR()
MinusOne()
InputZ() CounterZeros()
OzerZeros()
MoreOneZeros()
isPair() MoreZeros()
3. Текст програми
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace Crypto_Lab2
{
class FastMult
{
StreamWriter sw = new StreamWriter("results.txt");
int[] a;
int[] sa;
int[] b;
int[] s;
int[] so;
int n = 0, m = 0;
int index = 0;
public FastMult(string str1, string str2)
{
n = str1.Length;
m = str2.Length;
a = new int[n];
sa = new int[n];
b = new int[m];
s = new int[n + m];
so = new int[n + m];
foreach (char ca in str1)
{
a[index] = Converter.ToIntDigit(ca);
index++;
}
index = 0;
foreach (char cb in str2)
{
b[index] = Converter.ToIntDigit(cb);
index++;
}
int hz = 0;
for (int i = 0; i < s.Length; i++)
s[i] = 0;
while (MoreZeros(b))
{
if (isPair(b))
{
// A = A + A
Array.Copy(a, sa, a.Length);
if ((a[0] + a[0]) >= 10)
{
a = new int[a.Length + 1];
a[0] = 0;
for (int j = 1; j < a.Length; j++)
a[j] = sa[j - 1];
sa = new int[a.Length];
Array.Copy(a, sa, a.Length);
}
a = AplusA(a);
// B = B / 2
b = DivTwo(ref b);
}
else
{
so = new int[s.Length];
Array.Copy(s, so, s.Length);
// S = S + A
Array.Copy(s, so, s.Length);
if (EldestR(s, a))
{
s = new int[s.Length + 1];
s[0] = 0;
for (int j = 1; j < s.Length; j++)
s[j] = so[j - 1];
so = new int[s.Length];
Array.Copy(s, so, s.Length);
}
s = SplusA(ref s, a);
if (HowZeros(s) > 0)
{
so = new int[s.Length];
Array.Copy(s, so, s.Length);
hz = HowZeros(s);
s = new int[s.Length - hz];
for (int j = 0; j < s.Length; j++)
s[j] = so[j + hz];
so = new int[s.Length];
Array.Copy(s, so, s.Length);
}
// B = B - 1
MinusOne(ref b);
}
}
Console.Write("s = ");
Show(s);
sw.Close();
}
int HowZeros(int[] test)
{
int c = 0;
for (int i = 0; i < test.Length; i++)
if (test[i] == 0)
c++;
else break;
return c;
}
void Show(int[] b)
{
for (int i = 0; i < b.Length; i++)
{
Console.Write(b[i]);
sw.Write(b[i]);
}
sw.WriteLine();
Console.WriteLine();
}
// B = B / 2
int[] DivTwo(ref int[] b)
{
int[] c = new int[b.Length];
int[] temp = new int[c.Length];
for (int i = 0; i < c.Length; i++)
c[i] = 0;
if (b.Length < c.Length)
c = new int[b.Length];
if (c.Length == 1)
{
c[0] = b[0] / 2;
}
else
for (int i = c.Length - 1; i >= 1; i--)
if (b[i - 1] % 2 == 0)
{
c[i - 1] = b[i - 1] / 2;
c[i] = b[i] / 2;
}
else
{
c[i - 1] = b[i - 1] / 2;
c[i] = (b[i] / 2) + 5;
}
Array.Copy(c, temp, c.Length);
if (c[0] == 0)
{
temp = new int[c.Length - 1];
for (int i = 0; i < temp.Length; i++)
temp[i] = c[i + 1];
}
return temp;
}
// A = A + A
int[] AplusA(int[] k)
{
int[] res = new int[k.Length];
int[] A = new int[k.Length];
int[] B = new int[k.Length];
int st = 0;
Array.Copy(k, A, k.Length);
Array.Copy(k, B, k.Length);
for (int i = 0; i < res.Length; i++)
res[i] = 0;
for (int i = res.Length - 1; i >= 0; i--)
{
A[i] += st;
if ((A[i] + B[i]) >= 10)
{
res[i] = (A[i] + B[i]) - 10;
st = 1;
}
else
{
res[i] = A[i] + B[i];
st = 0;
}
}
return res;
}
// S = S + A
int[] SplusA(ref int[] s, int[] a)
{
int[] at = new int[a.Length];
int[] sm = new int[s.Length];
int[] temp;
int rs = 0;
int size;
int ind = 0;
Array.Copy(a, at, a.Length);
Array.Copy(s, sm, s.Length);
if (sm.Length > at.Length)
{
rs = sm.Length - at.Length;
size = sm.Length;
at = new int[size];
for (int i = 0; i < rs; i++)
at[i] = 0;
for (int i = rs; i < size; i++)
{
at[i] = a[ind];
ind++;
}
}
else
if (at.Length > sm.Length)
{
rs = at.Length - sm.Length;
size = at.Length;
sm = new int[size];
for (int i = 0; i < rs; i++)
sm[i] = 0;
for (int i = rs; i < size; i++)
{
sm[i] = s[ind];
ind++;
}
}
else
{
size = at.Length;
}
temp = new int[sm.Length];
int st = 0;
for (int i = temp.Length - 1; i >= 0; i--)
{
at[i] += st;
if ((at[i] + sm[i]) >= 10)
{
temp[i] = (at[i] + sm[i]) - 10;
st = 1;
}
else
{
temp[i] = at[i] + sm[i];
st = 0;
}
}
return temp;
}
bool EldestR(int[] s, int[] a)
{
int[] at = new int[a.Length];
int[] st = new int[s.Length];
int[] temp;
int rs = 0;
int size;
int ind = 0;
int st_r = 0;
Array.Copy(a, at, a.Length);
Array.Copy(s, st, s.Length);
if (st.Length > at.Length)
{
rs = st.Length - at.Length;
size = st.Length;
at = new int[size];
temp = new int[size + 1];
for (int i = 0; i < rs; i++)
at[i] = 0;
for (int i = rs; i < size; i++)
{
at[i] = a[ind];
ind++;
}
}
else if (st.Length < at.Length)
{
rs = at.Length - st.Length;
size = at.Length;
st = new int[size];
temp = new int[size + 1];
for (int i = 0; i < rs; i++)
st[i] = 0;
for (int i = rs; i < size; i++)
{
st[i] = s[ind];
ind++;
}
}
else
{
size = at.Length;
temp = new int[size + 1];
}
for (int i = size - 1; i >= 0; i--)
{
at[i] += st_r;
if ((at[i] + st[i]) >= 10)
{
temp[i] = (at[i] + st[i]) - 10;
st_r = 1;
}
else
{
temp[i] = at[i] + st[i];
st_r = 0;
}
}
if (((at[0] + st_r) + st[0]) >= 10)
return true;
else return false;
}
// B = B - 1
void MinusOne(ref int[] b)
{
int lastElement = b[b.Length - 1];
if (b[0] == 1 && OtherZeros(b))
{
b = new int[b.Length - 1];
for (int i = 0; i < b.Length; i++)
b[i] = 9;
}
else if (MoreOneZeros(b))
{
InputZ(ref b);
}
else if (lastElement == 0)
{
b[b.Length - 1] = 9;
b[b.Length - 2]--;
}
else
{
b[b.Length - 1]--;
}
}
void InputZ(ref int[] b)
{
int cz = CounterZeros(b);
for (int i = b.Length - 1; i >= b.Length - cz; i--)
b[i] = 9;
b[b.Length - cz - 1]--;
}
int CounterZeros(int[] cz)
{
int count = 0;
for (int i = cz.Length - 1; i >= 0; i--)
if (cz[i] == 0)
count++;
else break;
return count;
}
bool OtherZeros(int[] k)
{
int count = 0;
for (int i = 1; i < k.Length; i++)
if (k[i] == 0)
count++;
if (count == k.Length - 1)
return true;
else return false;
}
bool MoreOneZeros(int[] k)
{
int moz = 0;
for (int i = k.Length - 1; i >= 0; i--)
if (k[i] == 0)
moz++;
else break;
if (moz > 1)
return true;
else return false;
}
// B - парне - ?
bool isPair(int[] b)
{
if (b[b.Length - 1] % 2 == 0)
return true;
else return false;
}
// B > 0 - ?
bool MoreZeros(int[] b)
{
int[] zeros = new int[b.Length];
for (int i = 0; i < zeros.Length; i++)
zeros[i] = 0;
for (int i = 0; i < b.Length; i++)
if (b[i] > zeros[i]) return true;
else return false;
return false;
}
}
class Converter
{
public static int ToIntDigit(char c)
{
int dig = 0;
switch (c)
{
case '0':
dig = 0;
break;
case '1':
dig = 1;
break;
case '2':
dig = 2;
break;
case '3':
dig = 3;
break;
case '4':
dig = 4;
break;
case '5':
dig = 5;
break;
case '6':
dig = 6;
break;
case '7':
dig = 7;
break;
case '8':
dig = 8;
break;
case '9':
dig = 9;
break;
default:
break;
}
return dig;
}
}
class Program
{
static void Main(string[] args)
{
string a = String.Empty;
string b = String.Empty;
Console.Write("Введiть A - ");
a = Console.ReadLine();
Console.Write("Введiть B - ");
b = Console.ReadLine();
FastMult fm = new FastMult(a, b);
Console.ReadLine();
}
}
}
5. Результати роботи програм
14.05.2016 10:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора