Устройство для вычисления значения полинома -ой степени
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (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