Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ТАіМОПЗ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2007
Тип роботи:
Лабораторна робота
Предмет:
Інформаційні технології
Група:
КН
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Інститут комп’ютерних наук і інформаційних технологій
Кафедра АСУ
Складність алгоритмів. Реалізація на ПЕОМ цілочислових арифметичних операцій багатократної точності
Лабораторна робота №1
з курсу “ТАіМОПЗ”
Львів – 2007
Мета лабораторної роботи : 1) експериментально дати оцінку складності елементарних арифметичних функцій мов програмування типу Паскаль;
2)забезпечити засобами мови Паскаль або Си емуляцію арифметичних операцій додавання, віднімання, множення i ділення натуральних чисел багатократної точності й оцінити їх складність.
ТЕОРЕТИЧНІ ВІДОМОСТІ
Практично важливим напрямком, що вивчає теорія алгоритмів є дослідження й аналіз їх, складності [2,4].
1. Однією із задач аналізу алгоритмів є необхідність отримання оцінок для об'єму часу, що необхідно алгоритму для обробки конкретних даних. Досить часто, тільки на практиці програміст переконується, що його програма в змозі обробити вхідні дані тільки через декілька діб безперервної роботи ЕОМ. Крім того, необхідно порівнювати ефективність, складність (час роботи, пам'ять) алгоритмів, що ров'язують одну й ту ж задачу.
Нехай А - алгоритм для розв’язування задач деякого класу К, а число n - розмірність окремої задачі з К (кількість змінних, слів у тексті і т.п.) Визначимо fа(n) як функцію складності, що визначає верхню межу для максимальної кількості основних операцій (додавання, порівняння і т.п.), які повинен виконати алгоритм А для розв’язку будь якої задачі розмірності n.
Будемо користуватися наступним критерієм оцінки складності А. Алгоритм А має поліноміальну складність, коли fa(n) зростає не швидше, ніж поліном від n, у протилежному випадку алгоритм А експоненційний. Цей критерії базується на часі роботи у найгіршому випадку. Основою для цього критерію складності є машинні експерименти, що продемонстрували, що реальні послідовні або паралельні ЕОМ більш менш здатні сприймати і ефективно реалізовувати поліноміальні алгоритми для великих задач, а експоненційні алгоритми вони не в змозі "реалізувати" за практично прийнятний час.
Більш формально, функцію складності fa(n) визначають як O(g(x)) і кажуть, що вона має порядок g(n) для великих n, якщо
f(n)
lim ------- = constanta = a, a>0.
n->g(n)
Це позначується, як f(n) = O(g(n)). Функція h(n) є o(z(n)) для великих n, якщо
h(n)
lim ------- = 0.
n-> z(n)
Змістовно, якщо 1) fa(n) є O(g(x)), то ці дві функції , по суті, зростають з однаковою швидкістю; 2) якщо fa(n) є o(g(x)), то g(n) зростає набагато швидше, ніж fa(n).
Іншими словами, функція f(x) має порядок O(g(x)), якщо знайдеться константа С і f(x) <= C*g(x) для всіх x, крім скінченої (можливо, пустої) множини значень, або, що те саме, завжди знайдеться таке n 40 0, що f(x) <= C*g(x) для всіх x, де x >= n 40 і x > 0.
Розвиток теорії складності обчислень йшов по чотирьом напрямкам :
1) абстрактна (машино-незалежна) складність: 2) машинно-залежна складність;3) складність конкретних задач і алгоритмів; 4)експериментальна (ЕОМ-залежна) складність.
У першому із них обчислювальні моделі і міри складності визначаються аксіоматично і вивчаються найбільш загальні властивості складності алгоритмічних функцій. Доведені теореми про "стискування" і "прискорення". Перша із них стверджує про існування функцій будь якої складності, що оптимально реалізуються. Друга стверджує про існування функцій, кожне обчислення яких можна "прискорити", тобто функцій, для яких не існують оптимальні обчислення.
Другий напрям пов’язаний з дослідженням складності обчислень на конкретних моделях обчислювальних пристроїв і реальних ЕОМ. В цій галузі однією із дуже відомих невирішених проблем є проблема " Р – і NP - складності": чи співпадає клас P функцій, що обчислюються за поліноміальний час на машинах Тюрінга (послідовних ЕОМ), з класом NP функцій, що обчислюються за поліноміальний час на не детермінованих машинах Тюрінга (по суті, паралельних ЕОМ).
Із теорії алгоритмів відомо, що якщо задача Z належить класу NP, то вона завжди реалізується детермінованою машиною Тюрінга з часовою складністю O(k 5Pz(n) 0), де k - константа, а P(n) - поліном, що залежить від Z.
Відмітимо, що до класу P входять класичні комбінаторні проблеми :
а) проблема входження ("ідентифікації") слів, яка полягає у визначенні для двох слів x і y, чи входить x як підслово в y, функція складності якої має порядок O(n), де n - сумарна довжина слів x і y;
б) задача сортування має порядок O(n*log(n));
в) задача множення матриць має порядок складності O(n 52.49..0).
По проблематиці третього напрямку наведемо декілька понять і результатів про складність конкретних алгоритмів. Задача Z називається А-повною для класу задач КА, якщо Z належить КА і по будь якому алгоритму, що розв'язує Z за час T(n), і довільної задачі Z1 із КА можна ефективно побудувати алгоритм В, який розв’язує Z1 за час T(pb(n)), де pb(n) деякій поліном, що залежить від В.
Задача Z називається NP-повною, якщо вона NP-повна для класу NP. На даний час відомо декілька тисяч NP-повних задач, серед яких можна назвати задачі булівського програмування, комівояжера і т.п. для яких відомо, що вони обчислюються за поліноміальний час на не детермінованих машинах Тюрінга. Але не відомо, чи ці NP-повні задачі належать класу P.
Цікаво, що задача ізоморфізму графів належить класу NP, але досі невідомо : 1) чи належить вона класу Р; 2) чи є вона NP-повною ?
Четвертий, експериментальний напрямок пов’язаний з "прокруткою" програми П на скінченій множині вхідних даних, заміром часу її роботи і прямою побудовою по цих замірах функції складності fп(n).
Такий підхід найбільш поширений при оцінці ефективності роботи паралельних, багатопроцесорних ЕОМ і мереж із розподіленою обробкою інформації, але широко і для звичайних послідовних програм, а саме, для виміру реальної швидкодії ЕОМ при реалізації задач практики відносно великої розмірності, так як оцінка ЕОМ по тактовій швидкодії є дуже "грубою".
Тому необхідно, щоб мати уявлення про те, які задачі можуть бути практично реалізовані на конкретному класі ПЕОМ, провести обчислювальні експерименти по оцінці швидкодії ПЕОМ, що і відображено в завданні на дану лабораторну роботу.
2. Завершуючи даний розділ зауважимо, що в теорії алгоритмів широко використовуються дуже великі цілі числа. Так геделiвська нумерація послідовності (x1,x2,..xk) кодуються числом p0 5x1 * p1 5x2 0 * ...pk 5xk 0,де pi - це i-е просте число, а ^ - операція піднесення у степінь.
В той же час, цілочислові типи даних , що вбудовані в мови програмування, можуть працювати не більше ніж з 10-розрядними числами. Тому для потреб теорії алгоритмів необхідно реалізувати алгоритми емуляції на ЕОМ арифметичних операцій над багато розрядними числами, одночасно проаналізувавши практичну цінність теоретичних побудов.
Зрозуміло, що актуальними є проблеми експериментальної оцінки складності алгоритмі в багатократної точності.
ПОРЯДОК РОБОТИ
1. Вивчити поняття складності алгоритмів.
2. Використовуючи функцію типу get time , скласти програми на одній із мов програмування, що дадуть можливість наближено оцінити складність основних цілочислових арифметичних операцій.
3. На основі машинних експериментів спробувати апроксимувати функції складності для цих операцій.
4.1 Вибрати i створити необхідні типи даних для реалізації арифметичних операцій багатократної точності над натуральними числами.
4.2 На основі відомих із шкільного курсу алгоритмів додавання, віднімання, множення та ділення DIV ( "у стовпчик") натуральних чисел із N в десятковій системі числення, а також функцій піднесення у степінь і залишку від ділення MOD над N, розробити машинно-орiентований алгоритм для цих операцій та функцій над багато розрядними натуральними числами.
4.3 Засобами мови Паскаль або Си реалізувати i вiдлагодити відповідні процедури для багато розрядних чисел.
5.1 Використовуючи функцію типу time із ДОС, скласти програми , що дадуть можливість наближено оцінити складність основних цілочислових операцій арифметики багатократної точності.
5.2 На основі машинних експериментів спробувати апроксимувати функції складності для цих операцій.
6. Здати викладачеві розроблені процедури, продемонструвавши їх працездатність на конкретних багато розрядних числах.
7. Проаналізувати результати лабораторної роботи .
8. Оформити звіт з лабораторної роботи.
ТЕКСТ ПРОГРАМ
Завдання 1.
1. Вивчити поняття складності алгоритмів.
2. Використовуючи функцію типу get time , cкласти програми на одній із мов програмування, що дадуть можливість наближено оцінити складність основних цілочислових арифметичних операцій.
program Project1;
uses
Crt,dos;
var a:byte;
b:word;
c:integer;
d:longint;
e:double;
f:longint;
h1,h2,m1,s1,ss1,m2,s2,ss2:word;
tm,ctime:extended;
function r(h1,m1,s1,ss1,h2,m2,s2,ss2:word):extended;
begin
r:=((h2-h1)*60+m2-m1)*60+s2-s1+(ss2-ss1)/100;
end;
begin
clrscr;
{addition}
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do;
gettime(h2,m2,s2,ss2);
ctime:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Cycle time = ':20,ctime:5,' . Speed = ',1000000/ctime:5:3,' op/msec');
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do a:=a+1;
gettime(h2,m2,s2,ss2);
tm:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Byte add time = ':20,tm:5,' . Speed = ',1000000/tm:5:3,' op/msec');
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do b:=b+1;
gettime(h2,m2,s2,ss2);
tm:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Word add time = ':20,tm:5,' . Speed = ',1000000/tm:5:3,' op/msec');
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do c:=c+1;
gettime(h2,m2,s2,ss2);
tm:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Longint add time = ':20,tm:5,' . Speed = ',1000000/tm:5:3,' op/msec');
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do d:=d+1;
gettime(h2,m2,s2,ss2);
tm:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Double add time = ':20,tm:5,' . Speed = ',1000000/tm:5:3,' op/msec');
{substraction}
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do a:=a-1;
gettime(h2,m2,s2,ss2);
tm:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Byte sub time = ':20,tm:5,' . Speed = ',1000000/tm:5:3,' op/msec');
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do b:=b-1;
gettime(h2,m2,s2,ss2);
tm:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Word sub time = ':20,tm:5,' . Speed = ',1000000/tm:5:3,' op/msec');
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do c:=c-1;
gettime(h2,m2,s2,ss2);
tm:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Longint sub time = ':20,tm:5,' . Speed = ',1000000/tm:5:3,' op/msec');
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do d:=d-1;
gettime(h2,m2,s2,ss2);
tm:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Double sub time = ':20,tm:5,' . Speed = ',1000000/tm:5:3,' op/msec');
{multiplying}
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do a:=a*2;
gettime(h2,m2,s2,ss2);
tm:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Byte mul time = ':20,tm:5,' . Speed = ',1000000/tm:5:3,' op/msec');
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do b:=b*2;
gettime(h2,m2,s2,ss2);
tm:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Word mul time = ':20,tm:5,' . Speed = ',1000000/tm:5:3,' op/msec');
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do c:=c*2;
gettime(h2,m2,s2,ss2);
tm:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Longint mul time = ':20,tm:5,' . Speed = ',1000000/tm:5:3,' op/msec');
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do d:=d*2;
gettime(h2,m2,s2,ss2);
tm:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Double mul time = ':20,tm:5,' . Speed = ',1000000/tm:5:3,' op/msec');
{dividing}
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do a:=a div 2;
gettime(h2,m2,s2,ss2);
tm:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Byte div time = ':20,tm:5,' . Speed = ',1000000/tm:5:3,' op/msec');
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do b:=b div 2;
gettime(h2,m2,s2,ss2);
tm:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Word div time = ':20,tm:5,' . Speed = ',1000000/tm:5:3,' op/msec');
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do c:=c div 2;
gettime(h2,m2,s2,ss2);
tm:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Longint div time = ':20,tm:5,' . Speed = ',1000000/tm:5:3,' op/msec');
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do d:=d div 2;
gettime(h2,m2,s2,ss2);
tm:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Double div time = ':20,tm:5,' . Speed = ',1000000/tm:5:3,' op/msec');
{module}
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do a:=a mod 2;
gettime(h2,m2,s2,ss2);
tm:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Byte mod time = ':20,tm:5,' . Speed = ',1000000/tm:5:3,' op/msec');
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do b:=b mod 2;
gettime(h2,m2,s2,ss2);
tm:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Word mod time = ':20,tm:5,' . Speed = ',1000000/tm:5:3,' op/msec');
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do c:=c mod 2;
gettime(h2,m2,s2,ss2);
tm:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Longint mod time = ':20,tm:5,' . Speed = ',1000000/tm:5:3,' op/msec');
gettime(h1,m1,s1,ss1);
for f:=1 to 10000000 do d:=d mod 2;
gettime(h2,m2,s2,ss2);
tm:=r(h1,m1,s1,ss1,h2,m2,s2,ss2);
writeln('Double mod time = ':20,tm:5,' . Speed = ',1000000/tm:5:3,' op/msec');
readln;
end.
Завдання 2.
1. На основi вiдомих iз шкiльного курсу алгоритмів додавання, віднімання, множення та ділення DIV ( "у стовпчик") натуральних чисел із N в десятковiй системi числення, а також функцій піднесення у степінь і залишку від ділення MOD над N, розробити машинно-орiентований алгоритм для цих операцій та функцій над багаторозрядними натуральними числами.
2. Засобами мови Паскаль або Сі реалiзувати i вiдлагодити відповідні процедури для багато розрядних чисел.
program Project2;
uses Crt;
var a,b:string;
function rot(a:string):string;
var f:byte;
ch:char;
begin
for f:=1 to length(a) div 2 do begin
ch:=a[f];
a[f]:=a[length(a)-f+1];
a[length(a)-f+1]:=ch;
end;
rot:=a;
end;
function iAdd(a,b:string):string;
var p,p1,f,j,lb:byte;
begin
{// ord(0)=48}
a:=rot(a);
b:=rot(b);
for f:=1 to length(a) do begin
j:=f;
p:=ord(a[f])-48;
while p<>0 do begin
lb:=length(b);
if lb>=j then p1:=(ord(b[j])-48+p)div 10 else p1:=0;
if lb>=j then b[j]:=chr((ord(b[j])-48+p)mod 10+48)
else b:=b+chr(p mod 10+48);
p:=p1;
inc(j);
end;
end;
b:=rot(b);
iAdd:=b;
end;
function bigger(a,b:string):boolean;
var abb:boolean;
f:byte;
a1,b1:string;
begin
abb:=true;
f:=1;
while (a[f]='0')and(f<length(a)) do inc(f);
a1:='';
while f<=length(a) do begin
a1:=a1+a[f];
inc(f);
end;
f:=1;
b1:='';
while (b[f]='0')and(f<length(b)) do inc(f);
while f<=length(b) do begin
b1:=b1+b[f];
inc(f);
end;
a:=a1;
b:=b1;
if (length(b)>length(a)) then abb:=false;
if (length(a)=length(b)) then begin
f:=1;
while (a[f]=b[f])and(f<=length(a)) do inc(f);
if f>length(a) then abb:=false else if ord(b[f])>ord(a[f]) then abb:=false;
end;
bigger:=abb;
end;
function iSub(a,b:string):string;
var sign:boolean;
s:string;
f,j,p:word;
begin
sign:=false;
if bigger(b,a) then begin
s:=a;
a:=b;
b:=s;
sign:=true;
end;
a:=rot(a);
b:=rot(b);
for f:=1 to length(b) do begin
j:=f;
p:=ord(b[f])-48;
while p<>0 do begin
if ord(a[j])-48>=p then begin
a[j]:=chr(ord(a[j])-p);
p:=0;
end else begin
a[j]:=chr(10+ord(a[j])-p);
p:=1;
end;
inc(j);
end;
end;
a:=rot(a);
if sign then a:='-'+a;
iSub:=a
end;
function iMul(a,b:string):string;
var s,n:string;
f,j,p,k:byte;
al,bl:byte;
begin
s:='0';
a:=rot(a);
b:=rot(b);
for f:=1 to length(b) do begin
bl:=ord(b[f])-48;
p:=0;
n:=a;
for j:=1 to length(n) do begin
al:=ord(n[j])-48;
al:=al*bl+p;
p:=al div 10;
al:=al mod 10;
n[j]:=chr(al+48);
end;
if p<>0 then n:=n+chr(p+48);
for k:=1 to f-1 do n:='0'+n;
s:=iAdd(s,rot(n));
end;
iMul:=s;
end;
function iDiv(a,b:string):string;
var f,k,rz,c,bp:byte;
a1,s,z,r:string;
begin
r:='';
for f:=1 to length(a)-length(b)+1 do begin
a1:='';
for k:=1 to f+length(b)-1 do a1:=a1+a[k];
s:='0';
repeat s:=chr(ord(s[1])+1) until bigger(iMul(b,s),a1);
s:=chr(ord(s[1])-1);
r:=r+s;
s:=iMul(b,s);
z:='1';
for k:=1 to length(a)-length(b)+1-f do z:=z+'0';
s:=iMul(s,z);
a:=iSub(a,s);
end;
iDiv:=r;
end;
function iMod(a,b:string):string;
var f,k,rz,c,bp:byte;
a1,s,z,r:string;
begin
r:='';
for f:=1 to length(a)-length(b)+1 do begin
a1:='';
for k:=1 to f+length(b)-1 do a1:=a1+a[k];
s:='0';
repeat s:=chr(ord(s[1])+1) until bigger(iMul(b,s),a1);
s:=chr(ord(s[1])-1);
r:=r+s;
s:=iMul(b,s);
z:='1';
for k:=1 to length(a)-length(b)+1-f do z:=z+'0';
s:=iMul(s,z);
a:=iSub(a,s);
end;
iMod:=a;
end;
begin
Clrscr;
write('Enter a: ');
readln(a);
write('Enter b: ');
readln(b);
writeln('a + b = ',iAdd(a,b));
writeln('a - b = ',iSub(a,b));
writeln('a * b = ',iMul(a,b));
writeln('a div b = ',iDiv(a,b));
writeln('a mod b = ',iMod(a,b));
readln;
end.
Завдання 3.
Використовуючи функцію типу time із ДОС, cкласти програми , що дадуть можливість наближено оцінити складність основних цілочислових операцій арифметики багатократної точності.
program Project2;
uses Crt,DOS;
var a,b,s:string;
f1,f2,f3,f4,f5:real; {Performance times}
as,bs:string; {A and B Values}
t1,t2,t:real; {Times for function of Time}
code:integer; {Code for Val procedure}
i,n:longint; {i,n for loop control}
loop:string;
in_file:text;
function time:real;
var h,m,s,ss:word;
t:real;
begin
gettime(h,m,s,ss);
t:=(((h*60+m)*60+s)*100+ss);
time:=t;
end;
function rot(a:string):string;
var f:byte;
ch:char;
begin
for f:=1 to length(a) div 2 do begin
ch:=a[f];
a[f]:=a[length(a)-f+1];
a[length(a)-f+1]:=ch;
end;
rot:=a;
end;
function iAdd(a,b:string):string;
var p,p1,f,j,lb:byte;
begin
a:=rot(a);
b:=rot(b);
for f:=1 to length(a) do begin
j:=f;
p:=ord(a[f])-48;
while p<>0 do begin
lb:=length(b);
if lb>=j then p1:=(ord(b[j])-48+p)div 10 else p1:=0;
if lb>=j then b[j]:=chr((ord(b[j])-48+p)mod 10+48)
else b:=b+chr(p mod 10+48);
p:=p1;
inc(j);
end;
end;
b:=rot(b);
iAdd:=b;
end;
function bigger(a,b:string):boolean;
var abb:boolean;
f:byte;
a1,b1:string;
begin
abb:=true;
f:=1;
while (a[f]='0')and(f<length(a)) do inc(f);
a1:='';
while f<=length(a) do begin
a1:=a1+a[f];
inc(f);
end;
f:=1;
b1:='';
while (b[f]='0')and(f<length(b)) do inc(f);
while f<=length(b) do begin
b1:=b1+b[f];
inc(f);
end;
a:=a1;
b:=b1;
if (length(b)>length(a)) then abb:=false;
if (length(a)=length(b)) then begin
f:=1;
while (a[f]=b[f])and(f<=length(a)) do inc(f);
if f>length(a) then abb:=false else if ord(b[f])>ord(a[f]) then abb:=false;
end;
bigger:=abb;
end;
function iSub(a,b:string):string;
var sign:boolean;
s:string;
f,j,p:word;
begin
sign:=false;
if bigger(b,a) then begin
s:=a;
a:=b;
b:=s;
sign:=true;
end;
a:=rot(a);
b:=rot(b);
for f:=1 to length(b) do begin
j:=f;
p:=ord(b[f])-48;
while p<>0 do begin
if ord(a[j])-48>=p then begin
a[j]:=chr(ord(a[j])-p);
p:=0;
end else begin
a[j]:=chr(10+ord(a[j])-p);
p:=1;
end;
inc(j);
end;
end;
a:=rot(a);
if sign then a:='-'+a;
iSub:=a
end;
function iMul(a,b:string):string;
var s,n:string;
f,j,p,k:byte;
al,bl:byte;
begin
s:='0';
a:=rot(a);
b:=rot(b);
for f:=1 to length(b) do begin
bl:=ord(b[f])-48;
p:=0;
n:=a;
for j:=1 to length(n) do begin
al:=ord(n[j])-48;
al:=al*bl+p;
p:=al div 10;
al:=al mod 10;
n[j]:=chr(al+48);
end;
if p<>0 then n:=n+chr(p+48);
for k:=1 to f-1 do n:='0'+n;
s:=iAdd(s,rot(n));
end;
iMul:=s;
end;
function iDiv(a,b:string):string;
var f,k,rz,c,bp:byte;
a1,s,z,r:string;
begin
r:='';
for f:=1 to length(a)-length(b)+1 do begin
a1:='';
for k:=1 to f+length(b)-1 do a1:=a1+a[k];
s:='0';
repeat s:=chr(ord(s[1])+1) until bigger(iMul(b,s),a1);
s:=chr(ord(s[1])-1);
r:=r+s;
s:=iMul(b,s);
z:='1';
for k:=1 to length(a)-length(b)+1-f do z:=z+'0';
s:=iMul(s,z);
a:=iSub(a,s);
end;
iDiv:=r;
end;
function iMod(a,b:string):string;
var f,k,rz,c,bp:byte;
a1,s,z,r:string;
begin
r:='';
for f:=1 to length(a)-length(b)+1 do begin
a1:='';
for k:=1 to f+length(b)-1 do a1:=a1+a[k];
s:='0';
repeat s:=chr(ord(s[1])+1) until bigger(iMul(b,s),a1);
s:=chr(ord(s[1])-1);
r:=r+s;
s:=iMul(b,s);
z:='1';
for k:=1 to length(a)-length(b)+1-f do z:=z+'0';
s:=iMul(s,z);
a:=iSub(a,s);
end;
iMod:=a;
end;
Label start,finish;
begin
ClrScr;
Writeln;
Writeln(' Written by Kruvorychko Sergij ');
Writeln;
Writeln('--------------------------------------------------------------------------------');
Writeln(' Loop length depends of quantity figures in number');
Writeln;
Writeln(' To see effect recommended loop length 1000 -> 3000');
Writeln;
Write(' Enter loop length: ');
Readln(loop);
if loop='' then loop:='1';
Val(loop,n,Code);
start:
Clrscr;
Writeln;
Writeln(' Written by Kruvorychko Sergij ');
Writeln;
Writeln('--------------------------------------------------------------------------------');
Writeln(' a must be <> 0');
Writeln;
write(' Enter a: ');
readln(a);
as:=a;
if a='' then a:='0';
if a='0' then goto start;
finish:
Clrscr;
Writeln;
Writeln(' Written by Kruvorychko Sergij ');
Writeln;
Writeln('--------------------------------------------------------------------------------');
Writeln(' a must be <> 0');
Writeln;
write(' Enter b: ');
readln(b);
bs:=b;
if b='' then b:='0';
if b='0' then goto finish;
Clrscr;
Writeln;
Writeln(' Written by Kruvorychko Sergij ');
Writeln;
Writeln('--------------------------------------------------------------------------------');
Writeln(' To break program performance press CTRL+BREAK !');
Writeln;
Writeln(' Loop length = ',n);
Writeln;
Writeln(' a = ',as);
Writeln(' b = ',bs);
Writeln;
t1:=Time;
For i:=1 to n do begin
s:=iAdd(a,b);
end;
t2:=Time;
t:=t2-t1;
f1:=t/100;
writeln(' a + b (Result) = ',s);
t1:=Time;
For i:=1 to n do begin
s:=iSub(a,b);
end;
t2:=Time;
t:=t2-t1;
f2:=t/100;
writeln(' a - b (Result) = ',s);
t1:=Time;
For i:=1 to n do begin
s:=iMul(a,b);
end;
t2:=Time;
t:=t2-t1;
f3:=t/100;
writeln(' a * b (Result) = ',s);
t1:=Time;
For i:=1 to n do begin
s:=iDiv(a,b);
end;
t2:=Time;
t:=t2-t1;
f4:=t/100;
writeln(' a div b (Result) = ',s);
t1:=Time;
For i:=1 to n do begin
s:=iMod(a,b);
end;
t2:=Time;
t:=t2-t1;
f5:=t/100;
writeln(' a mod b (Result) = ',s);
Writeln;
Writeln(' a + b (Performance Time) = ',f1:0:3,' (seconds)');
Writeln(' a - b (Performance Time) = ',f2:0:3,' (seconds)');
Writeln(' a * b (Performance Time) = ',f3:0:3,' (seconds)');
Writeln(' a div b (Performance Time) = ',f4:0:3,' (seconds)');
Writeln(' a mod b (Performance Time) = ',f5:0:3,' (seconds)');
Writeln;
Writeln;
Writeln('--------------------------------------------------------------------------------');
Writeln;
write(' Successfully done...');
Assign(in_file,'C:\Report.txt');
Rewrite(in_file);
Writeln(in_file,' Loop length = ',n);
Writeln(in_file,'');
Writeln(in_file,' a = ',as);
Writeln(in_file,' b = ',bs);
Writeln(in_file,'');
writeln(in_file,' a + b (Result) = ',s);
writeln(in_file,' a - b (Result) = ',s);
writeln(in_file,' a * b (Result) = ',s);
writeln(in_file,' a div b (Result) = ',s);
writeln(in_file,' a mod b (Result) = ',s);
Writeln(in_file,'');
Writeln(in_file,' a + b (Performance Time) = ',f1:0:3,' (seconds)');
Writeln(in_file,' a - b (Performance Time) = ',f2:0:3,' (seconds)');
Writeln(in_file,' a * b (Performance Time) = ',f3:0:3,' (seconds)');
Writeln(in_file,' a div b (Performance Time) = ',f4:0:3,' (seconds)');
Writeln(in_file,' a mod b (Performance Time) = ',f5:0:3,' (seconds)');
Close(in_file);
readln;
end.
Висновок:
У ході даної лабораторної роботи ми розробили програми, які здійснють арифметичні операції по розрядам, що дає нам можливість отримати точний результат при дуже великих вхідних числах. Також ми вивчили поняття складності алгоритмів. Використовуючи функцію типу get time , ми cклали програми на мові Pascal, що дала можливість наближено оцінити складність основних цілочислових арифметичних операцій для різних типів даних.
В результаті виконання лабораторной роботи я дійшов висновку, що зі збільшенням розрядності чисел, час збільшується також, більше того залежність „кратність-час” є лінійною. Результати продемонстровані в таблиці.
Кратність чисел
Час виконання операцій
Додавання
Віднімання
Множення
DIV
MOD
20
0.15
0.010
0.20
0.120
0.10
40
0.35
0.30
4.7
0.340
0.4
60
0.57
0.60
6.50
0.530
0.650
120
0.9
0.8
15.8
1.35
1.1
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора