Устройство для вычисления факториала числа

 

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

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК

„„Я0„„1571609 (ц)5 G 06 F 15/31

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГННТ СССР

° .. а"ггпу

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

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

«Ф (21) 4478541/24-24 (22) 29.08. 88 (46) 15.06.90. Бюл. N - 22 (72) И.Н.Кузьо, А.А.Самчинский и Е.Л.Помыткина (53) 681.325(088.8) (56) Авторское свидетельство СССР

У 1120345, кл. G 06 F 15/31, 1984.

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

11 1297071, кл. G. 06 Г 15/31, 1986. (54) УСТРОЙСТВО ДЛЯ ВЬ1ЧИСЛЕНИЯ ФАКТОРИАЛА ЧИСЛА (57) Изобретение относится к вычислительной технике и может быть использовано для вычисления функций в спеВ исходном состоянии после снятия начальной установки элементы И 7, 8, Изобретение относится к вычислительной технике и может быть использовано для вычисления функций в специализированных вычислительных системах. . Цель изобретения — повышение. быстродействия устройства.

На чертеже представлена структурная схема устройства.

Устройство содержит генератор 1 импульсон, накапливающий сумматор 2, первый регистр 3, вычитающие счетчики 4 и 5, элементы И 6 — 11, элементы ИЛИ 12 — 15, элементы НЕ 16 - 19, второй регистр 20, .первый 21 и второй 22 дешифраторы нуля, суммирующий счетчик 23, триггер 24.

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

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

3 ки устройства осуществится сброс первого 3 и второго 20 регистров, перво- 2 го 4 и второго 5 вычитающих счетчиков, суммирующего счетчика 23. После снятия сигнала начальной установки в на капливающем сумматоре 2 и в первом

Фи регистре 3 должна быть записана единица ° При этом "0 1 с выхода второго е регистра 20 осуществится включениа генератора 1 импульсов, разрешение подачи импульсов с выхода последнего на вход синхронизации. второго регистра 20, триггера 24. "0" на выходе первого дешифратора 21 нуля удерживает ф в нулевом состоянии выход триггера

24, тем самым блокирует счетный .вход

Ь счетчика 23 и задает второму регистру 20 режим параллельной записи.

157!609

10 будут заблокированы нулевым состоянием информации на выходах первого вычитающего счетчика 4. С каждым импульсом на входе второго регистра 20 осуществится запись нулевой информации с выхода в" îðîãî вычитающего счетчика 5, которая не изменит состояния работы устройства.

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

Множнтели факториала заданного числа задаются поочередно, начиная с большего ег о значения, во втором вы-. читающем счетчике 5.при вычитании в каждом цикле вычисления единицы из его содержимого. Циклы вычислений для нечетных множителей факториала заданного числа реализуются путем накоплений, а четных — путем выделения п-раз-,> рядного двоичного числа, кратного четному множителю, его хранением с последующим количеством накоплений, I равным остатку при делении четного множителя на п-разрядное двоичное 40 число. Вместе с тем содержимое второго вь|читающего счечтика 5, т.е. значение очередного множителя, определяет количество накоплений в накапливающем сумматоре 2, в последуюц1ем 45 цикле вычисления.

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

Ненулевое значение информации на выходах регистра 20 задает ему через первый дешифратор 2 1 нуля режим сдвига информации влево (в сторону младших разрядов), При этом сигнал сброса триггера 24 отсутствует.

Если во второй регистр 20 записано двоичное значение четного числа, признаком четности которого является

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

Если во второй регистр 20 записано двоичное значение нечетного числа, то на его выходе вызовет запись значения этого числа в первый вычитающий счетчик 4. !

После записи в первый вычитающий счетчик 4 двоичного значения любого числа, а оно всегда будет нечетное, устройство непосредственно реализует процесс накопления в накапливающем сумматоре 2. Количество накоплений будет на единицу меньше значения нечетного числа. "1" с выхода элемента ИЛИ 13 осуществится выключение режима записи для первого вычитаюцего счетчика 4, включение генератора 1 импульсов, разрешение подачи импульсон с генератора 1 импульсов на вход вычитания первoro вычитающего счетчика 4 и на вход накапливающего сумматора 2. А по переднему фронту сигнала на ныходе элемента НЕ 17 осуществляется вычитание единицы иэ содержимого второго вычитающего счетчика 5. На- . копление в накапливающем сумматоре 2 произойдет до тех пор пока содержимое перного вычитающего счетчика 4 станет равным двоичному значению единицы.

"0" с выхода второго дешифратора 22 нуля заблокируется работа элемента

5 157

И 10, с выхода элемента И 9 осуществится сброс второго регистра 20 °

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

Рассмотрим пример работы устройства при вычислении факториала числа три. Факториал числа три содержит в себе множители 1 — 3, из которых дв а нечетных и один четный. В накапливающем сумматоре 2 в цикле вычитания для нечетного множителя 3 осуществляется два накопления. В результате чего в первый регистр 3 будет записан первый промежуточный результат вычисления, равный двоичному значению числа 3. Для четного множителя 2 цикл вычисления заключается только в выделении двоичного числа, кратного числу 2, в результате чего содержимое счетчика станет равным 1. Для следующего нечетного множителя 1 количество .накоплений равно нулю. Итак, результат вычисления факториала заданного числа содержится в первом регистре 3 и счетчике 23 и равен соответсгвенно

3 и 2, произведение которых равно 6.

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

1609 I5

45 разрешения записи второго вычитающего счетчика, выход переполнения которого соединен с выходом готовности устройства, информационный вход накапливающего сумматора соединен с первым информационным выходом устройства и выходом первого регистра, о т л и ч а юб щ е е с я тем, что, с целью повьппения быстродействия, в него введены с второго по шестой элементы И, с второго по четвертый элементы НЕ, с первого по четвертый элементы ИЛИ, суммирующий счетчик, второй регистр, второй дешифратор нуля и триггер, причем вход синхронизации устройства соединен с первым входом первого элемента И, второй вход которого соединен с выходом генератора импульсов и первым входом второго элемента И, второй вход которого соединен с выходом третьего элемента И и первым входом первого элемента ИЛИ, выход и второй вход которого соединены соответственно с входом запуска генератора импульсов и третьим входом первого элемента И, выход переполнения первого вычитающего счетчика соединен с первым входом второго элемента ИЛИ и через первый элемент НЕ с первым входом третьего элемента ИЛИ, выход которого соединен с первым входом четвертого элемента И, второй вход которого соединен с входом чачальной установки устройства и входом сброса суммирующего счетчика, вход синхронизации которого соединен с выходом пятого элемента И, первый вход которого соединен с выходом первого элемента

И, входом синхронизации второго регистра и входом синхронизации триггера, прямой выход которого соединен с вторым входом пятого элемента И, выход второго элемента ИЛИ соединен с первым входом четвертого элемента ИЛИ и первым входом третьего элемента И, второй вход которого соединен с вхо50

55 устройство для вычисления факториала числа, содержащее генератор импульсов, накапливающии сумматор, первый регистр, первый и второй вычитающие счетчики, первый элемент И, первый дешифратор нуля, первый элемент

HE причем вход начальной установки устройства соедйнен с входом сброса первого и второго вычитающих счетчиков и первого регистра, вход синхронизации устройства соединен с входом дом второго элемента НЕ и выходом четвертого элемента KIN, второй вход которого соединен с выходом третьего элемента НЕ и третьим входом первого элемента И, выход генератора импульсов соединен с первым входом шестого элемента И, второй вход которого соединен с выходом второго дешифратора нуля, вторьгж входами второго и третьего элементов ИЛИ и через четвертый элемент НЕ с входом синхронизации первого регистра, выход шестого эле1571609

Составитель А.Зорин

Редактор О.Спесивых Техред M.Äèäûê Корректор 0 Чипле

Заказ 1514 Тираж 5б9 Подписное

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

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

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

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