THE EFFECTIVE ALGORITHM OF EXACT DEFINITION OF UNIVERSAL POSITIONAL CHARACTERISTICS OF MODULAR NUMBERS AND ITS APPLICATION TO CALCULATION OF THE MAIN AREAS OF OPERATIONS IN THE SYSTEM OF RESIDUAL CLASSES

Full Text

Введение Современное состояние развития инфокомму-никационных технологий в области обработки и передачи данных характеризуется интенсивным внедрением новых принципов и подходов к обработке информации. Результаты теоретических и практических разработок отечественных и зарубежных специалистов со всей определенностью указывают на то, что одним из перспективных многообещающих путей решения задач сокращения времени обработки данных и повышения надежности вычислительных средств является применение различных форм параллельной обработки данных, в том числе и на основе числовых систем с параллельной структурой. Одним из магистральных направлений среди современных подходов к созданию отказоустойчивых высокопроизводительных средств обработки данных является использование системы остаточных классов (СОК) [1-5]. Арифметика СОК долгое время вызывала интерес только на теоретическом уровне из-за сложности архитектур, определяемых использованием представляемых данных. Однако быстрый рост технологий вычислительной базы делает СОК удобной для многих приложений цифровой обработки данных, криптографии, систем передачи данных, основанных на множественном до ступе с кодовым разделением каналов, облачных вычислений и др. [6-14] Главным преимуществом СОК является разложение динамического диапазона на параллельные каналы с меньшими динамическими диапазонами, определяемыми выбором оснований СОК, которые приводят к операциям без переноса между каналами с различными основаниями и сокращению задержек сигналов [1-4]. В качестве недостатка СОК можно отметить трудность выполнения немодульных операций [5, 7-9, 14], для выполнения которых необходимо знать информацию о величине числа в целом. Существуют разные подходы к определению характеристик числа в системе остаточных классов, указывающих на его величину. Такие характеристики принято называть позиционными. Система остаточных классов Основной теоретико-числовой базой системы остаточных классов является теория сравнений. Полной системой вычетов по модулю р называется совокупность р целых чисел, содержащая точно по одному представителю из каждого класса вычетов по модулю р. Каждый класс вычетов по модулю р содержит в точности одно из чисел совокупности всех возможных остатков от деления на . Множество {ОД,-,/>-1} также называется полной системой наименьших неотрицательных вычетов по модулю р. Один из методов выполнения арифметических операций над длинными целыми числами основан на простых положениях теории чисел. Представление чисел в СОК позволяет заменить операции с большими числами на операции с малыми числами, которые представлены в виде остатков от деления больших чисел на заранее выбранные взаимно-простые модули Pi,P2’-’Pn. Пусть А = ах(modр^),..., А = ап(modрп). (1) «Инфокоммуникационные технологии» Том 12, № 1, 2014 Бабенко М.Г., Лавриненко И.Н., Ляхов П.А., Червяков Н.И. 5 Тогда целому числу A можно поставить в соответствие кортеж (а1,а2,...,ап) наименьших неотрицательных вычетов по одному из соответствующих классов. Данное соответствие будет взаимно однозначным, пока А<р1р2...рп, в силу Китайской теоремы об остатках (КТО). Кортеж (а1,а2,...,ап^ можно рассматривать как один из способов представления целого числа A в ЭВМ - модулярное представление или представление в СОК. Основным преимуществом такого представления является тот факт, что выполнение операций сложения, вычитания и умножения реализуется очень просто по формулам: А±в = (а1,а2,...,ап)±{р1,р2...,рп) = = ((«1 ±Р1)тод.р1,...,(ап ± Ajmodpj; (2) Ахв = (а1,а1,...,ап)х{р1,р2 ...,Рп) = = ((«i х#)mod/>!»•■•»(«» х A)mod^„). (3) Эти операции носят название модульных, так как для их выполнения в СОК достаточно одного такта обработки численных значений, причем эта обработка происходит параллельно и значения информации в каждом разряде не зависят от других разрядов. Основной недостаток модулярного представления чисел состоит в том, что трудно упорядочить множество всех целочисленных кортежей длины n так, чтобы этот порядок соответствовал естественному порядку на множестве целых чисел. Как следствие этого факта, трудно установить, является ли кортеж (а1,сс2,...,ап) большим (меньшим), чем (P^Pi-.^Pn). Трудно также проверить, возникло ли переполнение допустимого диапазона чисел Р = р1р2-р„ в результате выполнения операций сложения или умножения, но еще труднее выполнить операцию деления. Эти и некоторые другие операции носят название немодульных, так как для их выполнения требуется знание о величине числа в целом, которая называется позиционной характеристикой числа. Модель целочисленной модулярной арифметики можно задать следующей сигнатурой , где: |р| - полная система вычетов по модулю полного динамического диапазона, | • | - вычет чисел по модулю pt, МО - множество ’модульных операций, к которым относятся арифметические операции сложения, вычитания, умножения и деления нацело или умножение на обратный элемент, НО - множест во немодульных операций, к которым относятся расширения база СОК, деления, масштабирования и другие. Немодульные операции обусловлены знанием числового значения модулярной величины, которая определенным образом связана со значениями компонент модулярного представления. Эти операции являются медленными, что снижает эффективность применения модулярной алгебры. Для реализации немодульных операций используются специальные функционалы, которые определяют количественные характеристики отношения порядка над множеством модулярных векторов. Одно из устоявшихся названий функционалов -позиционная характеристика (ПХ) модулярной величины или числовой величины в модулярном коде. В основе алгоритмов выполнения немодульных операций лежат методы вычисления ПХ, сложность которых непосредственно влияет на скорость выполнения немодульных операций в модулярной алгебре. Поиск эффективных и универсальных ПХ важен для теоретических основ модулярных вычислительных структур и вычислительных средств на их основе. В настоящее время известны следующие методы определения позиционных характеристик модулярного представления чисел [1-4]: метод ортогональных базисов, метод функции Эйлера, метод интервальных оценок, метод с использованием коэффициентов обобщенной позиционной системы счисления (ОПСС) и другие. Анализ позиционных характеристик показал, что коэффициенты ОПСС представляют собой универсальную характеристику, на основе которой можно эффективно выполнить основные проблемные операции СОК. Алгоритм эффективного вычисления универсальной позиционной характеристики Суть метода вычисления ОПСС состоит в следующем. Пусть задана система оснований р1,р2,-,р„ с диапазоном Р = р1р2...рп и ортогональными базисами В1,В2,...,Вп, которые определяются как тР - Bi=-!- = \vQodpi,\ = \,n, (4) Pi где mi веса ортогональных базисов. Тогда КТО можно представить в виде * = = (5) i=i /=1 «Инфокоммуникационные технологии» Том 12, № 1, 2014 6 Бабенко М.Г., Лавриненко И.Н., Ляхов П. А., Червяков Н.И. где ai остатки (вычеты) числа X по mod р R(x) - ранг числа. Представим ортогональный базис Bt в ОПСС, тогда Bi =К +bi2PiP2 +- + bi,nPlP2-Pn’ (6) где by - коэффициенты ОПСС, i,j = 1,2 На основе формулы (6) запишем ^0псс ■ ^ОПСС = а\ (^11 > ^12 > • • • > ^1в ) а2 (^215 ^22 > ^23 »• • • > ^2п ) + а3 (631, Ъъ1 ,...,ЬЪп )+... + «„ {ь„л,ьпл ) Так как Bt mod pt = 0 для всех j >i, то перед первым значившим разрядом будут г -1 нулей. Для удобства вычислений базисы можно представить в виде матрицы J\i О 12 22 '1л 2л о о ••• ь п Тогда Х0псс запишется как (7) ^сок «Ап 1А о о I #2^12 I р1 I а2^22 Iр2 О При этом п <*i =T.aibumodPi I апК Iр„ I «Ал I Pn I a b I I n nn I pn > ^ОПСС a\ a2 a„ • (8) by - ортогональные базисы, представленные в ОПСС; i,j = \,2,..,n (9) При использовании традиционной вычисли тельной базы произведения cctby mod pt можно ,, поместить в память, а адресами будут являться где at - коэффициенты ОПСС числа х; at - вы- ^ J J четы числа х по mod pt, остатки сс,. Последовательность вычисления для первого варианта имеет вид Адрес Выборка Модули СОК ПЗУ из ПЗУ Pi P2 Рп -^■сок «1 -» [| # Ai]/>,, «Аг 1 р2 ’• ••>1«А„ 1А] а2 [0, а 2^*22 1 р2 -5|«2^2Л 1А] (10) ап [0, о, ■■>1 «Ал 1 л] -^опсс + flj а2 Для определения всех цифр ОПСС требуются две операции: одна операция для выборки из памяти и одна операция для суммирования. По сравнению с известным последовательным методом Гарнера выигрыш определяется выражением 3(л-1)/2 . Для реализации этого метода необходимо иметь средства для выполнения модулярных операций, например нейронные сети конечного кольца по pt основаниям, где / = 1,2,..., п [2-4]. Пример 1. Пусть основания системы Pi = 3 ’ Р2 = 5»Ръ = 7 » Ра = 2 • Дано число * = [2, 3, 0, 1], представленное в СОК по выбранным модулям. Найти представления этого числа в ОПСС, то есть х - \а1,а2,аъ,а/:\. На основании выражения (4) определим ортогональные базисы СОК В1 =70, В2 =126, Въ =120, ВА =105. Представим базис Bt в ОПСС, тогда by : Ьц 1, Ь\2 3 , &J3 4 , 0 , ^21 = 0, Ь22 = 2 , 623 = 1 ’ ^24 = ^ ’ &32 0 , Ъу2 0 , Ьуj 1, Ь34 1 , Ь^у - 0 , Z?42 - 0 , - 0 , Ьщ - 1 • В связи с тем, что константы by определяются выбором системы модулей СОК, то их с учетом переноса в i разрядах можно поместить в память, тогда процесс преобразований можно представить в виде «Инфокоммуникационные технологии» Том 12, № 1, 2014 Бабенко М.Г., Лавриненко И.Н., Ляхов П.А., Червяков Н.И. 7 Адрес ПЗУ Выборки из ПЗУ ^■сок -^■опсс Модули СОК 3,5,7,2 ах= 2 -» [2, 1, 2, 1] а2 = 3 -» [ОД,4,3] а3=0 -» [0, 0, 0, 0] а4 =1 -» [0, 0, 0, 1] + [2, 2, 6, 1] Для определения всех цифр ОПСС требуются две операции: одна операция для выборки из памяти и одна операция для суммирования. По сравнению с последовательным итерационным процессом [12] выигрыш равен п - 1, где п число модулей СОК. Алгоритмы использования универсальной позиционной характеристики (УПХ) для вычисления основных проблемных операций в СОК Метод расширения базы системы остаточных классов. Рассмотрим метод определения вычета по расширенному основанию на основе использования УПХ. Пусть СОК состоит из оснований р1,р2,...,рп. Объем диапазона этой системы П будет '-П pi . Добавим к числу оснований 1=1 СОК новое основание Рп+\- Объем диапазона л+1 этой системы Pn+l = pt . Тогда любое число 1=1 A из диапазона [0,^л+1) в обобщенной системе счисления представляется в виде п п-\ A = an+lY[Pi+anY{Pi +... + alPl +а0. (П) i=1 i=1 Если число A будет лежать в первоначальном диапазоне [0,Р), то в ОПСС цифра я„+1 = 0. Если ап+1 Ф 0, тогда значение числа A выходит за пределы динамического диапазона. Факт ап+1 =1 используется для получения остатка (вычета) от деления числа A на новое основание СОК Pn+v Пусть число А имело представление (а1,а2,...,ап) по основаниям Р\,Рг^-^Р„-Добавляем новое основание рп+1, тогда число А = (о^, а2ап,| А \р ] в системе оснований р1,р2,...,рп,рп+1 - остаток от деления числа A на рп+1, то есть искомая цифра по новому основанию. Для определения этой цифры используем метод перевода числа из СОК в ОПСС, включая неизвестную цифру | А | в проводимые операции. При этом мы параллельно получим цифры ОПСС а1,а2,...,ап и выражение для цифры С(п+1 . Но так как по условию число Ае[0,Р) , то цифра ап+1 = 0. Из полученного соотношения и определяем искомую цифру \ А\р . Рассмотрим этот метод на примере 2. Пример 2. Пусть задана система модулей рх= 2, />2=3, р3=5, тогда Р = 30. И пусть задано число А = П = (1,2,1). Расширим систему оснований, добавляя р4 = 7. Тогда -4 = 11 = (l,2,l,| А^} в системе оснований Р\ =2, р2 =3, ръ = 5, рл =7. Набор констант btj задается матрицей 1 1 2 3 0 2 1 2 0 0 1 4 0 0 0 4 Процесс решения задачи иллюстрирует таблица 1. Таблица 1. Определение цифр ОПСС Вычеты числа А по модулю Pi Модули Р\~2 р2 =3 Ръ= 5 1п II 1 1 1 2 3 2 0 4 2 4 1 0 0 1 4 1А |7 0 0 0 4-1 jc |7 Коэффициенты ОПСС числа А 1 2 1 5 + 4-1 x |7 После сложения цифр по модулю р получим А = (l,2,l,5 + 4-1 х |7), но так как «Инфокоммуникационные технологии» Том 12, № 1, 2014 8 Бабенко М.Г., Лавриненко И.Н., Ляхов П. А., Червяков Н.И. (-5). 15 + 4-1 х |717, но по условию а4 =0, то есть „ I с I ^ 5 1 4-\AL--5 или А 7 =- - 1 17 ' 17 4 7 4 Мультипликативная обратная величина = 2, и так как число 5 отрицательное, возь- 4 мем его дополнение по модулю 7. Итак, вычет числа А по модулю 7 определяется выражением |Л|7 = 2(7-5) = 4. Тогда расширенное представление числа будет А = 11 = (1,2,1,4). Так как результат образования цифр в СОК по новому основанию рп+1 зависит только от первых цифр, то операцию расширения вычетов можно проводить сразу по нескольким основаниям. Деление и масштабирования чисел в СОК. Деление в модулярной арифметике относится к немодульным операциям и является одной из важнейших операций в модулярной компьютерной арифметике, так как лежит в основе многих других операций и входит в состав операций вычислительных алгоритмов. Операцию деления в СОК можно отнести к одной из трех различных форм [1-2]: деление с нулевым остатком, округление и масштабирование, основное деление. Рассмотрим все основные формы модулярного деления. Деление с нулевым остатком. Для этой формы деления известно, что делимое представляет собой целое число, кратное делителю, а также известно, что делитель и P являются взаимно простыми. Эта категория имеет ограниченную область использования, поскольку должно быть известно априори, удовлетворены ли условия, необходимые для осуществления операции. Для этого алгоритма используется следующая теорема 1. Теорема 1. Если а делится на b без остатка и наибольший общий делитель (НОД) величин а и b равен 1, то а 1 ~Ь Pi - а Ъ (12) Pi для всех р. г где - мультипликативная обрат ная b величина, взятая по модулю р. Доказательство: предположим, что необходимые два условия удовлетворены, тогда alb - это целое число, представленное в остатках, имеет вид (13) / а а а \ ~Ь ъ ?•••? ~ь V Р\ Рг Pn J коде: Выполним вычисление --а в остаточном Ъ pi Рг (14) Рп . или *1й,1-,1 ч„) я , ■Ъ а 1 1 а ■ - ъ \ь\ Pi \b\ Р ь 1 |д Pi b 1 'Pn Pn Pn . (15) Так как a 1*1 b i \Pi Pi =\а\р, следовательно = а (16) По уникальности мультипликативной инверсии следует, что Ъ\р=\а Pi (17) а Если b не делит а, то величина ^ не является а не определено. Следоцелой и выражение pi f.*. 1 ,16- 1 ,12 1 1 9 29 9 32 9 31 J вательно, (1) не имеет смысла. Пример 3. Деление с нулевым остатком. Для модулей /?х=29, р2=32 и рг= 31 разделим число 1872 на 9. Решение: остаточное представление 1872 -это (16, 16, 12). Остаточное представление 9 это - (9, 9, 9), тогда для 1872/9 = 208 остаточный код = (5,16,22) <->208. С другой стороны, если мы делим 1873 на 9 (1873 не делится на 9 без остатка), то получим 1873 / 9 (17,17,13) • (13,25,7) = (l 8,9,29) <-> 6601, что абсолютно неправильно. Масштабирование целых положительных чисел При делении этой формы делимое является произвольным, а делителем может быть любой сомножитель P, представляющий собой произведение первых степеней некоторых модулей. Это деление аналогично делению на степень числа 2 «Инфокоммуникационные технологии» Том 12, № 1, 2014 Бабенко М.Г., Лавриненко И.Н., Ляхов П.А., Червяков Н.И. 9 в двоичной арифметике в том смысле, что деление на числа, принадлежащие определенному ограниченному множеству, выполняется быстрее, чем деление на произвольный делитель. Деление в любой целочисленной системе счисления определяется формулой а= - 'Ь+\а\ь, где а представляет собой дели-а мое, b - делитель, - целая часть отношения а к b (частное), а |я|6 - остаток (наименьший целый положительный остаток). Целью алгоритма масштабирования является нахождение а для значений b из ограниченной области. а-\а\ь Заметим, что системе вычетов ми . Следовательно, в представляется величинагде f а~\а\ь т 55 >£> сз т <3 \ V Ъ 9 Р\ ъ Рг •9 ъ Рп) а-\а\ р принимают целые значения. Если b совпадает с одним из Pi или является произведением первых степеней некоторых модулей pt, то | а \ь можно найти. Тогда по теореме, используемой в форме деления с нулевым остатком, для всех i, для которых НОД величин pt и b равен 1, можно получить (18) а~\а\ь а L( Ъ Pi Ь_ Pt b 1 Это уравнение задает цифры системы выче-а тов для всех таких цифр, что НОД величин р. и Ъ равен 1. Остальные цифры 5 могут быть найдены с помощью метода расширения базы. Таким образом, алгоритм масштабирования состоит из двух следующих этапов. 1. Деление с нулевым остатком. 2. Расширение базы. Процесс масштабирования покажем на числовом примере. Пример 4. Масштабирование положительного числа единичным модулем. Для модулей р1- 2, р2-Ъ, ръ=5 и рА-1 определим остаточное представление значения целого числа . Пусть а имеет остаточный код (l, 2,4,3)<-> 59 . В качестве делителя используется модуль Ръ- Таблица 2. Результаты вычислений остатка по модулю 5 Модули 2 3 5 7 59 1 2 4 3 Вычитаем | а 5= 4 <-> 0 1 4 4 а-1 а 5<-> 1 1 0 6 Решение: сначала определим остаточное представление числа, которое делится на 5 и является ближайшим целым к а, не превышающим а, то есть а- | а |5. Это можно найти путем вычитания остатка а по модулю 5, результаты занесены в таблицу 2. Таблица 3. Умножение a- I a L на Умножаем на 1 Pi а | cl <-> (1Д,-6) (1,2,-,3) (1,2-4) 2,3,7 а-\а\ Результат делится на 5 кроме модуля ръ, который сам является делителем. Все модули простые по отношению к делителю. Применяем метод деления с нулевым остатком, при этом остаточную цифру по модулю 5 временно игнорируем, результаты вычислений в таблице 3. Исходный интервал определения для всего набора модулей был равен [0-209], --оказал ся в интервале [0-41], поэтому остаточное представление (1,2 ...4) неясно. Остаток по модулю 5 может быть найден путем расширения базы. Это можно сделать по методу Гарнера или по предложенному методу в работе [9]. Для этого остаток по модулю 5 примем за 0 в первом случае и за | а |5 - во втором, результат работы приведен в таблице 4. В методе Гарнера для замены вычитания сложением необходимо использовать дополнительный код, при этом для вычитания необходимы «Инфокоммуникационные технологии» Том 12, № 1, 2014 10 Бабенко М.Г., Лавриненко И.Н., Ляхов П. А., Червяков Н.И. Таблица 4. Расширение базы СОК Расширение базы: на основе известного метода Гарнера на основе предложенного метода Номер Модули 2, 3, 5, 7 операции а-1 а 5<-»(1,2,0,4) (1,1,1,1) 1. Вычитаем 1 (0,1,4,3) , .. 1 (-,2,3,4) 2. Умножаем на - 2Й (-,2,2,5) (-,2,2,2) 3. Вычитаем 2 (-,2,2,5) 1 (-,-,2,5) 4. Умножаем на - зй (-,-,o,i) 5. Вычитаем 1 (-,-,4,0) Матрица изменен! 1 2 4- Ms ’ коь шм по 1 1 1 0 2 0 0 0 0 [стант для набора с рядком модулей 2,3,5,7 . 113 2 0 2 4 2 0 0 6 2 0 0 0 3 . Умножение 3 2 -»1 1 3 2 4 2 -»0 2 4 2 6 2 -»0 0 6 2 0 3^0 0 0 31 а |5 Если отсюд 1 1 53 1 ^ -1 1 га обозначить как z5, тогда получим | z51 +4 = 0, 2. Сложение (1,2,1,17 + 31 а |5) 6. | z5 Итак а _~5_ 4 mod 5 = lmod5. = (1,2,1,4) «*11 3. Вычис 17 + 31 а Или | а |5 Итак - _5 ление 5=0 = 0.2 остатка по mod 5 mod 5 = 1. s5 1,4) <->11 две операции. Выигрыш предложенного метода оценивается как 3 Пример 5. Масштабирование положительного числа несколькими модулями. В примере 4 коэф -фициентом масштабирования был только один модуль. В этом примере коэффициентом масштабирования будет произведение двух модулей, а именно 3x5 = 15. Вначале делим на 3, и полученное частное является новым делимым для делителя равного 5, деление на 5 выдает значения целого числа частного. Для завершения операции масштабирования: необходимо выполнить операцию расширения базы. Изменение последовательности деления: сначала выполнить деление на 5, а затем на 3 - не меняет результата. Для модулей р1 = 2 , р2 = 3, р3=5 и р4=7 число а = 89 <-> (1,2,4,5) масштабируем коэффициентом 15. Обозначим а результат 15 как z Решение: расчеты вычислений приведены в таблице 5. Для расширения базы внесем 0 в пропущенные колонки для метода Гарнера и обозначим как | а |3 и | а |5 - для предложенного метода из работы [7], результаты работы методов приведены в таблице 6. Итак, для масштабирования числа большим коэффициентом масштаба используется последовательное деление на простые числа и расширение базы модулей СОК. Математические модели масштабируемых чисел другого знака. Отрицательные числа в СОК «Инфокоммуникационные технологии» Том 12, № 1, 2014 Бабенко М.Г., Лавриненко И.Н., Ляхов П.А., Червяков Н.И. 11 Таблица 5. Первый этап масштабирования чисел несколькими модулями Модули 2, 3, 5, 7 Остаточное представление для а (1,2,4, 5) Вычитаем | а |3= 2 (0,2,2, 3) (1,0,2, 3) 2,3,5,7 <-» а-1 а |3 Умножаем на 1 3 (1.-.2, 5) (1,-4,1) 2, 5,7 a-1 a L <->-1- 3 Вычитаем | а |5= 4 (0, 4,4) (1, -, 0,4) 2, 5,7 a-1 a L <-»---- а , 3 5 Умножаем на 1 5 (1,- - 3) (1, -, 5) Таблица 6. Второй этап масштабирования чисел несколькими модулями Метод Гарнера Предложенный метод 1. Вычитаем 1. (1, 0, 0, 5) (1,1, 1,1) Разобьем матрицу констант для последовательности модулей на 2 матрицы измененной 2. Умножаем на 3. Вычитаем 2. (0,2,4,4) 2, 7, 3 2, 7, 5 2,3,4) Модули 1, з, 1 И 1, з, 2 0, 4, 2 0, 4, 1 (-.1,2, 2) 0, 0, 2 0, 0, 3 (-,2,0,0) 1 Умножаем 1 , , „ 1 , , „ 4. Тогда - z з +2 = 0 и X z 5 +2 2 2 5 Следовательно, z|3=2 И 1 z 5 масштабируемое число 89 15 = 0. это (1, 2, 0, 5) <-> 5. 1- 1, 3, 1 1- 1, з, 2 5- 0, 20, 10 5- 0, 20, 5 х|3' 0, 0, 2-1 х |3 ’ 1X 1з • 0, 0, 9-1 х |3 1, 2, 14 + 2-|х| 1, 2, 10 + 3-|х| Отсюда 14 + 2-1 х |3= 0, |;с|з=-7тос13 = = 2mod3 10 + 3-1 х |5= 0. И5=-ю = 20 mod 5 = 0 mod 5 89 15 = (l, 2, 0, 5)<->5 «Инфокоммуникационные технологии» Том 12, № 1, 2014 12 Бабенко М.Г., Лавриненко И.Н., Ляхов П. А., Червяков Н.И. можно записать как Р - а . Если известно, что число отрицательное, то легко можно его определить из Р - а, затем проводится масштабироа ~Ь вание на b, получаем Р + результаты как Если же знак неизве стен, то возникает определенная сложность. При масштабировании отрицательного числа как будто бы число положительное результатом будет р а а - + вместо необходимого Р + ъ А Ь Поэтому перед масштабированием необходимо определить знак а, этого процесса можно избежать, если принять во внимание следующее обстоятельство: деление на b отображает все числа " Р ' в интервале 0,--1 в интервал 2 b и все числа в интервале Р Р-\ 2 Ъ О, --1 2 Ъ в интервал Отсюда следует, что можно выполнить вначале деление числа на b, а затем, принимая во и затем представляем сло внимание интервал, в котором находится определяется знак а. Если а - отрицательное чиР ъ г для получения правильного ответа Р + то к нему прибавляется по модулю P а Определение интервала, в котором находится требует такого же количества времени, что а А и для определения знака числа. Однако, как было рассмотрено в предыдущем примере, процесс масштабирования требует операции расширения базы модулей СОК на основе цифр ОПСС, поэтому можно определить местонахождение числа - путем использования цифр ОПСС. Ъ _ Рассмотрим метод одновременного масштабирования и распознавания знака. Пример 6. Одновременное масштабирование и определение знака. Для модулей рх =13, ^2=9> Ръ = 119 Рл=7 и р5=2 масштабируем число а - -979 <-> (9,2,0,1, l) на число b - 7-11 с округлением до ближайшего Таблица 6. Второй этап масштабирования чисел несколькими модулями Метод Гарнера Предложенный метод 1. Вычитаем 1. (1, 0,0, 5) ал, 1Л) (О, 2,4,4) 1 Разобьем матрицу констант для последовательности модулей на 2 матрицы измененной 2. Умножаем на 3. Вычитаем 2. (-.2,3,4) (-,1,2,2) (-, 2, 2,2) (-, 2, 0,0) Модули 1 Умножаем 2, 7, 3 2, 7, 5 1, з, 1 и 1, з, 2 0, 4, 2 0, 4, 1 0, 0, 2 0, 0, 3 1 , , „ 1 , , „ 4. Тогда - z L +2 = 0 и - z L +2 2 3 2 5 Следовательно, z |3= 2 и z |5 масштабируемое число 89 15 0. это (1,2,0, 5) <-> 5. 1- 1, з, 1 1- 1, 3, 2 5- о, 20, 10 5- 0, 20, 5 х|3 • 0, 0, 2‘ 1 х з ’ 1 х |3 • 0, 0, 9-1 х |3 1, 2, 14 + 2-|jc|3 Отсюда 1, 2, 10 + 3-|jc|3 14 + 2-1 х |3= 0, x|3=-7mod3 = = 2mod3 10 + 3-1 х |5= 0, -10 = 20mod5 = 0mod5 89 15 = (l, 2, 0, 5)<->5 «Инфокоммуникационные технологии» Том 12, № 1, 2014 Бабенко М.Г., Лавриненко И.Н., Ляхов П.А., Червяков Н.И. 13 Таблица 7. Результаты решения первого этапа примера 6. Модули 13,9,11,7,2 Остаточное представление числа а (9,2,0,1,1) Вычитаем 1 (1,1,1,1,1) (8,1,10, 0,0) Умножаем на 1 7 Pi (2,4, 8,-, 1) (3,4, 3, 0) Вычитаем 3 (3,3,3,-, 1) (0,1,0,-, 1) Умножаем на 1 11 Pt (6,5,-,-, 1) (0,5,-,-, 1) Г^-9791 13, 9,2 <-» - L 7-11 целого числа. Результаты выполнения занесены в таблицу 7. Внесем 0 в пропущенные колонки для расширения базы, см. вычисления, приведенные в таблице 8. Пусть z будет результатом этой операции масштабирования, то есть Р -919 z = - , тогда 7-11 J_ 1 13 9 -\z\n +3 = 0, 1 1 in = 1,---\z\7 +2 = 0, |z|7 = 4. 13 9 В строку (0,5,13’9’2 Р-979 7-11 _ _ добавляем | z |ц, | z |7, тогда остаточное представление z будет равно (0,5,1,4,1). В зависимости от знака а остаточное представление z будет либо либо Р + Цифры ОПСС для z по модулям 13, 4, 2 были вычислены на протяжении процесса масштабирования и обозначились в преобразованиях. Отсюда z можно выразить как z = l(9 • 13) + 8(l 3) + 0(l) .Если a - положительное число, то \ci\p должно быть в интервале Р/2-1 о,- 77 или [0,(9* 13) -1]. Так как наибо лее значимой цифрой ОПСС \z\P является 1, то \z\p, не может входить в этот интервал. Отсюда a должно быть отрицательным. Следовательно, для получения правильного результата необходимо Р ~ъ сложить с | z | р. Для завершения примера необходимо число (0,0,8,4,0) , кото- _Р~ рое является величиной h сложить с числом (0,5,1,4,1). Результатом является число -979 z = 77 = -13. Таблица 8. К решению примера 6. (0, 5, 0,0, 1) Вычитаем 0 (0, 0, 0,0, 0) (0, 5, 0,0, 1) Умножаем на 1 13 Pi (-, 7, 6, 6, 1) (-,§, 0, 0,1) Вычитаем 8 (-, 8, 8,1, 0) (-, 0, 3, 6, 1) Умножаем на 1 9 Pi (-,-,5,4, 1) (- - 4,3, Щ) Вычитаем 1 (-,-,1,1,1) (-,-,3,2, 0) Разработка метода и алгоритма основного модулярного деления. Рассмотренные модели связаны со специальными случаями и не применимы в «Инфокоммуникационные технологии» Том 12, № 1, 2014 14 Бабенко М.Г., Лавриненко И.Н., Ляхов П. А., Червяков Н.И. ситуации, когда и делимое, и делитель представляют собой произвольные целые числа. Различные алгоритмы деления целых чисел а „ „ _ можно описать итеративной схемой, испольъ зующей так называемый метод спуска Ферма [4]. Конструируется некоторое правило ф, ко -торое каждой паре целых положительных чисел а и Ъ ставит в соответствие некоторое целое положительное q, такое, что a - bq = г> 0. Тогда деление а на b осуществляется по следующему правилу: согласно операции j паре чисел а и Ъ ставится в соответствие число q1, такое, что а - bqx = гх > 0. Если гх<Ъ, то деление закончено, если же гх>Ь, то, согласно ф, паре чисел (т}, bj ставится в соответствие q2, такое, что г,-bql =г, >0. Если 02 <Ъ), то деление завершается, если же (г2 > Ъ, то, согласно (рх, паре (r2, b) ставится в соответствие q3 , такое, что r2 - bql = г3 > 0, и так далее. Так как последовательное применение операции ф приводит к строго убывающей последовательности положительных целых чисел а>гх >г2 >г3 >...>0, то процесс является ко -нечным и алгоритм реализуется за конечное число шагов. В общем случае b может быть и не равным модулю или их произведению. Здесь встает проблема выбора b таким, чтобы оно было равным либо модулю, либо их произведению. Если эта проблема будет решена, тогда итерации могут быть сведены к процессу масштабирования, которые рассмотрены выше. Для решения этой проблемы вначале докажем теорему о границах изменения b. Теорема 2. Если на ^-шаге зафиксирован случай 0<rk_x - bqk =гк <Ь, тогда частное q от деления целых чисел а на Ъ будет равк L S'q +r' но “ ' к Если гк < 2 ’ то г'к=0, а если ъ , гк >2’то Гк =1- Доказательство проведем для случая, когда Ь = Л-Ь при Л = 1,2,.... Выполним следующую последовательность действий: 9i = а _ 1 а А “ А А при а =а0; , , 1 а 1 ( П =а-а-=а 1- А Л V К Чг а, Л-Ъ Л-Ъ 1-- Л а2 - &\ ~ ^ (л п а 1 ' п 1 - - ъ - 1 - ^ А у А Л1 ^ Л у а 1 Л 1 - а - Л 'i-l' 'У = а г п с п \ О2 1 - 1- = а\ 1- ; ч А, V "а, \ , aJ ’ Яъ Чк = i а ы 1 1 м 1 1 1 1 л2 Л-Ъ а а 1 ( П 1- А Ъ А Л) ч*-1 > Як=^-’ ЬйЛк+1; ъ qx +q2 +... + qk = 1 • -+ Л л 1 л + + а 1 fi-i] 2 .+ а 1 fi-i] к-1 - . -. + . - . -. А А ч А, А А ^ А, Итак, ^ q. = Прове денные расчеты на ЭВМ приведены на графике рис. 1, где видно, что в качестве делителя лучшие характеристики получаются при Л = 1,2,3,4 . При Л = 1 частное представляет собой точное значение, а при Л = 2 частное при малом числе итераций приближается к точному ее значению. Таким образом, в качестве делителя выбирается величина Ъ < Ъ < 2Ь. к Заметим, что при Л = 1 сумма ^ а Ъ Для вычисления частного с точностью 0,9 и выше значение l целесообразно выбрать равное 2, то есть b<b<2b. Проблема разработки оптимальных вычислительных алгоритмов деления побуждает к разработке таких операций фг, которые бы минимизировали число шагов спуска Ферма и вместе с тем достаточно просто реализовывались на заданной вычислительной базе. Кроме того, на способ формирования операции ф существенно «Инфокоммуникационные технологии» Том 12, № 1, 2014 Бабенко М.Г., Лавриненко И.Н., Ляхов П.А., Червяков Н.И. 15 влияет также принятая система кодирования числовой информации. Теперь возникает еще одна проблема, каким образом полученный приблизительный делитель Ъ свести либо к величине одного модуля или их произведению? 0.9 0.6 0.5 0.4 0.3 0.2 1=] * • * ^ т ^ т 1 = 9 #* ✓ % п ч II_V / У У i / / / / * • / / ' / / 1 г / .1 / /' f ; • Г 1 2 3 4 5 6 7 8 9 Рис. 1. График зависимости точности вычислений от значения величины делителя и числа итераций Предлагается модифицированный модулярный алгоритм деления целых чисел на основе метода спуска Ферма, который направлен на использование деления на приблизительный делитель Ь , в предположении, что b либо целое положительное число попарно простое с Рх^Рц-^Рп^ либо целое положительное число, представляющее собой произведение чисел попарно простых с PuPi >•••> Рп • Этот приблизительный делитель выберем из значения делителя, используемого в применении алгоритма масштабирования. Так как в этом случае b не равно Ъ, ошибка деления будет представлена в частном, которое при выполнении итерации будет уменьшаться до нуля. Допустим, что и делимое а, и делитель b являются положительными числами и что значение для Ъ найдено в соответствии с условием b <Ь <2Ь, где b - это допустимый делитель для алгоритма масштабирования. Метод нахождения b, удовлетворяющий этому условию, рассмотрен выше. В алгоритме деления первым этапом является этап вычисления частного по алгорита ~Ь = му масштабирования, при котором Найденный таким образом ql далее используется в рекурсивных соотношениях ai - ai-1 bqt, а0=а и qt = ai-\ для получения q2, <?з и так далее. Эта повторяющаяся процедура продолжается до тех пор, пока qt = 0, либо до at = 0. Если это возникает на r-ом повторении, то 4 = ~ч'г, где q q, еслиqr ^0иаг =0; 1, если#,. = Ои агЛ > 6 для любыхб фЪ\ 0, иначе. Действительность этого алгоритма зависит от трех предпосылок: 1. Или qi, или at становится нулевым после последнего числа повторений. г-1 2. Ряд + q'r должен быть равен /=о 3. Для любого Ъ существует подходящий b , который определяется из условия Ъ<Ъ<2Ь и удовлетворяет условию алгоритма масштабирования. Приблизительный делитель Ъ можно найти путем использования наиболее значимой ненулевой цифры представленного Ь в полиадической системе счисления. Эту ненулевую цифру заменим ближайшим простым числом или произведением простых чисел. Тогда делитель b можно представить в виде простого числа или произведения простых чисел, что позволит использовать для вычисления частного алгоритм масштабирования. В таблице 9 приведен список допустимых значений Ь для системы модулей 23, 19, 17, 13, 11, 7, 5, 3, и 2. Если система модулей СОК выбрана иной, то таблицу 9 можно аппроксимировать. Для определения b можно составить таблицу 10 приблизительного делителя. Пример 7. В остаточной системе, состоящей из модулей 23, 19, 17, 13, 11, 7, 5, 3, и 2 (Р = 223092870), делим а = 10304312 на а Ь = 1401. Округленное частное q = - |_ b Решение: вначале представим b в обобщенной позиционной системе счисления в порядке уменьшаемой значимости Ь9 = 0, bs= 0, Ь7 = 0, Ь6= 0, Ь5 = 0, Ь4= 0, Ь3= 3, «Инфокоммуникационные технологии» Том 12, № 1, 2014 16 Бабенко М.Г., Лавриненко И.Н., Ляхов П. А., Червяков Н.И. Таблица 9. Цифры приблизительного делителя если bt - 0 для i Ф к ъР 1 2 3 4 5 6 7 8 9 10 11 Q 1 2 3 5 5 3-2 5-2 5-2 5-2 5-2 11 если bt Ф 0 для i Ф к ъР 1 2 3 4 5 6 7 8 9 10 11 Q 1 3 5 5 3-2 7 5-2 5-2 5-2 11 13 если bt - 0 для i Ф к К 12 13 14 15 16 17 18 19 20 21 22 Q 13 13 7-2 5-3 17 17 19 19 7-3 7-3 11-2 если bt Ф 0 для i Ф к ъР 12 13 14 15 16 17 18 19 20 21 22 Q 13 7-2 5-3 17 17 19 19 7-3 7-3 7-3 23 Таблица 10. К определению приблизительного делителя #3 = 607 #4=218 #5=78 #6 =28 о *-н II о II оо #9 =1 5* о II и-* 9п = '1358' .2185. = 0 «з = 477698 а4 = 172280 «5 = 63002 «б = 23774 а7 = 9764 а% ~ 4160 ^ - 2759 «10 - 1358 Ъ2= 3, Ъх = 21, где нения: bt определяем из уравb = 69(23-19-17 -13-11-7-5-3)+ + г»8(23-19-17-13-11-7-5)+ + *7(23 -19 -17 -13 -11 - 7)+ + +г?6 (23-19 17-13-11)+г»5(23 -19 -17 -13)+ £>4 (23 • 19 • 17) ■+ Ъъ (23 • 19)+ Ь2 (23) ■+ Ь,. Используя таблицу 10 с bt=3, получаем 6 = 5-19-23 = 2185 , так как Ь является наиболее значимой ненулевой цифрой обобщенной позиционной системы и определяется выражением, _ к-1 ъ=ап Рг , где Q дано в таблице 10. Отсюда i=1 9i = а “10304312“ _Ь_ 2185 = 4715; а, =а0 -bq1 = 10304312 - (l40l)-(4715) = = 3698597; '3698597' 92 = 2185 =1692; а2 =3698597 - (l40l)-(1692) = 1328105. Далее получаем остальные значения я, и #,, которые приведены в таблице 10. Так как qr=0 (то есть qn =0), но а^^Ь, то q'r= 0. Следовательно ю # = £#,. =4715 + 1692 + 607 + 218 + 78 + 28 + /=1 + 10 + 4 + 1 = 7354. Полученный результат можно легко проверить обычным делением а = 10304312 на 6 = 1401. Для вычисления округленного частного потребовалось десять итераций, так как числа были выбраны обдуманно, чтобы получилось много операций. Это происходит в тех случаях, если a -большое число, а b - относительно малое число и Ъ - аппроксимация b. Модифицируем полученный алгоритм на язык кольцевых операций СОК. Для этого рассмотрим следующий пример. Пример 8. В остаточной системе, состоящей из модулей 7, 5, 3, 2, необходимо разделить число а = 201 -» (5,1,ОД) на число b = 8 -» (1,3,2,0). Округленное частное обозначим как q = - Решение: вначале преобразуем делитель b в ОПСС в порядке уменьшаемой значимости: 6 = 64(7-5-3) + 63(7-5) + 62 1+ ЪХ, тогда 6 = 0-(7- 5-3)+0 -(7-5)+ 1- 7 + 1, где Ь2=\, Ъ,= 1. «Инфокоммуникационные технологии» Том 12, № 1, 2014 Бабенко М.Г., Лавриненко И.Н., Ляхов П.А., Червяков Н.И. 17 Используя таблицу 1 с 1 с Ър = Ъ2 и bt -ф- О _ р-1 i*p, получим Ъ = QY[Pi, где Q = 2 _ i=l 6 = 2-7. или Далее по алгоритму масштабирования, излоа1 I женному выше, находим <1\- ~ , где и - это и _ произведение двух модулей 7 ■ 2: #,=(0,4,2,0)-И4. Используя #,, найдем а\=аъ~ ЪЧ\ = (5Д,ОД) - (1,3,2,0 • 0,4,2,0) = = (5,4,2,l) -» 89. Далее получаем значения ах и : q2= ^ = (б,1,0,0) -> 6; _ъ _ а2=ах- bqx = (5,4,2,l) - (1,3,2,0 • 6Д,0,0) = = (6,1,2,1)->41; Яъ = = (2,2,2,0) -> 2 ; а3 =а2- bq2 = (6,l,2,l)- (l,3,2,0 • 2,2,2,0) = = (4,0,l,l) -> 25; = (1ДДД)-И; а4 = (4,0,1,!)- (1,3,2,0 • 1ДДД) = (3,2,2,1)-И7; Я 5 = ал = (1ДДД)->1); я5 = (3,2,2,1) = (1,3,2,0 • l,l,l,l) = (2,4,0,l) -► 9; Яб - = (1,1,1,1)-И; а6 = (2,4,ОД) - (1,3,2,0 • 1ДДД) = (l,l,l,l). Ъ . Так как а5 > -, то #6 = 1. Следовательно, q = fdqi= (о,4,2,0)+ (6,1,0,0)+ (2,2,2,0) + i-1 + (1,1,1,1)+ (1ДД,1) + (1ДДД) = (4,0,1,1) 25. Действительно а "201" А . 8 . = 25. Заключение В статье представлены проблемные направления в СОК, исследования которых необходимы при проектировании СОК-архитектур следующего поколения. 1. Исследование позиционных характеристик СОК показывает, что коэффициенты ОПСС представляют собой универсальную позиционную характеристику, на основе которой можно эффективно выполнять основные проблемные операции СОК. 2. Показано, что предложенный метод расширения базы позволяет получить расширенное представление вычетов числа сразу по нескольким дополнительным основаниям, что не снижает быстродействия операции расширения при одновременном расширении на несколько модулей СОК. 3. Исследованы модификации алгоритма масштабирования чисел в СОК, которое состоит из операции деления и расширения базы СОК и реализуется с помощью модульных вычислений. Показано, что при использовании модифицированного алгоритма масштабирования, построенного на основе расширения базы, выигрыш вычислительной сложности равен (n - 1) раз. 4. Разработан итерационный модулярный метод общего деления на основе модификации метода спуска Ферма, исходными данными которого являются произвольные значения делимого и делителя. При этом приблизительный делитель выбирается равным простому числу или их произведению, который в дальнейшем используется в итерациях получения промежуточных и окончательного значений частного. Представленная в частном ошибка при выполнении итераций уменьшается до нуля. Если допустимая ошибка задана не выше 0,1, то достаточно провести всего четыре итерации.

About the authors

M. G Babenko

Email: whbear@yandex.ru

I. N Lavrinenko

Email: k-fmf-primath@stavsu.ru

P. A Lyakhov

Email: ljahov@mail.ru

N. I Chervyakov

Email: k-fmf-primath@stavsu.ru

References

Supplementary files