Устройство для вычисления значения полинома -ой степени Советский патент 1980 года по МПК G06F17/10 G06F7/544 

1

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

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

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

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

Однако известное устройство не может вычислять значение полинома с произволь10 ными коэффициентами, что не позволяет вычислять с его помощью такие важные для практики функции, как , Y cosX, Y aTcigX, y arcshJ, F arcchX и т. д., которые аппроксимируются полиномами с произвольными коэффициентами.

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

20 полинома с произвольными коэффициентами.

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

30 сдвига. На фиг. 1 показана блок-схема устройства для вычисления значения полинома /п-й степени. Она содержит блок 1 управления, регистры 2, 3, 4 сдвига, счетчик 5 переносов, сумматор 6, элементы И 7-10, выход 11 признака сложения блока управления, выход 12 тактирующих импульсов блока управления, выход 13 признака сдвига счетчика переноса блока управления, выходы 14, 15 признака сдвига (соответственно) первого и второго регистров блока управления, выход 16 инверсии признака сложения блока управления, шины 17 ввода аргумента, шины 18 ввода коэффициентов при степенях аргумента. На фиг. 2 показана временная диаграмма работы блока управления в каждом цикле. Здесь 19 - выход четвертого элемента И, если частичное значение полинома 20 - выход четвертого элемента И, если частичное значение полинома Sj,0. На фиг. 3 показана диаграмма перемены содержимого регистров, fJtfe а - расположение чисел в исходном положении; б - расположение чисел после выполнения первого цикла; в - расположение чисел при циркуляции в первом такте второго цикла; г - расположение чисел при циркуляции в (п- 1)-м такте второго цикла; д - расположение чисел при циркуляции в п-м такте второго цикла; е - расположение чисел при циркуляции в (2л-1)-м такте второго цикла. При этом на фиг. 3 обозначено: х,-j-я двоичная цифра аргумента X; а/ -/-я двоичная цифра коэффициента при степени аргумента Aji , 1, 2, ..., п-1, / 0, 1, 2,..., т; bi-г-я двоичная цифра л-разрядного числа . Первый регистр 2 и второй регистр 3 являются (2л-1)-разрядными, а третий регистр 4 - л-разрядным, где л - разрядность двоичных чисел, включая один знаковый разряд, принятая в устройстве. Предлагаемое устройство вычисляет значение полинома с произвольными коэффициентами AjXJ + + + ... + А;г + 4 по алгоритму (схеме) Горнера r {((...((A + + A,,)X + + ...+4) + 4), где У - значение полинома; X - степень аргумента; AJ - /-Й коэффициент при степени аргумента;Хз - /-Я степень аргумента; AjXi - /-Й член полинома; / - номер коэффициента при степени аргумента, номер члена полинома, показатель степени аргумента; т - степень полинома; (т+1)-количество членов полинома; ...l(.,гlX + An, + + ...)частичное значение полинома. /Ь/(; (0,1} -цифры числа 2 f2-. Аргумент 1Х ,2-, , ., . ., где ,1} -цифра t-ro разряда аргумента, является л-разрядным двоичным числом, у которого запятая фиксирована перед дробной частью. Как в известном устройстве, так и в предлагаемом устройстве, аргумент X - число неотрицательное, т. е. -,0, и значение знакового разряда . Коэффициент при степени аргумента , где а/е{0,1}-цифра i-ro разряда /-го коэффициента при степени аргумента, является л-разрядным двоичным числом, у которого запятая фиксирована перед дробной частью. В отличие от известного устройства, в предлагаемом устройстве коэффициент AJ-произвольное число. Если коэффициент Л;,0, то он представлен в прямом коде и значение знакового разряда а 0. Если коэффициент Л; О, то он представлен в дополнительном коде, и значение знакового разряда . Вначале во второй регистр 3 по шинам 17 ввода подается аргумент X старшими разрядами вперед. Одновременно в третий регистр 4 по шинам 18 ввода подается коэффициент Am младшими разрядами вперед. Устройство подготовлено к работе для вычисления значения полинома. На фиг. 3,а изображено расположение чисел в исходном положении.. ., Устройство работает циклически (см. временную диаграмму работы блока управления в каждом цикле, показанную на фиг. 2). Каждый цикл состоит из (2л-1) тактов. В каждом такте на управляющий вход второго регистра 3 сдвига поступает признак сдвига второго регистра из блока 1 управления. Признак сдвига второго регистра представляет собой последовательность из (2л-1) импульсов.. Под ., воздействием признака сдвига второго регистра во втором регистре 3 происходит циркуляция аргумента в каждом такте. В каждом такте на управляющий вход первого регистра 2 сдвига поступает признак сдвига первого регистра из блока 1 управления. Признак сдвига первого регистра представляет собой последовательность из 2п импульсов. Под воздействием признака сдвига первого регистра в каждом такте происходит циркуляция числа, находящегося в первом регистре 2, а кроме того, в каждом такте происходит сдвиг числа, находящегося в первом регистре, на один разряд относительно аргумента, находящегося во втором регистре 3. В результате циркуляции числа, находящегося в первом регистре 2, и циркуляции аргумента, находящегося во втором регистре 3, на выходе первого элемента И 7 получаются цифры поразрядных произведений этих чисел. Под воздействием тактирующих импульсов на первый элемент И 7 в каждом такте происходит передача цифр поразрядных произведений в счетчик 5 переноса. В конце каждого такта па управляющий вход счетчика 5 переноса подастся признак сдвига счетчика переноса из блока управления. Под воздействием признака сдвига счетчика переноса в счетчике 5 переноса происходит сдвиг на один разряд находящегося в нем числа в сторону младших разрядов. В результате на выходе младшего разряда счетчика 5 переноса в конце каждого такта оказывается, начиная с младшей, очередная цифра произведения числа, находящегося в первом регистре 2, и аргумента, находящегося во втором регистре 3. Таким образом, на выходе младшего разряда счетчика 5 переноса в течение одного цикла будут сформированы, начиная с младшей, все {2/г-1) цифры произведения празрядного числа, находящегося в первом регистре 2, и «-разрядного аргумента, находящегося во втором регистре 3. При выполнении второй половины цикла, т. е. в п, («+), ..., (2га-1) тактах блок 1 управления вырабатывает и признаков еложения, под воздействием которых в последовательном сумматоре б происходит сложение, начиная с.младших разрядов, двух чисел, из которых первое число -- старшие п разрядов ()-разрядного произведення, а второе число - очередной п-разрядньтй коэЛЛициент при степени аргумента. Под действием каждого признака сложения происходит передача, начиная с младшей, каждой цифры суммы с выхода последовательного сумматора б через второй элемент И 8 на вход первого регистра 2. Кроме того, под воздействием каждого признака сложения, поданного на управляющий вход третьего регистра 4, происходит сдвиг в сторону младших разрядов на один разряд коэффициента при степени аргумента, хранящегося в третьем регистре 4, а в освобождающийся старщий разряд помещается, начиная с младшей, цифра следующего, начиная со старщего, коэффициента при степени аргумента, который поступает по щинам 18 ввода. Одновременно с признаком сложения блок управления вырабатывает инверсию признака сложения. Под воздействием инверсии признака сложения на третнй элемент И 9, стоящий в цепи циклического переноса первого регистра 2, происходит размыкание цепи циклического переноса в тот момент, когда на вход первого регистра 2 под воздействием признака сложения подается через второй элемент И 8 с выхода последовательного сумматора 6 цифра суммы. Таким образом, осуществляется замена цифр, которые поступают по цепн циклического переноса на вход первого регистра 2, цифрами, которые поступают с выхода последовательного сумматора б, т. е. в первом регистре происходит накопление результата- вычисляемого значения полинома. После (m-fl)-кратного повторения указанного цикла в первом регистре 2 окажется результат - вычисленное значение полинома. Работу устройства целесообразно проследить по диаграмме перемены содержимого регистров, показанной на фиг. 3. После выполнения первого цикла в нервом регистр.е 2 окажется коэффициент Am, во втором регистре 3 - без изменения аргзмент X, в третьем регистре 4 - коэффициент Лт-1 (см. фиг. 3,6). В первом такте второго цикла происходит циркуляция аргумента Л во втором регистре 3 и циркуляния коэффициента Л,,, в первом регистре 2 (см. фиг. 3,s). В результате на выходе младшего разряда счетчика 5 переноса будет сформирована цифра младшего (2п-2)-го разряда произведения Х-А-т. Эта цифра будет o j-An-i. Во втором такте второго цикла на выходе младшего разряда счетчика 5 переноса будет сформирована цифра следующего (2л-3)-го разряда произведения Х-Л„ В (п-1)-м такте второго цикла на выходе младшего разряда счетчика 5 переноса будет сформирована цифра л-го разряда произведения Х-Am (см. фиг. 3,г). В п-м такте второго цикла на выходе последовательного с шматора б будет сформирована цифра младшего (п-1)-го разряда п-разрядного числа X-Am- -Am-i. Эта цифра будет . Она поступает на вход первого регистра 2, заменив собою цифру младшего разряда коэффициента Л„,. Одновременно происходят под воздействием признака сложения сдвиг на один разряд в сторону младших разрядов коэффициента Ат-1 в третьем регг:тре 4 и прием по шинам 18 ввода цифры ajij младшего разряда коэффициента Am-z (см. фиг. 3,д) и т. д.

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

число АтХ+Ат-1, ЦифрЫ КОТОрОГО &о, Ьь

, ..., , во втором регистре 3 - без изменения аргумент X, в третьем регистре 4 - коэффициент Лт-2 (см. фиг. 3,е).

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

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

У (...{(А„,Х: + ...+А,}Х+А,):

т

2

во втором регистре 3 - без изменения аргумент X третий регистр 4 свободен.

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

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

...l( + + +

+ ..

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

В /-М цикле с помощью четвертого элемента И 10 в конце каждого из первых (п-1) тактов значение знакового разряда частичного значения полинома Bj с выхода первого, считая от входа, разряда первого регистра сдвига 2 подается на вход первого регистра сдвига, что соответствует сдвигу числа Bj в прямом коде, если Bj,, и соответствует сдвигу числа Bj в дополнительном коде, если .

Если 5,-,0, то в данном цикле с помощью четвертого элемента И 10 в конце каждого из первых (п-1) тактов значение знакового разряда с выхода первого, считая от входа, разряда первого регистра 2 сдвига подается на вход первого регистра сдвига, что соответствует сдвигу числа 5,-в прямом коде (см. фиг. 2, позицию 20). В этом случае умножение аргумента X на частичное значение полинома Bj происходит в прямом коде точно также, как и в известном устройстве.

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

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

19). В этом случае в отличие от известного З стройства, умножение аргумента X на частичное значение полинома Bj происходит в дополнительном коде без каких-либо преобразований в прямой код, при этом результат X-Bj-.G представлен в дополнительном коде.

Органическим свойством сумматора является обеспечение операции сложения произвольных чисел, если отрицательные слагаемые представлены в дополнительном коде. Поэтому в данном цикле с выхода сумматора 6 через второй элемент И 8 на вход первого регистра 2 сдвига поступает младшими разрядами вперед новое частичное значение полинома Bj+i XBj- -Am-j-i. При этом число Sj+i может быть как положительным, так и отрицательным, поскольку слагаемые X-Bj и Am-j-i могут быть произвольными числами.

В первом цикле , поэтому цифры 6, начального значения полинома В обозначены как а™-г на фиг. 3, б, д.

Использование нового по сравнению с прототипом элемента - четвертого элемента И - и новых связей выгодно отличает предлагаемое устройство расширением функциональных возможностей, заключающихся в обеспечении вычисления значени-я полинома с произвольными коэффициентами, что позволяет вычислять с помощью предлагаемого устройства дополнительно по отношению к известному устройству такие важные для практики функции, как 7, sin J, , Y aTcigX, 7 arcshJ,

y arcch J и т. д., которые аппроксимируются полиномами с произвольными коэффициентами.

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

Устройство для вычисления значения полинома т-й степени по авт. св. № 575648, отличающееся тем, что, с целью расширения класса решаемых задач за счет

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

Источники информации,

принятые во внимание нри экспертизе

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

-„affias:;.

1-4 I I 1-1 :|---Ч1 1-Н -1 I J--I 1

Я

гп-1 гп-1

in

2П

1-й

11

in-f

гп-1

Zn-1

ТТ

.2w

2/7

2/-

If

(in-l}-u

(п-1)-й.п-й

--.- -k

Фиг. 2.

Puz.3a,f,e

Ри.2.3 z,d,e