Устройство для извлечения корня четвертой степени Советский патент 1986 года по МПК G06F7/552 

to

05

к:

4

00

Изобретение относится к вычислительной технике и может быть исполь зовано в цифровых вычислительных ма шинах . Целью изобретения является увели чение быстродействия устройства путем повьппения однородности и параллельности вычислений. В Основу работы устройства положен итерационный алгоритм вычисления по формуле У. - +У / I ci - 1 of. ; где i - номер итерации (,1,2,... начальное условие у и пара метр о(. определяются по правилу, описанному ниже. Вычисления по формуле (1) прекра щаются при вьшолнении условия ., -y. где f - заданная точность вычислени Известно, что итерационньй проце ,(у. ) 1 0,1,2,... сходится к точному решению при выпо нении условия |.(у)(2 В нашем случае условие (2) в каж дой итерации имеет вид |,,. Если 4;jr , то неравенство (З) всегДа вьтолняется. В виду отсутствия в предлагаемом устройстве операции деления, котора заменяется сдвигом делимого на определенное число двоичных разрядов влево или вправо, значение выбир ется равным ближайшему числу, кратн му степени.двойки с целым показателем, например 4-у.0,128, тогда У, 4у 0,1 . : Начальное значение у находится следующим образом. Определяется зйаченг е х, ближайшее к X, но кратное 2. Показатель k / к делится на четьфе -г где деление числа k заменяется сдвигом его на два разряда), на полученное значени сдвигатеся число х. Например, у v6 , у 2 Итерационный п°роцесс ( 1 ) сходится со знаменателем 3/4, число итера ций при заданной точности вычислени легко определяется из формулы , 3 h In (4-) « n ln(3/) 72 В приложении I приведен расчет вычисления у f 9 по алгоритму (1), где в первом столбце почитаются значения у , во втор(1м столбце значения d . Вычисления проподятся на микроэвм Электроника-бОМ с применением алгоритмического языка BASIC, точность вычислений 10 На фиг. показана структурная схема устройства; . 2 - то же, блока окончания вычислений; на фиг. 3 - то же, блока нормализации;на фиг. 4 - то же,блок вычисления коэффициента. Устройство содержит генератор 1 импульсов, первый 2 и второй 3 распределители импульсов, первый 4 и второй 5 триггеры, элемент И 6, сумматор 7, блок В окончания вычислений, первый 9 и второй 10 регистры, первый 11 и второй 12 блоки нормализации, сдвиговый регистр 13,вычитатель 14, группу 15 элементов ИЛИ, первьй 16 и второй 17 умножители, квадратор 18, блок 19 вычисления коэффициента. Устройство имеет вход 20 пуска, выход 21 признака окончания работы, вход 22 допуска, шину 23 результата, информационный 24 вход. Блок 8 окончания вычислений содержит первый 25 и второй 26 вычитатели, триггер 27 и элемент И 28. Блок окончания вычислений имеет входы следующей итерации 29 и текущей итерации 30, вход 31 допуска, вход 32 запуска, стробирующий 33 вход, выход 34. Блок 11 (12) нормализации содержит генератор 35 импульсов, элемент И 36, триггер 37, первый 38 и второй 39 регистры сдвига. Бпбк нормализации имеет вход 40 нормализуемого значения, вход 41 нормализующего коэффициента, вход 42 запуска, выход 43. Блок 19 вычисления коэффициента содержит генератор 44 импульсов, элемент И 45, триггер 46, первый 47 и второй 48 регистры сдвига. Блок вычисления коэффициента имеет вход 49 запуска, информационный вход 50, выход 51. Устройство работает следующим образом. В исходном состоянии регистры 9, 10, 13 и блоки 11, 12, 19, 8 устанавливаются в нулевое положение. На

шину 24 поступает преобразуемая величина X и по сигналу Пуск, посту. пающему по входу 20, осуществляется запуск устройства. По сигналу с восьмого выхода второго распределителя 3 в регистр 9 заносится число х,по сигналу с седьмого выхода блока 3 в регистр 10 со сдвигом - число х, равное первому значению у , по импуль су с шестого выхода блока 3 - число у, поступающее с регистра 10 чере элементы 15, фиксируется в регистре

13.По сигналу с пятого выхода блока 3 в квадраторе 18 значение у возводится в квадрат, по сиг)шлу с четвертого выхода блока 3 в умножителе

16 вычисляется значение , а по импульсу третьего выхода блока 3 в умножителе 17 формируется у и в блоке 19 значение коэффициента ot по сигналу со второго выхода блока 3 в блоках- 11 и 13 нормализации формируются значения -;.- и ---, значения коа., f-o

торых по сигналу с первого выхода блока Зо( вычитаются в блоке 14. Результат,, полученный в вычитателе

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

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

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

Цикл вычисления приближенного значения у. продолжается до тех пор, пока не выполняется у. -у,, Тогда по сигналу с первого выхода блока 2 с выхода блока 8 поступает на выход 21 признак окончания вычислений, по которому останавливается распределитель 3 и происходит считывание информации с выхода 23 устройства.

Заметим, что для извлечения корня четвертой степени имеется классический метод Ньютона (1) и (2).

., ь +3у;), ,1,2... (4)

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

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

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

У ЭА

2

8

89062564

772632

74532332

73660332

73363532

73260432

73224532

. 73211932

73207532

732059 32

732054.32

732052. 32

73205132

732051 32

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

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

87643 03234 51678 48006

1.47988

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

Ньютон

30.06784

22.71061

17.48364

13.87643 .

12.03234

1 1 .51678

11.48006

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

51

Формула изобретения

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

дам.соответствующих элементов lUIH группы, первые входы которых подключены к выходам соответстпукнцих разрядов регистра сдвига, л вторые вхо5 ды - к выходам соответствующих разрядов сумматора, к входам соответствующих разрядов следующей итерации блока окончания вычислений и к шине результата устройства, третий выход

to второго распределителя импульсов

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

15 выходу второго блока нормализации, входы запуска блоков нормализации подключены к четвертому выходу второго распределителя импульсов, входы нормализующего коэффициента блоков 20 нормализации подключены к выходу блока вычисления коэффициента, вход нормализуемого значения первого блока нормализации соединен с выходом второго регистра и информационным входом

25 регистра сдвига, вход нормализуемого значения второго блока нормализации подключен к выходу второго умножителя, пятый выход второго распределителя импульсов подключен к стробирую30 щему входу второго умножителя и к входу запуска блока вычисления коэффициента, информационный вход которого подключен к выходу первого умножителя и к входу второго сомножителя

35 второго умножителя, шестой выход второго распределителя импульсов подключен к стробирующему входу первого умножителя, вход второго сомножителя которого соединен с выходом

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

5 входы разрешения записи регистра

сдвига и второго регистра подключены соответственно к первому и второму выходам первого распределителя импульсов , информационный вход второго

0 регистра является информационным

входом устройства, причем блок окончания вычислений содержит два вычитателя, триггер и элемент И, причем входы уменьшаемого и вычитаемого первого вычитателя подключены соответственно к входам следующей итерации и текущей итерации блока окончания вычислений, выход первого вычитателя подключен к вxoдv вычитаемого второго 7l вычитателя, вход уменьшаемого которого является иходом : 1адант1я точност блока окончания вычислений, а выход подключен к входу установки в 1 три гера, вход установки в О которого подключен к стробирующим входам вычитателей и к входу.запуска блока окончания вычислений, прямой выход триггера подключен к первому входу элемента И, второй вход и выход которого являются соответственно стробирующим входом и выходом блока окончания вычислений, а блок вычисления коэффициента содержит генератор импульсов, элемент И, триггер и два регистра сдвига, причем выход генератора импульсов подключен к пер вому входу элемента И, второй вход которого соединен с инверсным выходо триггера, а выход элемента И подключен к входу сдвига в сторону младших разрядов первого регистра и к входу сдвига в сторону старших разрядов -второго регистра сдвига, входы младшего разряда которых подключены к входу запуска блока вычисления коэффициента и к входу установки в 1 триггера, вход установки в О котор го подключен к выходу старшего разря да первого регистра сдвига, информа7lUffJrtHbiii вход которого является информационным входом блока выч11слсния коэффициента, выход второго регистра сдвига является выходом блока вычисления коэффициента. 2. Устройство по п. I, о т л и чающееся тем, что блок норма лизации содержит генератор импульсов, элемент И, триггер и два регистра сдвига, причем выход генератора импульсов подключен к первому входу элемента И, второй вход которого подключен к инверсному выходу триггера, а выход элемента И - к входу сдвига в сторону старших разрядов первого регистра и к входу сдвига в сторону младших разрядов второго регистра сдвига, информационные входы последних являются соответственно входом нормализуемого значения и входом нормализующего коэффициента блока нормализации, входом запуска которого является вход установки в О триггера, вход установки в 1 которого подключен к второму, считая с младшего, разряду выхода второго регистра сдвига, выход первого регистра сдвига является выходом блока нормализации.

i/0

j

3S

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

iit

4S

Dd

sr

tS