Устройство для извлечения корня четвертой степени

 

Изобретение относится к В11гчислительной технике и может быть использовано в цифровых вычислительных машинах. Изобретение решает задачу увеличения быстродействия устройства за счет повышения однородности и параллельности вычислений. Эта цель достигается тем, что вычисление значения корня выполняется с помощью блоков сложения, вычитания, умножения и возведения в квадрат, объединенных в обрабатывающее кольцо. Обрабатывающее кольцо реализует итераР ционный алгоритм вычисления. Алгоритм (Л не содержит трудоемкой операции деления и специального блока для ее выс полнения. 1 з.п. ф-лы, 4 ил.

СОЮЗ СОБЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (ч) 4 -: 06 1 7/552

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

Н АBTOPCHOMV СВИДЕТЕЛЬСТВУ (21) 3876026/24-24 (22) 01.04.85 (46) 07.10.86. Бюл. 11 - 37 (71) Таганрогский радиотехнический институт им. В.Д. Калмыкова (72) В.Ф. Арсени, М.F.. Бородянский, И.Ф. Сурженко, M.Á. Бабакон и С.H. Неценко (53) 68).325(088.8) (56) Авторское свидетельство СССР

11 541169, кл. G 06 F 7/552, 1976.

Анторское свидетельстно СССР

У 538360, кл. G 06 Е 7/552, 1977.

„„SU „„1262487 А 1 (54) УСТРОЙСТВО ДЛЯ ИЗБА!ЕЧЕНИЯ КОРНЯ

ЧЕТВЕРТОЙ СТЕ11ЕНИ (57) Изобретение относится к ны гнслительной технике и может быть использовано н цифровых вычислительных машинах. Изобретение решает задачу увеличения быстродействия устройства за счет повышения однородности и па— раллельности вычислений. Эта цель достигается тем, что вычисление значения корня выполняется с помощью блоков сложения, вычитания, умножения и возведения в квадрат, объединенных в обрабатывающее кольцо. Обрабатывающее кольцо реализует итераЖ ционный алгоритм вычисления. Алгоритм не содержит трудоемкой операции деления и специального блока для ее выполнения. 1 з и. ф лы, 4 ил. С:!

26?487

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных машинах.

Целью изобретения является увеличение быстродействия устройства путем повышения однородности и параллельности вычислений.

В основу работы устройства положен итерационный алгоритм вычисления по формуле

У. = +У (1) !

+1 < е С !. ° где i — номер итерации (i=0,1,2,,), начальное условие у и парао метр d. определяются по правилу, описанному ниже.

Вычисления по формуле (l) прекращаются при выполнении условия ! У... У; Е ° где Š— заданная точность вычислений.

Известно, что итерационный процесс

У; = (У, ) 1=0,1,2,... сходится.к точному решению при выполнении условия !

iр(y)!(i (2)

В нашем случае условие (2) в каждой итерации имеет вид

)1 — — — с 1.

4уз (3)

Ы, Если ; =4у, то неравенство (3) всегда выполняется.

В виду отсутствия в предлагаемом устройстве операции деления, которая заменяется сдвигом делимого на определенное число двоичных разрядов влево или вправо, значение Ы, выбирается равным ближайшему числу, кратному степени двойки с целым показателем, например 4 у.=0,128 тогда

ы =4y З=О, 125=2

Начальное значение у находится о следующим образом.

Определяется зйаченпе х, ближайшее к х, но кратное 2". Показатель

k делится на четыре — (где деление

4 числа k заменяется сдвигом его на два разряда), на полученное значение

4Г спвигатеся число х. Например, у= ч 68, x=68, х=64=2, у.=2 =2 2

6 б!4 3!2 ) 1

Итерационный процесс (!) сходится со знаменателем 3/4, число итераций при заданной точности вычислений

F легко определяется из формулы

3" Znf ь "- указ,!

В приложении 1 приведен расчет .1 г— вычисления у=- / 9 по алгоритму (1), где в первом столбце печатаются зна— чения функции у, во втором столбце 1

5 значения d . Вычисления проводятся ! на микроЭВМ "Электроника-60М" с применением алгоритмическог о языка

-з

BAHIC, точность вычислений Е =10

На фиг. 1 показана структурная схема устройства; на фиг. 2 — то же, блока окончания вычислений; на фиг, 3 — то же, блока нормализации; на фиг. 4 — то же,блок вычисления коэффициента.

Устройство содержит генератор l импульсов, первый 2 и второй 3 распределители импульсов, первый 4 и второй 5 триггеры, элемент И 6, сумматор 7, блок 8 окончания вычислений, 20 первый 9 и второй 10 регистры, первый 11 и второй 12 блоки нормализации, сдвиговый регистр 13,вычитатель 14, группу 15 элементов ИЛИ, первый !6 и второй 17 умножители, квадратор )8, блок 19 вычисления коэффициента.

Устройство имеет вход 20 пуска, выход 21 признака окончания работы, вход 22 допуска, шину 23 результата, 30 информационный 24 вход.

Блок 8 окончания вычислений содержит первый 25 и второй 26 вычитатели, триггер 27 и элемент И 28.

Блок окончания вычислений имеет входы следующей итерации 29 и текущей итерации 30, вход 31 допуска, вход 32 запуска, стробирующий 33 вход, выход 34.

Блок ll (12) нормализации содержит

40 генератор 35 импульсов, элемент И 36, триггер 37, первый 38 и второй 39 регистры сдвига.

Блок нормализации имеет вход 40 нормализуемого значения, вход 41

45 нормализующего коэффициента, вход

42 запуска, выход 43.

Блок 19 вычисления коэффициента содержит генератор 44 импульсов, элемент И 45, триггер 46, первый 47 и второй 48 регистры сдвига.

Блок вычисления коэффициента име- ет вход 49 запуска, информационный вход 50, выход 51.

Устройство работает следующим об55 разом.

В исходном состоянии регистры 9, 10, 13 и блоки ll, 12, !9, 8 устанавливаются в нулевое положение. На

1262487 писцу 24 поступает преобразуемая величина х и по сигналу Пуск, посту, пающему по входу 20, осуществляется запуск устройства. По сигналу с восьмого выхода второго распределителя

3 в регистр 9 заносится число х, по сигналу с седьмого выхода блока 3 в регистр 10 со сдвигом — число х равное первому значению у, по импуль су с шестого выхода блока 3 — число 0 у, поступающее с регистра 10 через элементы 15, фиксируется в регистре

13. По сигналу с пятого выхода блока

3 в квадраторе 18 значение у воз с водится в квадрат, по сигналу с чет- 15 вертого выхода блока 3 в умножителе

16 вычисляется значение у ", а по импульсу третьего выхода блока 3 в, 4 умножителе 17 формируется и в блоке 19 значение коэффициента d по 20 сигналу со второго выхода блока 3 в блоках ll и 13 нормализации фориирух y ются значения †. — и †вЂ, значения кос,> с о ° торых по сигналу с первого выхода блока Зс вычитаются в блоке 14. 25

Результат,, полученный в вычитателе

14, по сигналу с второго выхода блока 2 суммируется в сумматоре 7 со значением у, поступающим из регистра 10. Этот результат является.первым значением у. функции Чх.

По сигналу с первого выхода блока

2 в блоке окончания вычислений сравнивается разность у -у с величиной о допуска Е, определяющей точность вы- З числений.

В случае, если разность превьппает допуск, то на выходе блока 8 остается потенциал, не влияющий на цикличность работы блоков 2 и 3, поэтому4О на выходах блока 3 с восьмого на первый появляются поочередно сигналы, обеспечивающие повторное вычисление приближенного значения у с той разницей, что в регистр 10 заносится 45 через элементы 15 число с выхода сумматора 7.

Цикл вычисления приближенного значения у. продолжается до тех пор, 1 пока не выполняется у. -у Е. Тогда +1 50 по сигналу с первого выхода блока 2 с выхода блока 8 поступает на выход

21 признак окончания вычислений, по которому останавливается распределитель 3 и происходит считывание информации с выхода 23 устройства.

Заметим, что для извлечения корня четвертой степени имеется классический метод Ньютона (1) и (2). у = — (†; +Зу-;), i=0,1,2... (4)

1 х

f+ 1

Как показали вычисления (приложение 2) для одного и того же х, число итераций при заданной точности для алгоритмов (1) и (4) одно и то;ке, но каждая итерация в (1) операции деления.

Таким образом, устройство, использующее алгоритм (1), имеет ряд преимуществ перед известным устройством: автоматически выбирает начальное значение; не использует трудоемкой операции деления; благодаря единообразию вычислительных деиствий работает в параллельном режиме.

П р и л о ж е н и е I. Вводят число х и начальное приближение у9.1

У Э А

2 8

890625 64

1. 7726 32

1. 745323 32

1. 736603 32

1. 733635 32

1. 732604 32

1. 732245 32

l., 732119 32

1. 732075 32

1. 732059 32

1. 732054 32

1. 732052 32

1 732051 32

1. 732051 32

Количество итераций 15

П р и л о ж е н и е 2. Вводят число х и начальное приближение у. х=17368.00 у=40.00000

30,06784

22.71061

17.40364

13.87643

12.03234

11.51678

ll.48006

11.47988

Количество итераций 8

Ньютон

30.06784

22.71061

17.48364

13.87643 .

12.03234

11.51678

11 .48006

11.47988

Количество итераций 8.

S 12Ь2487 формула из обре т ения да

1. Устройство для извлечения корня четвертой степени, содержащее генератор импульсов, два распределителя импульсов, два триггера, элемент

И и сумматор, причем вход запуска генератора импульсов подключен к инверсному выходу первого триггера, а выход генератора импульсов соединен 10 с тактовым входом первого распределителя импульсов и первым входом элемента И, второй вход которого подключен к инверсному выходу второ- го триггера, вход установки в "0" 15 которого соединен с входом установки в "О" первого триггера и с входами запуска первого и второго распределителей импульсов, тактовый вход второго распределителя импульсов подклю- 20 чен.к выходу элемента И, а вход блокировки — к своему первому выходу, первый выход первого распределителя импульсов соединен с входом установки в 1" второго триггера, о т л ич а ю щ е е с я тем, что, с целью увеличения быстродействия устройства за счет повышения однородности и параллельности вычислений,оно содержит блок окончания вычислении, два 30 регистра, два блока нормализации, сдвиговый регистр, вычитатель, группу элементов ИЛИ, два умножителя, квадратор и блок вычисления коэффициента, причем вход установки в "О" первого триггера является входом пуска устройства и подключен к входу запуска блока окончания вычислений, выход которого подключен к входу установки в "1" первого триггера и 40 является выходом признака окончания работы устройства, вход задания точности вычислений блока окончания вычислений является одноименным входом .устройства, стробирующий вход 4S блока окончания вычислений подключен к первому выходу второго распределителя импульсов, второй выход которого подключен к стробирующему входу сумматора, вход первого слагаемого g0 которого подключен к выходу разности вычитателя, вход второго слагаемого сумматора соединен с входом текущей итерации блока окончания вычислений, с входом операнда квадратора, с вхо- 5 дами первого сомножителя первого и второго умножителей и с выходом первого регистра, информационные входы разрядов которого подключены к выхом соответствующих элементов 1Б1И группы, первые входы которых подключены к выходам соответствующих разрядов регистра сдвига, а вторые входы — к выходам соответствующих разрядов сумматора, к входам соответствующих разрядов следующей итерации блока окончания вычислений и к шине результата устройства, третий выход второго распределителя импульсов подключен к стробирующему входу вычитателя, вход уменьшаемого которого подключен к выходу первого блока нормализации, а вход вычитаемого — к выходу второго блока нормализации, входы запуска блоков нормализации подключены к четвертому выходу второго распределителя импульсов, входы нормализующего коэффициента блоков нормализации подключены к выход,. блока вычисления коэффициента, вход нормализуемого значения первого блока нормализации соединен с выходом второго регистра и информационным входом регистра сдвига, вход нормализуемого значения второго блока нормализации подключен к выходу второго умножителя, пятый выход второго распределителя импульсов подключен к стробирующему входу второго умножителя и к входу запуска блока вычисления коэффициента, информационный вход которого.подключен к выходу первого умножителя и к входу второго сомножителя второго умножителя, шестой выход второго распределителя импульсов подключен к стробирующему входу первого умножителя, вход второго сомножителя которого соединен с выходом квадратора, а седьмой и восьмой выходы второго распределителя импульсов подключены соответственно к стробирующему входу квадратора и к входу разрешения записи первого регистра, . входы разрешения записи регистра сдвига и второго регистра подключены соответственно к первому и второму выходам первого распределителя импульсов, информационный вход второго регистра является информационным входом устройства, причем блок окончания вычислений содержит два вычитателя, триггер и элемент И, причем входы уменьшаемого и вычитаемого первого вычитателя подключены соответственно к входам следующей итерации и текущей итерации блока окончания вычислений, выход первого вычитателя подключен к вход вычитаемого второго вычитателя, вход уменьшаемого которого является вхоцом задания точности блока окончания вычислений, а выхоц подключен к входу установки в "1" триггера, вход установки в 0 которого подключен к стробирующим входам вычитателей и к входу. запуска блока окончания вычислений, прямой выход триггера подключен к первому входу элемента И, второй вход и выход 10 которого являются соответственно стробирующим входом и выходом блока окончания вычислений, а блок вычисления коэффициента содержит генератор импульсов, элемент И, триггер 15 и два регистра сдвига, причем выход генератора импульсов подключен к первому входу элемента И, второй вход которого соединен с инверсным выхсдом триггера, а выход элемента И подклю- 20 чен к входу сдвига в сторону младших разрядов первого регистра и к входу сдвига в сторону старших разрядов .второго регистра сдвига, входы младшего разряда которых подключены к 25 входу запуска блока вычисления коэффициента и к входу установки в "1" триггера, вход установки в "О" которого подключен к выходу старшего разряда первого регистра сдвига, информа87 8 циояньш вход которого является информационным входом блска вычисления коэффициента, выход второго регистра сдвига является выходом блока вычисления коэффициента.

2. Устройство по и. 1, о т л и ч а ю щ е е с я тем, что блок нормализации содержит генератор импульсов, элемент И, триггер и два регистра сдвига, причем выход генератора импульсов подключен к первому вхоцу элемента И, второй вход которого подключен к инверсному выходу триггера, а выход элемента И вЂ” к входу сдвига в сторону старших разрядов пе1вого регистра и к входу сдвига в сторону младших разрядов второго регистра сдвига, информационные входы последних являются соответственно входом нормализуемого значения и входом нормализующего коэффициента блока нормализации, входом запуска которого является вход установки в

"О" триггера, вход установки в которого подключен к второму, считая с младшего, разряду выхода второго регистра сдвига, выход первого ре— гистра сдвига является выходом блока нормализации.

I фиг. 1

ping 4

Составитель Н. Захаревич

Техред Л.Сердюкова КорректоР E. Сирохман

Редактор Г. Волкова

Заказ 5428/46 Тираж 671 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4