Извлечение корня из чисел с фиксированной запятой

ОМСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА Информатики и вычислительной техники

КУРСОВАЯ РАБОТА

Тема: “ Извлечение корня из чисел с фиксированной запятой ”

ВЫПОЛНИЛ: студент гр. В-123

Бензак А.Н.

РУКОВОДИТЕЛЬ: к.т.н., доцент

Червенчук И.В.

ОМСК, 2004 г.

ОГЛАВЛЕНИЕ

1. Описание алгоритма………………………………………………………….3

2. Блок-схема алгоритма………………………………………………………..4

3. Структура операционного устройства………………………………………5

4. Моделирование работы алгоритма на ЭВМ………………………………..6

5. Список используемой литературы…………………………………………..7

6. Приложения

1 Текст программы……………………………………………………..8

2 Пример работы программы…………………………..……………11

ОПИСАНИЕ АЛГОРИТМА

При выполнении операции извлечения корня из чисел, представленных в формате с фиксированной запятой, для получения результата надо выполнить n одинаковых циклов, которые содержат три фазы:

1. Из сумматора вычитается очередной результат извлечения корня с приписанной к нему парой 01. Если разность положительна то очередная цифра R1=1, иначе R1=0.

2. Если очередная цифра результата = 0, то необходимо сделать восстановление сумматора.

3. Содержимое сумматора сдвигается на 1 разряд влево и формируется значение регистра R2. Формирование регистра R2 происходит следующим образом: после каждого цикла приписаная пара 01 удаляется, затем из R1 берется очередная цифра и снова приписывается 01.

0,01

0,y₁01

0,y₁y₂01

………..

и т. д.

В блок-схеме алгоритма эта специальная операция обозначается R2*.

Общая формула вычисления Y как корня квадратного из X: Y_n+1=0,5(Y_n+x/Y_n) .

БЛОК-СХЕМА АЛГОРИТМА

Блок схема работы УА для выполнения алгоритма извлечения корня из чисел с фиксированной запятой:

R2*

=+R2+1

R1[i]=0

R2[i]=0

=+R2

R1[i]=1

R2[i]=1



0

1

СТРУКТУРА ОПЕРАЦИОННОГО УСТРОЙСТВА

Y₄

R1

1

Y₁



Y₅

Y₂

n

R2

Y₃

Упр. сигнал	Операция
Y1	Загрузка в сумматор подкоренного выражения
Y2	Вычитание из сумматора регистра R2 =+R2+1
Y3	Специальная операция R2* (см.алгоритм)
Y4	Выдача результата
Y5	Сдвиг сумматора на один разряд влево

МОДЕЛИРОВАНИЕ РАБОТЫ АЛГОРИТМА НА ЭВМ

Для моделированиям работы алгоритма было решено использовать язык программирования высокого уровня Borland Pascal 7.0 как наиболее приемлемый для решения данного рода задач. Программа выполнена методом восходящего программирования и имеет в своей основе три ключевых процедуры:

1. Процедура sloj. Выполняет сложение массивов двоичных чисел. Реализует управляющий сигнал Y2.

2. Процедура sdvig. Выполняет сдвиг массива на один разряд влево. Реализует управляющий сигнал Y5.

3. Процедура invert. Выполняет инвертирование числового массива. Используется в формировании дополнительного кода R2.

Управляющие сигналы Y1 и Y4 реализуются простыми операциями ввода-вывода. Управляющий сигнал Y3 реализуется непосредственно в цикле, постоянным обнулением массива R2 и новым его формированием из R1 и приписыванием пары 01.

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1. Операции двоичной и десятичной арифметики в ЭВМ: Метод. указания / Сост. Пальянов И.А.; Омск: ОмПИ, 1990. - 36 с.

2. Моделирование на ЭВМ алгоритмов выполнения арифметических операций и синтез управляющих автоматов: Метод. указания / Сост. Пальянов И.А., Шафеева О.П.; Омск: ОмПИ, 1988. - 36 с.

3. Б.Н. Иванов Дискретная математика. Алгоритмы и программы: Учеб. пособие. – М.: Лаборатория Базовых Знаний, 2002 – 288 с.: ил.

Приложение 1

Текст программы:

program discret;

uses crt;

type

mass=array[1..16] of integer;

massstr=array[1..16] of string;

var

k,i,i2,errcod,cikl,cikl2:integer;

sum,r2,dopm,r1,memosum:mass;

ch:string;

sumstr:massstr;

procedure sloj(var s:mass;var b:mass);

var

p,raz:integer;

begin

p:=0;

for i:=16 downto 1 do begin

raz:=s[i]+b[i]+p;

If raz=0 then begin

s[i]:=0;

p:=0;

end;

if raz=1 then begin

s[i]:=1;

p:=0;

end;

if raz=2 then begin

s[i]:=0;

p:=1;

end;

if raz=3 then begin

s[i]:=1;

p:=1;

end;

end;

end;

procedure sdvig(var sd:mass);

begin

for i:=1 to 15 do

sd[i]:=sd[i+1];

sd[16]:=0;

for i:=1 to 15 do

end;

procedure invert(var si:mass);

begin

for i:=1 to 16 do

if si[i]=1 then si[i]:=0 else si[i]:=1;

end;

procedure obnul(var obn:mass);

begin

for i:=1 to 16 do

obn[i]:=0;

end;

procedure vivod(viv:mass);

begin

for i:=1 to 16 do

write(viv[i]);

writeln;

end;

begin

{vvod summatora}

Writeln('Vvedite podkorennoe viragenie');

readln(ch);

for k:=1 to 16 do begin

sumstr[k]:=copy(ch,k,1);

val(sumstr[k],sum[k],errcod);

end;

{vvod R2 i formirovanie dop. massiva i R1}

for i:=1 to 16 do begin

r2[i]:=0;

dopm[i]:=0;

r1[i]:=0;

memosum[i]:=0;

end;

r2[3]:=1;

dopm[7]:=1;

{pervii etap}

invert(r2);

sloj(r2,dopm);

Writeln;

write('sum ');

vivod(sum);

write('R2 ');

vivod(r2);

Writeln(' -------');

sloj(sum,r2);

write('sum ');

vivod(sum);

if sum[1]=1 then r1[2]:=0 else r1[2]:=1;

writeln;

write('R1 ');

vivod(r1);

writeln;

for cikl:=2 to 15 do begin

sdvig(sum);

obnul(r2);

i2:=1;

for cikl2:=3 to cikl do begin

r2[cikl-i2]:=r1[cikl-i2];

i2:=i2+1;

end;

r2[cikl]:=r1[cikl];

r2[cikl+1]:=0;

if cikl+2<>16 then r2[cikl+2]:=1;

write('sum ');

vivod(sum);

invert(r2);

sloj(r2,dopm);

write('R2 ');

vivod(r2);

for i:=1 to 7 do

memosum[i]:=sum[i];

sloj(sum,r2);

write(' -------');

writeln;

write('sum ');

vivod(sum);

writeln;

if sum[1]=1 then r1[cikl+1]:=0 else r1[cikl+1]:=1;

write('R1 ');

vivod(r1);

writeln;

if sum[1]=1 then begin

for i:=1 to 7 do

sum[i]:=memosum[i];

writeln('Vosstanovlenie');

end;

readkey;

end;

end.

Приложение 2

ПРИМЕР РАБОТЫ ПРОГРАММЫ

1. При запуске программы появляется следующее окно:

2. Вводим например, 0110101:

3. Нажимаем Enter, получаем результат:

Ответ

11