Устройство для возведения чисел в степень четьре

Х 4" И" Е ЕН ИЯ 90279 Союз Советских Социалистических РеспубликТЕЛЬСТВУ У СВ АВТОРСКО ьства М Зависимое от авт вндет МПК 6 061 7/Ь 78/18-24) аявлено 14.Ч.196 с присоединением заявке Комитет по делам изобретений и открыти при Совете Министров СССР,1970 ублпковацо 22 та опубликова юллетец я оппс Авторизобретени ерн Заявите ТРОЙСТВО ДЛЯ ВОЗВЕДЕН И ответствующих разрядов умножителя на коэффициент три, выход каждого г-го разрядакоторого соединен с входом (е+ 1)-го разряда регистра второго блока, выходы разрядов5 этого регистра - с входами соответствующихразрядов ряда сумматоров третьего блока,выходы разрядов этого ряда сумматоров соединены с соответствующими входамп разрядов умножптеля на коэффициент четыре, вы 10 ход каждого е-го раязряда этого умножителясоединен с входом (е - 2)-го разряда другогоряда сумматора третьего блока, выход каждого -го рязряда этого ряда сумматоров соединенс (е+3)-м разрядом регистра результата, вы 15 ходы разрядов квадратора соединены с входами соответствующих разрядов умножцтеляна коэффициент шесть, выходы которых соединены с соответствующими разрядами другогоряда сумматоров третьего блока.20 Построение устройства основано на следующих соображениях.Берется некоторое число, записанное в виде:Ас = а г 1 -+ а г" - - + +- асг-+ а;г + арго,2где а, - цифры числа,г - осцоваццс системы счисления,Это можно представить в виде:+-ао круг сударственный всесоюзный цент институт комплексИзобретение относится к вычислительнои технике и может быть использовано в цифровых вычислительных машинах и устройствах автоматики.Известны устройства для возведения чисел в степень - арифме 1 ические устройства, в которых результат получается многократным умножением числа самого на себя.Целью изобретения является уменьшение количества арифметических операций, необходимых для получения результата.Предлагаемое устройство отличается тем, что содержит квадратор, умцожитель на коэффициент три, умножитель на коэффициент четыре, умножитель на коэффициент шесть, регистр второго блока и регистр результата, причем выход младшего разряда регистра числа соединен с входом младшего разряда регистра результата, выход второго разряда регистра числа - с входом младшего разряда регистра второго блока, выход третьего разряда регистра числа - с входами младших разрядов квадратора и ряда сумматоров второго блока. Выход каждого е-го из остальных разрядов регистра числа соединен с входом (е - 1)-го разряда квадратора, выход каждого е-го разряда квадратора (кроме второго) - с входом (е+1)-го разряда ряда сумматоров второго блока. Выходы разрядов ряда сумматоров второго блока соединены с входами соальный научно-исследовательскийой автоматизации Л В СТЕПЕНЬ ЧЕТЬ 1 РЕ,3лые скобки через А, (индекс при букве А указывает на самую младшую цифру части числа в скобках), получим следующую форму записи числа АоАо = А 1+ аоЧисла в этой записи возводятся в степень д: Ац = (А,+ аоУ: А 4 + С Ао ц 1ао+ + С А 4 гаг2+ ." + Ст А 1 - т. ат ч" - т+ + Ч 1 О " 1 1О+,"., +Со -Аао 1 -+аоо,Степень д у части числа А, здесь сохранилась только в первом члене, все остальные члены разложения содержат более низкие степени части числа без младшей цифры А 1, но часть числа А, содержит на одну цифру меньше, чем исходное число. Аналогичный прием повторяется к первому члену Ао, о (умножение на 1 равносильно сдвигу влево на д разрядов и, следовательно, все члены разложения достаточно сдвинуть на д разрядов влево), Очевидно, что степень д после этого будет содержать также только первый член (Аго ), но число Аг будет уже без двух младших цифр. Продолжая этот процесс и раз, получим некоторую матрицу, сумма строк которой равна степени д исходного числа, но степени всех частей числа будут не выше, чем (д - 1), а в степень д будут возводиться только цифры исходного числа, а не его части. Аналогичным образом теперь можно поступить со всеми членами этого разложения и снизить степень каждого из них еще на единицу,Пусть, например, необходимо возвести в квадрат некоторое число, записанное в виде:а 1 2 и - +аг 2" - 2+,+ а, 2 з+ а, 2 з++ а,21+ ао,Умножение на бином инальный коэффициент 2 в этой матрице выполнено за счет сдвига на разряд влево.Нетрудно убедиться, что число слагаемых цифр в этой матрице:1+(и - 1) ( ) и+ и2 2 где и - разрядность числа, что почти в двараза меньше, чем при обычном способе умножения. Пусть теперь необходимо возвести в кубнекоторое число, записанное в регистре или При возведении этого числа в квадрат каЖ.дый из квадратов слагаемых а;2 преобразуют в а; 22. Так как преобразования осуществляются в двоичной системе счисления, то 5 аг;=а;,а умножение на 2" равносильно сдвигу,влево на 21 разрядов, что соответствует сдвигу на 1 разрядов слагаемого а; 2. Поскольку цифры исходного числа записываются подряд, то квадраты в силу указанного пре образования оказываются записанными черезразряд. После этого прибавляют к квадратам цифр исходного числа удвоенное произведение каж 15 дой цифры на остальные, т, е. произведение вида 2 а; 24 а;2 з, нетрудно видет, что 2 а; 2 а; 21 = а,а; 244Последнее выражение означает, что эти уд 20,военные произведения получаются сдвигом цифры а; влево на число разрядов, равноеБерут самую младшую цифру ао и умножа.25 ют ее на остальные цифры числа, Очевидно,что при этом получится исходное число, сдвинутое на один разряд влево без младшей цифры. Затем берут следующую цифру и умножают на цифры исходного числа без двух 30 младших цифр, что равносильно сдвинутомуисходному числу на два разряда влево без двух младших цифр. Эту операцию продолжают до тех пор, пока не будет умножена предпоследняя цифра на самую старшую.35Складывают полученные произведения сквадратами цифр .исходного числа и получают следующую матрицу, сумма строк которой равна квадрату исходного числа. 40 другом запоминающем устройстве в двоичнойсистеме счисления, например (для большейнаглядности) пятиразрядное в виде:а 424 + аз 2 аг 22 + а,21 + ао 2 о. 45 Для этого возведем в куб это число, которое представим в виде1 (а 423 + аз 22 + аг 21 + а,)+ ао 3. По известному разложению по биному Ньютона 50 получим (а 4 а,а,а,)2+ 3 (а 4 азага,)2 ао 22++3 (а 4 азага,) ао 2 4- ао, но в двоичной системе счисления а 43 = а умножение на а, не(а, аз аг а )з аз а 2 а 1 а,а,а,а 2 а 4 а,З: о х 3 Р аз Х а,аз а. а, Х а,ао Х а,аз а 4 аз а 1 а аг а,аз ао аг аз а,а, Х а,аз аг аз а 4 а 4 аз аг аз а 2 а 4 аз а 4 аз аз Х аг а 4 аз а 4 Я аз а 4 гОагМо а,йа,а, аз а,а 4 аз а 2 а, а,а 4 аз а 2 сдвигает выражения (аазага,), выражение (а 4 азага,) сдвигается влево на разряд, так как степень двойки в самом младшем разряде этого числа равна единице и после возведения в квадрат удвоится, что соответствует сдвигу на один разряд влево, Кроме того, из вышеприведенного примера, возведения числа в квадрат известно, что выражение (агазага 1) равно сумме строк следующей матрицы: Повторим вышеприведенный прием теперь к выражению (а 4 азага,) , Поскольку степень двойки при коэффициенте а 1 равна единице, то (21)з = 2 з, или самый младший разряд этого числа будет размещен на четвертом месте или через два разряда от ао,аг Х а,аз Х ао Щ а 1 Х а,4 а 2 Х а,аз Х а,аг а, Эта матрица построена для пятиразрядного числа (но таким же способом можно построить матрицу для числа произвольной разрядности), Аналогичным образом строятся матрицы более высоких степеней чисел.При аппаратурной реализации приведенного способа необходимо учесть общее свойство этих матриц: составляющие части их, например матрицы квадратов частей числа, построены таким образом, что в матрицу квадрата двух старших цифр входит квадрат старшей цифры, в матрицу квадрата трех старших цифр и т. д.Запишем теперь матрицу квадрата числа для сложения частей исходного числа, начиная со старших разрядов: Перепишем полученный результат с учетом этих соображений и мест цифр в разрядной сетке: 10 Таким образом, матрица для выражения(а,азага,)не отличается от предыдущей, но смещена на три разряда, влево, при этом степень три оттанется у выражения (а 4 азаг) Продолжая этот процесс дальше, получим 15 окончательно следующую матрицу, суммастрок которой равна кубу числа (а 4 азага 1 ао): 25 Очевидно, что для реализации этой матрицы в виде устройства достаточно иметь два регистра: один - исходного числа, а другой - накапливающий сумматор с цепями сдвига влево на два разряда за такт. Вдвигая состо- ЗО роны старших младших разрядов исходноечисло по одному разряду в регистр, а содержимое накапливающего сумматора сдвигая.влево на два разряда за такт и складывая после каждого такта сигнал части числа без цифры, размещенной на месте младшего разряда со сдвигом на разряд влево, и сигнал цифры, размещенной на месте младшего разряда без сдвига с содержанием накапливающего сумматора, в каждом такте будет получать квадрат сигнала части числа, вдвинутого в данный момент в регистр исходного числа.На чертеже изображена схема описываемого устройства. Оно содержит регистр 1 числа, квадратор (регистр 2 первого блока), первый ряд сумматоров 3 первой группы второго блока, умножитель 4 на коэффициент три второго блока, регистр Б,второго блока, первый ряд сумматоров б первой группы третьего блока, умножитель 7 на коэффициент четыре третьего блока, умножитель 8 на коэффициент шесть третьего блока, первый ряд сумматоров 9 второй группы третьего блока и регистр 10 третьего блока (регистр результата),Кроме того, на чертеже приведены следующие обозначения: а; - 1; - разряды соответствующих блоков, причем меньшим цифрам соответствуют младшие разряды.Стрелки на рисунке показывают направление передачи сигнала между разрядами блоков, цифры с буквами у свооодных концов стрелок указывают: цифра на номер разряда, а буква на блок, к которою должен быть подсоединен этот разряд. Регистр 1 имеет семь разрядов, а регистр 2 - десять, разрядность исходных чисел - шесть.Регистры 1, 2, 5 и 10 снабжены цепями сдвига, причем за один такт сдвиг в регистре 1 осуществляется на один разряд влево, в регистре 2 - на два разряда, в регистре 5 - на три разряда и в регистре 10 - на четыре разряда.Вход разряда Ь регистра 2 соединен с выходом разряда аз регистра 1, а входы разрядов Ьз, Ь 4, Ь, и Ьз соединены с выходами разрядов аз, аз, аз и а,ВЫХОДЫ РаЗРЯДОВ С Сз, СЗ И С 4 РЯДа СУММаторов 3 соединены с выходами разрядов аз, а . аз и аз регистра 1. Вторые входы разрядов сз и с 4 ряда сумматоров 3 соединены с выхо- даМИ раЗрядОВ Ь 4 И Ьз рЕГИСтра 2 (ВЫХОД разряда Ьз регистра никуда не подается, так как сигнал, выхода этого разряда всегда соответствует нулевому сигналу, для двоичной системы счисления), Выходы разрядов с-,. сз, с 7, с, и сз ряда сумматоров 3 соединены с выходами РазРЯдов Ь 4, Ьз, Ьз, Ь 7 и Ьз РегистРа 2, Выходы сумматоров 3 поразрядно соединены с входами умножителя 4, биноминальный коэффициент этого блока равен трем. Выходы умножителя 4 соединены с входом регистра 5, причем выход младшего разряда множителя 4 соединен свходом второго разряда регистра 8, Остальные разряды также подсоединены со сдвигом на разряд влево.Выход: регистра 5 соединены с входами 5 10 15 го 25 ЗО 35 40 45 50 55 60 65 8первого ряда сумматоров б первой группь третьего блока, причем младший разряд е регистра 5 соединен с входом разряда з ряда сумматоров б, Остальные разряды подсоединены со сдвигом на два разряда влево. ВхоДы РазРЯДов ь з, з, 14 и з соеДинены с выходами соответственно разрядов а а а 4, аз и аз регистра 1. Выходы ряда сумматоров б поразрядно соединены с входами умножителя 7, Поскольку бином инальный коэффициент этого умножителя равен четырем, то, например, в двоичной системе счисления этот блок может быть опущен, а умножение на четыре выполняют, сдвигая входные сигналы влево на два разряда, т. е, соединяя выходы сумматоров б с входами первого ряда сумматоров 9 второй группы третьего блока со сдвигом на два разряда влево.Выходы регистра 2 соединены непосредственно со входами умножителя 8 (биноминаль. ный коэффициент этого умножителя равен шести),Выходы ряда сумматоров 9 соединены с входами регистра 5, при этом формально не. обходимо было бы соединить младший раз. ряд к с входом разряда ез, но поскольку в качестве примера рассматривается устройство, работающее в двоичной системе счисления, то в связи с тем, что биноминальные коэффициенты для третьего блока - 4 и б, то первый значащий разряд ряда сумматоров 9 будет совпадать с четвертым разрядом регистра 10, таким образом, разряд к, ряда сумматоров 9 соединен с разрядом е 4 регист. ра 10.Работает устройство следующим образом.Исходное число последовательно вдвигают в регистр 1 старшими разрядами вперед. Прн сдвиге на один разряд влево в регистре 1 одновременно производят сдвиги,в регистре 2 на два разряда влево, в регистре б - на три разряда влево и в регистре 10 - на четыре разряда влево. После каждого сдвига анализируют состояние разрядов аь а 2 и аз регистра 1. Если содержимое разряда а, соответствует сигналу единицы (аз = 1), то производят сложение содержимого регистров 1 и 2; если а. = 1, то сложение кода с выхода ряда сумматоров и с содержимым регистра 5 и подают код с выхода умножителя 8 на вход ряда сумматоров 9; если а = 1, то подают код с выходамножителя 7 на вход ряда сумматоров 9. Если же содержимое какого-либо из этих разрядов равно нулю, то существующие операции в данном цикле запрещают.Завершается операция после цикла, следующего за тем сдвигом, когда младший разряд исходного числа займет места разряда аз.Аналогичным образом мажино создать устройства более высоких степеней чисел.Предмет изобретенияУстройство для возведения чисел в степень чстьре, состоящее из регистра числа и накапливающих сумматоров, отличающееся тем,что, с целью повышения быстродействия, оно содержит квадратор, умножитель на коэффициент три, умножитель на коэффициент четыре, умножитель на коэффициент шесть, регистр второго блока и регистр результата, причем выход младшего разряда регистра числа соединен с входом младшего разряда регистра результата, выход второго разряда регистра числа соединен с входом младшего разряда регистра второго блока, выход третьего разряда регистра числа соединен с входами младших разрядов квадратора и ряда сумматоров второго блока, выход каждого -го из остальных разрядов регистра числа соединен с входом ( - 1)-го разряда квадратора, выход каждого -го разряда квадратора (кроме второго) соединен с входом (+ +1) -го разряда ряда сумматоров второго блока, выходы разрядов ряда сумматоров .второго блока соединены с входами соответствующих разрядов умножителя,на коэффи.циент три, выход каждого К-го разряда которого соединен с входом (+ 1)-го разряда регистра второго блока, выходы разрядов 5 этого регистра соединены с входами соответствующих разрядов ряда сумматоров третьего олока, выходы разрядов этого ряда сумматоров соединены с соответствующими входами разрядов умножителя на коэффициент четы ре, выход каждого -го разряда этого умноякитсля соединен с входом (1 - 2)-го разряда другого ряда сумматоров третьего блока, выход каждого -го разряда этого ряда сумматоров соединен с ( + 3) -м разрядом ре гистра результата, выходы разрядов квадратора соединены с входами соответствующих разрядов умножителя на коэффициент шесть, выходы которых соединены с соответствующими разрядами другого ряда сум маторов третьего блока.Заказ 153/18 Изд.83 Тираж 473 Подписное ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР Москва, Ж, Раушская наб., д. 4/5 Тигографпя, пр, Сапунова, 2