Устройство для вычисления значения полинома -ой степени

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (iij744559

Союз Советских

Социалистических

Республик (61) Дополнительное к авт. свид-ву 575648 (22) Заявлено 07.04.78 (21) 2602370/18-24 с присоединением заявки № (51) M. Кл. б 06F 7/38 (43) Опубликовано 30.06.80. Бюллетень № 24 (45) Дата опубликования описания 30.06.80 (53) УДК 681.325 (088.8) по делам изобретений и открытий (72) Авторы изобретения

А. Н. Чуватин и В. А. Чуватина

Кировский политехнический институт (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ЗНАЧЕНИЯ

ПОЛИНОМА т-ой СТЕПЕНИ

ГосУдаРствениый комитет (23) Пр нори гет

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

Наиболее близким по технической сущно- 5 сти к предложенному является устройство (1) для вычисления значения полинома т-й степени, содержащее три регистра сдвига, три элемента И, счетчик переноса, сумматор, блок управления. При этом первый и 10 второй регистры сдвига содержат цепи переноса. Выходы первого и второго регистров через первый элемент И соединены со входом счетчика переноса, Первый вход сумматора соединен с выходом счетчика пе- 15 реноса, второй вход сумматора — с выходом третьего регистра сдвига, а выход сумматора через второй элемент И подсоединен ко входу первого регистра сдвига, выход которого подключен к первому входу третьего элемента И; выход которого подключен ко входу первого регистра, управляющие входы регистров, сумматора, счетчика переноса, первого и второго элементов

И, а также второй вход третьего элемента

И подсоединены к соответствующим выходам блока управления.

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

ЦВМ по сравнению с вычислением функций программными средствами.

Однако известное устройство не может вычислять значение полинома с произвольными коэффициентами, что не позволяет вычислять с его помощью такие важные для практики функции, как Y=sin Х, Y=

=cos Х, Y=arc tgX, У=агс sh X, Y=

=агс ch Х и т. д., которые аппроксимируются полиномами с произвольными коэффициентами.

Целью дополнительного изобретения является расширение класса решаемых задач за счет возможности вычисления значения полинома с произвольными коэффициентами.

Поставленная цель достигается тем, что в устройство по авт. св. № 575648 введен четвертый элемент И, первый, второй и третий входы которого соединены соответственно с выходом блока управления, с управляющим входом счетчика переноса и с выходом первого разряда первого регистра сдвига, а выход — со входом первого регистра сдвига.

744559 где У в значение полинома;

Х вЂ” степень аргументa;

А; — /-й коэффициент при степени аргумента;

Х вЂ” j-я степень аргумента;

А,Х вЂ” 1-й член полинома;

65

На фиг. 1 показана блок-схема устройства для вычисления значения полинома m-й степени.

Она содержит блок 1 управления, регистры 2, 3, 4 сдвига, счетчик 5 переносов, сум- 5 матор 6, элементы И 7 — 10, выход 11 признака сложения блока управления, выход 12 тактирующих импульсов блока управления, выход 13 признака сдвига счетчика переноса блока управления, выходы 14, 15 при- 10 знака сдвига (соответственно) первого и второго регистров блока управления, выход

16 инверсии признака сложения блока управления, шины 17 ввода аргумента, шины

18 ввода коэффициентов при степенях аргу- 15 мента.

На фиг. 2 показана временная диаграмма работы блока управления в каждом цикле.

Здесь 19 — выход четвертого элемента И, если частичное значение полинома В;(О; 20

20 — выход четвертого элемента И, если частичное значение полинома B;,)) 0.

На фиг. 3 показана диаграмма перемены содержимого регистров, 1 де а — расположение чисел в исходном положении; б — рас- 25 положение чисел после выполнения первого цикла; в — расположение чисел при циркуляции в первом такте второго цикла; г— расположение чисел при циркуляции в (n—

1)-м такте второго цикла; д — расположе- ç0 ние чисел при циркуляции в п-м такте второго цикла; е — расположение чисел при. циркуляции в (2п — 1)-м такте второго цикла.

При этом на фиг. 3 обозначено: x; — i-я З5 двоичная цифра аргумента Л; а1 — 1-я двоi ичная цифра коэффициента при степени аргумента А,; i=0, 1, 2, ..., n — 1, j=0, 1, 2,..., т; b; — 1-я двоичная цифра и-разрядного числа А Х+А 1. Первый регистр 2 и вто- 40 рой регистр 3 являются (2п — 1) -разрядными, а третий регистр 4 — n-разрядным, где п — разрядность двоичных чисел, включая один знаковый разряд, принятая в устройстве.

Предлагаемое устройство вычисляет значение полинома с произвольными коэффициентами

Y = А Xl = A + А 1Х - + у=о

+...+АХ+А, по алгоритму (схеме) Горнера

Y = (((...((АЯ+А 1)Х+А 2)Х+

+ ... +А,)Х+А,), j — номер коэффициента при степени аргумента, номер члена полинома, показатель степени аргумента;

m — степень полинома; (m+1) — количество членов полинома;

В = (...((А„Х+ - А. 1) Х+А 2)Х+

+...+А }— частичное значение полинома, 0-1

bJ ((0,1} — цифры числа В;.= g b 2- .

i=0

Аргумент

n — 1

1Х =, Х,2 —, i=0 где Х;е-=(О,Ц вЂ” цифра 1-го разряда аргумента, является п-разрядным двоичным числом, у которого запятая фиксирована перед дробной частью. Как в известном устройстве, так и в предлагаемом устройстве, аргумент

Х вЂ” число неотрицательное, т. е. Х) О, и значение знакового разряда ХО=0.

Коэффициент при степени аргумента

А,= а 2 —, i=0 где a",e(G,Ц вЂ” цифра 1-го разряда j-го коэффициента при степени аргумента, является п-разрядным двоичным числом, у которого запятая фиксирована перед дробной частью. В отличие от известного устройства, в предлагаемом устройстве коэффициент

А; — произвольное число. Если коэффициент А;) О, то он представлен в прямом коде и значение знакового разряда а — 0.

Если коэффициент А;(О, то он представлен в дополнительном коде, и значение знакового разряда а = 1.

Вначале во второй регистр 3 по шинам 17 ввода подается аргумент Х старшими разрядами вперед. Одновременно в третий регистр 4 по шинам 18 ввода подается коэффициент А младшими разрядами вперед.

Устройство подготовлено к работе для вычисления значения полинома. На фиг. 3a изображено расположение чисел в исходном положении.

Устройство работает циклически (см. временную диаграмму работы блока управления в каждом цикле, показанную на фиг.2).

Каждый цикл состоит из (2п — 1) тактов.

В каждом такте на управляющий вход второго регистра 3 сдвига поступает признак сдвига второго регистра из блока 1 управления. Признак сдвига второго регистра представляет собой последовательность из (2п — 1) импульсов. Под воздействием признака сдвига второго регистра во вто ром регистре 3 происходит циркуляция аргумента в каждом такте.

744559

25 происходит сдвиг на один разряд находящегося в нем числа в сторону младших разря- дов. В результате на выходе младшего раз- 60

50 шей, каждой цифры суммы с выхода после- 55 довательного сумматора 6 через второй элемент И 8 на вход первого регистра 2.

В каждом такте на управляющий вход первого регистра 2 сдвига поступает признак сдвига первого регистра из блока 1 управления. Признак сдвига первого регистра представляет собой последовательность из 2п импульсов. Под воздействием признака сдвига первого регистра в каждом такте происходит циркуляция числа, находящегося в первом регистре 2, а кроме того, в каждом такте происходит сдвиг числа, находящегося в первом регистре, на один разряд относительно аргумента, находящегося во втором регистре 3.

В результате циркуляции числа, находящегося в первом регистре 2, и циркуляции аргумента, находящегося во втором регистре 3, на выходе первого элемента И 7 получаются цифры поразрядных произведений этих чисел. Под воздействием тактирующих импульсов на первый элемент И 7 в каждом такте происходит передача цифр поразрядных произведений в счетчик 5 переноса.

В конце каждого такта на управляющий вход счетчика 5 переноса подается признак сдвига счетчика переноса из блока управления. Под воздействием признака сдвига счетчика переноса в счетчике 5 переноса ряда счетчика 5 переноса в конце каждого такта оказывается, начиная с младшей, очередная цифра произведения числа, находящегося в первом регистре 2, и аргумента, находящегося во втором регистре 3.

Таким образом, на выходе младшего разряда счетчика 5 переноса в течение одного цикла будут сформированы, начиная с младшей, все (2n — 1) цифры произведения иразрядного числа, находящегося в первом регистре 2, и и-разрядного аргумента, находящегося во втором регистре 3.

При выполнении второй половины цикла, т. е. в и, (n+1), ..., (2n — 1) тактах блок 1 управления вырабатывает п признаков сложения, под воздействием которых в последовательном сумматоре 6 происходит сложение, начиная с младших разрядов, двух чисел, из которых первое число — старшие и разрядов (2n — 1) -разрядного произведения, а втопое число — очередной и-разрядный коэФАициент при степени аргумента.

Под действием каждого признака сложения происходит передача, начиная с младКроме того, под воздействием каждого ппизнака сложения, поданного на управляющий вход третьего регистра 4, происходит сдвиг в стопону младших разрядов на один разряд коэффициента при степени аргумента, хранящегося в третьем регистре 4, а в освобождающийся старший разряд помещается, начиная с младшей, цифра следую35

45 щего, начиная со старшего, коэффициента при степени аргумента, который поступает по шинам 18 ввода.

Одновременно с признаком сложения блок управления вырабатывает инверсию признака сложения. Под воздействием инверсии признака сложения на третий элемент И 9, стоящий в цепи циклического переноса первого регистра 2, происходит размыкание цепи циклического переноса в тот момент, когда на вход первого регистра 2 под воздействием признака сложения подается через второй элемент И 8 с выхода последовательного сумматора 6 цифра суммы.

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

После (m+ 1)-кратного повторения указанного цикла в первом регистре 2 окажется результат — вычисленное значение полинома.

Работу устройства целесообразно проследить по диаграмме перемены содержимого регистров, показанной нг фиг, 3.

После выполнения первого цикла в первом регистре 2 окажется коэффициент А„, во втором регистре 3 — без изменения аргумент Х, в третьем регистре 4 — коэффициент А», (см. фиг. 3,б).

В первом такте второго цикла происходит циркуляция аргумента Л во втором регистре 3 и циркуляция коэффициента А», в первом регистре 2 (см. фиг. З,в). В результате на выходе младшего разряда счетчика 5 переноса будет сформирована цифра младшего (2n — 2) -ro разряда произведения

Х.А . Эта цифра будет а, Х„ь

Во втором такте второго цикла на выходе младшего разряда счетчика 5 переноса будет сформирована цифра следующего ,(2n — 3) -ro разряда произведения X. A и т. д.

В (и — 1)-м такте второго цикла на выходе младшего разряда счетчика 5 переноса будет сформирована цифра n-ro разряда произведения Х.А (см. фиг. З,г).

В и-м такте второго цикла на выходе последовательного сумматора 6 будет сформирована цифра младц1его (n.— 1)-го разряда и-разрядного числа Х.A»,+А„, ). Эта цифра будет b„,. Она поступает на вход первого регистра 2, заменив собою ци@оу младшего разряда а, коэффициента A„,, Одновременно происходят под воздействием признака сложения сдвиг на один разряд в сторону младших разрядов коэффициента

А 1 в третьем регг-тре 4 и прием по ши нам 18 ввода цифры а — младшего раз744559

А.Х, 40

60 ряда коэффициента А,„ (см. фиг. З,д) и т. д.

После выполнения (2n — 1)-го такта второго цикла в первом регистре 2 окажется число А, Х+А и цифры которого b p, b, b z, ..., Ь <, во втором регистре 3 — без изменения аргумент Х, в третьем регистре

4 — коэффициент А q (см. фиг. З,е).

После выполнения третьего цикла в первом регистре 2 окажется число (А Х+

+А — i) Х+А ь во втором регистре 3 — без изменения аргумента Х, в третьем регистре 4 — коэффициент Am з и т. д.

После повторения цикла (т+1) раз в первом регистре 2 окажется вычисленное значение полинома

V= :(... ((A„Õ+А ) Х+... +А,) Х+А,) = во втором регистре 3 — без изменения аргумент Х третий регистр 4 свободен.

Рассмотрим работу четвертого элемента И 10.

Поскольку коэффициент при степени аргумента А,(j=0, 1, ..., m) может быть как положительным, так и отрицательным числом, то частичное значение полинома

 — {... ((АХ+А 1)Х+А zJХ+

+ ... +АÄÄ;) также может быть как положительным, так и отрицательным числом.

B j-м цикле с помощью четвертого элемента И 10 в конце каждого из первых (и — 1) тактов значение знакового разряда

bop частичного значения полинома В, с выхода первого, считая от входа, разряда первого регистра сдвига 2 подается на вход первого регистра сдвига, что соответствует сдвигу числа В, в прямом коде, если В,,) О, и соответствует сдвигу числа В; в дополнительном коде, если B (О.

Если В;,) 0, то в данном цикле с помощью четвертого элемента И 10 в конце каждого из первых (n — 1) тактов значение знакового разряда b>p â€”вЂ” 0 с выхода первого, считая от входа, разряда первого регистра

2 сдвига подается на вход первого регистра сдвига, что соответствует сдвигу числа В; в прямом коде (см. фиг. 2, позицию 20). В этом случае умножение аргумента Х на частичное значение полинома В; происходит в прямом коде точно также, как и в известном устройстве.

Если В;(О, то в данном цикле с помощью четвертого элемента И 10 в конце каждого из первых (n — 1) тактов значение знакового разряда b p= =l с выхода первого, 10

l5

35 считая от входа, разряда первого регистра сдвига подается на вход первого регистра сдвига, что соответствует сдвигу числа .В. в дополнительном коде (см. фиг. 2, позицию

19). В этом случае в отличие от известного устройства, умножение аргумента Х на частичное значение полинома В; происходит в дополнительном коде без каких-либо преобразований в прямой код, при этом результат К.В,(0 представлен в дополнительном коде.

Органическим свойством сумматора является обеспечение операции сложения произвольных чисел, если отрицательные слагаемые представлены в дополнительном коде.

Поэтому в данном цикле с выхода сумматора 6 через второй элемент И 8 на вход первого регистра 2 сдвига поступает младшими разрядами вперед новое частичное значение полинома В,+ — ХВ;+А; 1. Приэтом число В;+1 может быть как положительным, так и отрицательным, поскольку слагаемые

Х В; и Am — j — могут быть произвольными числами.

В первом цикле Bp —= А, поэтому цифры

ОО„Bp обозначены как а "; на фиг. 3, б, д.

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

=sin Х, Y=cos Х, Y=arctgX, Y=arcshX, Y=агсchХ и т. д., которые аппроксимируются полиномами с произвольными коэффициентами.

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

Устройство для вычисления значения полинома m-й степени по авт. св. № 575648, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемых задач зв счет возможности вычисления "-начепня полинома с произвольными коэффициентами, в устройство введен четвертый элемент И, первый, второй и третий входы которого соединены соответственно с BLI;о. ом блока управления, с управляющим гходом счетчика переноса и с выходом первого разряда ггервого регистра сдвига, а выход — со входом первого регистра сдвига.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР № 575648, кл. G 06F 7/38, 1975 (прототип). г

° ° л

° ° ° (-.«р С (I ир И1 ie И-З Л-2. ° +n -1

° ° ° с

° ° °

Фиг,За,д,У (CZ, i

"2 . а а ° ° о o.. с

„t, Ф

744559 (,И-1 и-г! И-.1 +n-2 1

744559

2 т т ° ° ° 2т m 22m g.,.. д а а а 2 и-1

Хп 1 Хп 2. Х1

Я ï-1

° ° °

ХП -1 Х11 -2 Х1 е

° ° °

Хп-1

° ° ° фиг.а г,д,е

Составитель Н. Шелобанова

Редактор И. Грузова Техред А. Камышникова Корректор 3. Тарасова

Типография, пр. Сапунова, 2

Заказ 771/13 Изд. № 320 Тираж 772 Подписное

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

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