Устройство для вычисления факториала числа Советский патент 1990 года по МПК G06F17/10 

(Л

с

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

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

Цель изобретения - повышение быстродействия устройства.

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

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

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

Перед началом работы отрицательным импульсом по входу начальной установки устройства осуществится сброс первого 3 и второго 20 регистров, первого 4 и второго 5 вычитающих счетчиков, суммирующего счетчика 23. После снятия сигнала начальной установки в накапливающем сумматоре 2 и в первом регистре 3 должна быть записана единица. При этом О с выхода второго регистра 20 осуществится включение генератора 1 импульсов, разрешение подачи импульсов с выхода последнего на вход синхронизации, второго регистра 20, триггера 24. О на выходе первого дешифратора 21 нуля удерживает в нулевом состоянии выход триггера 24, тем самым блокирует счетный .вход счетчика 23 и задает второму регистру 20 режим параллельной записи.

В исходном состоянии после снятия начальной установки элементы И 7, 8,

сп vi

оэ

о

СО

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

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

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

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

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

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

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

5157

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

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

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

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

09(,

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

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

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

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

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

0 которого соединен с выходом третьего элемента НЕ и третьим входом первого элемента И, выход генератора импульсов соединен с первым входом шестого элемента И, второй вход которого соединен с выходом второго дешифратора

5

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

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