Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,074

МЕТОД ВЫПОЛНЕНИЯ НЕМОДУЛЬНЫХ ОПЕРАЦИЙ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ НА ОСНОВЕ ИНТЕРВАЛЬНЫХ ПОЗИЦИОННЫХ ХАРАКТЕРИСТИК

Исупов К.С. 1
1 ФГБОУ ВПО «Вятский государственный университет»
Высокая трудоемкость немодульных операций в системе остаточных классов (сравнение по величине, вычитание с получением отрицательного результата, определение переполнения и т.д.) не позволяет в полной мере использовать все достоинства данной системы, заключающиеся в возможности параллельной обработки отдельных разрядов чисел. Точные методы выполнения немодульных операций (преобразование к обобщенной позиционной системе, использование функции ядра, SQT-метод и т.д.) требуют больших временных либо аппаратурных затрат на реализацию, а приближенный метод не всегда позволяет получить корректный результат. В статье предлагается новый метод выполнения немодульных операций в СОК, основанный на концепциях интервальных (доказательных, достоверных) вычислений. Метод обладает низкой вычислительной и аппаратурной сложностью, но при этом обеспечивает получение достоверного результата операции.
система остаточных классов
немодульная операция
достоверные вычисления
интервальная позиционная характеристика
1. Машинная арифметика в остаточных классах / И.Я. Акушский, Д.И. Юдицкий. – М.: Советское радио, 1968. – 440 с.
2. Введение в интервальные вычисления / Г. Алефельд, Ю. Херцбергер. – М.: Мир, 1987. – 360 с.
3. Кнут Д. Искусство программирования для ЭВМ. Т. 2. Получисленные алгоритмы. – М.: Мир, 1977. – 728 с.
4. Достоверные вычисления. Базовые численные методы. / У. Кулиш, Д. Рац, Р. Хаммер, М. Хокс. – М.-Ижевск: НИЦ «Регулярная и хаотическая динамика», 2005. – 496 с.
5. Червяков Н.И. Методы, алгоритмы и техническая реализация основных проблемных операций, выполняемых в системе остаточных классов // Инфокоммуникационные технологии. – 2011. – № 4. – С. 4–12.
6. Приближенный метод выполнения немодульных операций в системе остаточных классов / Н.И. Червяков, В.М. Авербух, М.Г. Бабенко, П.А. Ляхов, А.В. Гладков, А.В. Гапочкин // Фундаментальные исследования. – 2012. – № 6. – С. 189–193.
7. Omondi A. Residue Number Systems theory and Implementation. – London: Imperial College Press, 2007. – 312 p.
8. Wilkinson J.H. Rounding Errors in algebraic processes. – N.Y.: Dover Publications, 1994. – 160 p.

Если задан ряд положительных целых чисел p1, p2, …, pn, называемых основаниями (модулями) системы, то под системой счисления в остаточных классах (СОК) понимают такую систему, в которой целое число X ∈ [0, P – 1], где P = p1∙p2∙...∙pn, представляется в виде остатков по выбранным основаниям [1, 7]:

Eqn12.wmf (1)

т.е. цифра i-го разряда xi числа Eqn13.wmf, называемого модулярным числом, есть наименьший неотрицательный остаток от деления позиционного числа X на pi. Если все pi попарно взаимно простые, то между множеством {X│X ∈ [0, P – 1]} и множеством кортежей Eqn14.wmf однозначным образом определяется биекция Eqn15.wmf, причем прямое преобразование задается в соответствии с (1), а обратное определяется формулой

Eqn16.wmf (2)

Здесь числа Bi представляют собой ортогональные базисы СОК [1].

Определенная таким образом система обладает рядом важных достоинств. Отдельные разряды модулярных чисел малоразрядные и могут обрабатываться без учета переносов между ними, поэтому СОК отвечает многоядерной архитектуре современных вычислительных устройств. На основе СОК могут быть построены эффективные параллельные алгоритмы для решения задач из самых разнообразных областей знаний. Базовые арифметические операции в СОК делятся на следующие две группы [1, 7].

1. Модульные операции, которые могут быть выполнены параллельно и независимо над отдельными цифрами чисел (1), например, сложение, умножение, вычитание без знака и т.д.

2. Немодульные операции, которые требуют знания величины модулярных чисел в целом. К данной группе относятся: сравнение, вычитание с получением отрицательного результата, контроль переполнения модулярного числа и т.д.

Основным фактором, сдерживающим широкое применение СОК на практике, является неочевидность выполнения немодульных операций [1, 3, 5–7].

1. Выполнение немодульных операций в системе остаточных классов

Для выполнения немодульных операций в СОК применяются, как правило, точные методы, основанные на вычислении точных позиционных характеристик модулярных чисел. Всякая позиционная характеристика представляет собой выраженную тем или иным способом информацию о позиционном значении модулярного числа (1). К наиболее известным точным позиционным характеристикам относятся коэффициенты обобщенной позиционной системы счисления (ОПСС), ранг, след, функция ядра и т.д. [1, 3, 7]. Недостатком методов, основанных на вычислении точных позиционных характеристик, является их высокая временная либо аппаратная сложность реализации [7].

Альтернативой точных является приближенный метод выполнения немодульных операций [5, 6]. Он основан на вычислении приближенной позиционной характеристики, которая представляет собой округленное до машинного представления значение отношения анализируемого модулярного числа к произведению модулей СОК. Вычисление приближенной характеристики осуществляется за малое время и при этом не требует хранения больших подстановочных таблиц. При знании приближенных характеристик чисел в СОК операции определения знака, сравнения, обнаружения ошибки и переполнения выполняются простым образом [5, 6]. Однако погрешности округления, возникающие в ходе вычисления приближенной характеристики, могут приводить к некорректному выполнению немодульных операций. Оценить эти погрешности и определить, что операция выполнена некорректно, весьма сложно без знания позиционного значения соответствующего модулярного числа. Это затрудняет использование приближенного метода на практике.

2. Метод выполнения немодульных операций на основе интервальных позиционных характеристик

Определение. Всякую немодульную операцию над модулярными числами будем называть достоверной тогда и только тогда, когда ее результат либо является корректным, либо за время, сопоставимое со временем выполнения данной операции, может быть доказательно определена невозможность получения корректного результата.

Решить проблему достоверности приближенного метода выполнения немодульных операций, сохранив при этом его преимущества, заключающиеся в низкой вычислительной и аппаратурной сложности, позволяет метод, основанный на применении интервальных позиционных характеристик. Предлагаемый метод опирается на базовые концепции интервальных (достоверных, доказательных) вычислений [2, 4] и состоит в следующем.

Пусть в СОК с модулями P = p1, p2, ..., pn задано модулярное число Eqn148.wmf. Пусть Eqn17.wmf – точное значение отношения Eqn18.wmf, где P = p1∙p2∙...∙pn. Eqn17.wmf по определению представляет собой рациональное число, разрядность которого определяется разрядностью P и может быть в общем случае много больше разрядности вычислительного устройства.

Определение. Вещественный интервал Eqn19.wmf с рациональными границами Eqn20.wmf и Eqn21.wmf, направленно округленными до размера разрядной сетки вычислительного устройства и отвечающими условию Eqn22.wmf, называется интервальной позиционной характеристикой модулярного числа Eqn13.wmf. Стоит различать интервальную позиционную характеристику и интервальный номер модулярного числа [1].

Границы, задающие интервальную позиционную характеристику, определяются с помощью направленных округлений: нижняя граница округляется до ближайшего машинного числа с недостатком, а верхняя – с избытком:

Eqn23.wmf (3)

где Eqn24.wmf Здесь операторы ↓ и ↑ отвечают округлениям с недостатком и избытком соответственно. Техника выполнения этих округлений для различных способов представления чисел неоднократно освещалась в литературе (см., например, работы [3, 8]).

Интервальная позиционная характеристика Eqn25.wmf модулярного числа Eqn13.wmf позволяет единообразным способом учесть погрешности округлений, неизбежно возникающие при сопоставлении точному значению Eqn26.wmf представления с ограниченной разрядностью: Eqn27.wmf заключается в гарантированно содержащие это значение границы, направленно округленные до разрядности машинного представления. При этом погрешности округлений лишь несколько расширяют границы, оставляя включение Eqn28.wmf истинным.

Пример. Пусть p1 = 7, p2 = 9, p3 = 11, p4 = 13 – модули СОК, P = 9009 – их произведение,

Eqn29.wmf Eqn30.wmf Eqn31.wmf

Eqn32.wmf – соответствующие мультипликативные инверсии [1, 7]. Тогда интервальная позиционная характеристика модулярного числа Eqn33.wmf определится в соответствии с (3) следующим образом:

Eqn34.wmf

Таким образом, Eqn35.wmf, причем гарантируется, что точное значение Eqn18.wmf лежит в указанном интервале. В соответствии с (2), Eqn36.wmf, поэтому Eqn37.wmf.

Определение. Для любого модулярного числа Eqn13.wmf его интервальная позиционная характеристика Eqn25.wmf является корректной тогда и только тогда, когда Eqn38.wmf.

Необходимым условием правильного выполнения немодульных операций над модулярными числами Eqn13.wmf и Eqn39.wmf с помощью их интервальных позиционных характеристик Eqn25.wmf и Eqn40.wmf соответственно является корректность как Eqn25.wmf, так и Eqn40.wmf.

Определение. Диаметром интервальной позиционной характеристики называется разность ее верхней и нижней границ:

Eqn41.wmf (4)

Погрешности округления границ при вычислении интервальной позиционной характеристики прямым образом отражаются в ее диаметре [4]. Если для машинного представления границ отведено k двоичных разрядов, а модулярное число задается n k-разрядными модулями СОК, то Eqn42.wmf

Определение. Пусть Eqn25.wmf и Eqn40.wmf – интервальные позиционные характеристики модулярных чисел Eqn13.wmf и Eqn39.wmf соответственно. Тогда отношение

Eqn43.wmf

суть теоретико-множественное пересечение Eqn25.wmf и Eqn40.wmf.

Если пересечение не пусто, то его результат может быть представлен интервалом

Eqn44.wmf

причем в этом случае в соответствии с (4) Eqn45.wmf. Если Eqn46.wmf то Eqn47.wmf. Если Eqn25.wmf и Eqn40.wmf пересекаются, то справедливо одно из утверждений:

1. Модулярные числа Eqn13.wmf и Eqn39.wmf равны. В этом случае всякая немодульная операция над ними выполняется интуитивным образом.

2. Модулярные числа различны, но отношение их разности к произведению модулей СОК находится в пределах погрешностей, определяющих диаметры характеристик Eqn25.wmf и Eqn40.wmf. В этом случае выполнение всякой немодульной операции над числами Eqn13.wmf и Eqn39.wmf при помощи Eqn25.wmf и Eqn40.wmf может дать некорректный результат, поэтому следует прибегнуть к использованию точных методов, например, преобразовав Eqn13.wmf и Eqn39.wmf в ОПСС.

Таким образом, достаточным условием корректности выполнения немодульных операций над модулярными числами Eqn13.wmf и Eqn39.wmfс помощью их интервальных позиционных характеристик Eqn25.wmf и Eqn40.wmf является пустое пересечение Eqn47.wmf.

Теорема. Если для модулярных чисел Eqn13.wmf и Eqn39.wmf их интервальные характеристики Eqn25.wmf и Eqn40.wmf корректны (см. определение выше), а Eqn47.wmf, то результат всякой немодульной операции над Eqn13.wmf и Eqn39.wmf, выполняемой при помощи Eqn25.wmf и Eqn40.wmf, будет корректным.

Доказательство теоремы исходит из замечания, что большинство немодульных операций над модулярными числами, так или иначе, сводятся к сравнению по величине этих чисел. Поэтому можно считать, что немодульная операция над Eqn13.wmf и Eqn39.wmf, выполняемая при помощи Eqn25.wmf и Eqn40.wmf, некорректна, если истинно одно из следующих утверждений:

Eqn48.wmf

Далее доказывается невозможность выполнения ни одного из этих утверждений.

Представленная теорема является обоснованием достоверности немодульных операций. Это означает, что всякая немодульная операция над модулярными числами, выполняемая с помощью их интервальных позиционных характеристик, либо будет выполнена корректно, либо будет сделан вывод о невозможности ее корректного выполнения. Арифметические операции сложения и вычитания интервальных характеристик определяются следующими формулами [2, 4]:

Eqn49.wmf (5)

Eqn50.wmf (6)

Умножение и деление определяется аналогичным образом [6, 7]. Правила выполнения основных немодульных операций в СОК с использованием интервальных позиционных характеристик модулярных чисел аналогичны правилам, справедливым для точечного представления приближенной позиционной характеристики, представленным в работах [5, 6]. Пусть, например, Eqn148.wmf и Eqn51.wmf – модулярные числа, а Eqn25.wmf и Eqn40.wmf – их интервальные позиционные характеристики, вычисленные в соответствии с (3) и отвечающие необходимому и достаточному условиям корректности немодульных операций. Тогда сравнение по величине Eqn13.wmf и Eqn39.wmf определится следующим образом:

Eqn52.wmf

Определение переполнения при сложении чисел в СОК выполняется следующим образом:

Eqn53.wmf

Аналогично определяются и другие немодульные операции, такие как контроль переполнения при умножении, определение знака модулярного числа в дополнительном коде, вычитание с возможностью получения отрицательного результата и т.д.

Примеры. Будем использовать следующие модули СОК: p1 = 7, p2 = 9, p3 = 11, p4 = 13, их мультипликативные инверсии:

Eqn54.wmf Eqn55.wmf Eqn56.wmf

Eqn57.wmf

1) Выполним сравнение Eqn58.wmf и Eqn59.wmf. Для этого определим их интервальные характеристики в соответствии с выражением (3), округляя границы до двух разрядов:

Eqn60.wmf Eqn61.wmf

Eqn62.wmf Eqn63.wmf

таким образом Eqn64.wmf, Eqn65.wmf. Данные характеристики корректны, а Eqn66.wmf поэтому заключаем, что операция сравнения чисел Eqn13.wmf и Eqn39.wmfс их помощью будет выполнена верно. Выполняя вычитание в соответствии с (6), получим

Eqn67.wmf,

поэтому Eqn68.wmf. И действительно

Eqn69.wmf

Eqn70.wmf

2) Пусть Eqn71.wmf, Eqn72.wmf и требуется определить, произойдет или нет переполнение при их сложении. Определяем интервальные позиционные характеристики: Eqn73.wmf, Eqn74.wmf. Данные характеристики отвечают необходимому и достаточному условиям корректности выполнения немодульной операции. В соответствии с (5) имеем:

Eqn75.wmf,

следовательно, при сложении Eqn13.wmf и Eqn39.wmf произойдет переполнение. В правильности полученного вывода можно убедиться, преобразовав операнды в позиционную систему:

Eqn76.wmf

Eqn77.wmf

Вычисление первой границы интервальной характеристики требует n обращений к LUT-памяти за значениями мультипликативных инверсий, n умножений, n делений и одну операцию n-операндного суммирования с отбрасыванием целой части, которая выполнится (последовательно) также за n тактов. При вычислении второй границы значения произведений модулярных разрядов и соответствующих мультипликативных инверсий (слагаемые Ni в (3)) уже будут вычислены, поэтому необходимо лишь поделить их на модули СОК, округ­лив соответствующим образом, и сложить. Таким образом, вычисление интервальной позиционной характеристики требует выполнения 6n операций над машинными числами (n – количество модулей СОК). Для сравнения, алгоритм Гарнера [3], основанный на использовании в качестве позиционной характеристики коэффициентов ОПСС, требует для их определения в среднем n2 операций.

Заключение

Предложен асимптотически быстрый метод выполнения немодульных операций в СОК, основанный на использовании интервальных позиционных характеристик для оценки величины модулярных чисел. Данный метод обеспечивает достоверность выполняемых операций в отличие от приближенного метода и не требует больших вычислительных либо аппаратурных затрат в отличие от известных точных методов. Алгоритм вычисления интервальных позиционных характеристик не требует работы с числами, выходящими за пределы разрядной сетки, а его временная сложность линейна по количеству модулей СОК. Таким образом, предложенный метод является полезной альтернативой известным методам выполнения немодульных операций в СОК.

Рецензенты:

Частиков А.В., д.т.н., профессор, декан факультета прикладной математики и телекоммуникаций Вятского государственного университета, г. Киров;

Страбыкин Д.А., д.т.н., профессор, заведующий кафедрой электронных вычислительных машин Вятского государственного университета, г. Киров.

Работа поступила в редакцию 22.02.2013


Библиографическая ссылка

Исупов К.С. МЕТОД ВЫПОЛНЕНИЯ НЕМОДУЛЬНЫХ ОПЕРАЦИЙ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ НА ОСНОВЕ ИНТЕРВАЛЬНЫХ ПОЗИЦИОННЫХ ХАРАКТЕРИСТИК // Фундаментальные исследования. – 2013. – № 4-3. – С. 566-570;
URL: http://www.fundamental-research.ru/ru/article/view?id=31233 (дата обращения: 21.10.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074