Математика / 2.Перспективы информационных систем

Д.т.н. Князьков В.С., аспирант Исупов К.С.

Вятский государственный университет, Россия

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

 

Введение

Если задан ряд положительных целых чисел , называемых в дальнейшем основаниями (модулями) системы, то под системой счисления в остаточных классах (СОК) понимают такую систему, в которой целое положительное число X представляется в виде остатков (вычетов) по выбранным основаниям [1, 2]:

                                        ,                                           (1)

причем образование цифр xi осуществляется следующим процессом

                                                                       (2)

т.е. цифра i-го разряда xi числа , называемого модулярным числом, есть наименьший неотрицательный остаток от деления позиционного числа X на pi. Если числа pi взаимно-простые между собой, то между  и , где , существует биективное отображение , причем обратное отображение  может быть явно определено следующим образом:

                                          ,                                            (3)

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

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

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

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

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

 

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

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

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

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

 

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

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

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

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

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

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

                         ,                    (4)

где  .  Выражения (4) достаточно просто выводятся из китайской теоремы об остатках. Операторы  и  отвечают округлениям «вниз» (с недостатком) и «вверх» (с избытком) соответственно. Техника выполнения этих округлений для различных способов представления чисел неоднократно освещалась в литературе (см. например, работы [3, 8, 9]).

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

Пример. Пусть p1 = 7, p2 = 9, p3 = 11, p4 = 13 – модули СОК, P = 9009 – их произведение, , , ,  – соответствующие мультипликативные инверсии. Тогда интервальная позиционная характеристика модулярного числа  определится в соответствии с (4) следующим образом:

Таким образом, , при этом можно утверждать, что точное значение отношения  лежит в указанном интервале. И действительно, в соответствии с (3), , следовательно .                                          □

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

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

Погрешности округления границ при вычислении интервальной позиционной характеристики прямым образом отражаются в ее диаметре [7].

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

                                     .                                       (5)

Не сложно показать, что если для машинного представления границ отведено k двоичных разрядов, и при этом модулярное число задается в СОК с n k-разрядными модулями, то .

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

представляет собой теоретико-множественное пересечение  и . Если пересечение не пусто, то результат этой операции может быть представлен интервалом

,

причем в этом случае, в соответствии с (5), . Если , то .

Если  и  пересекаются, то справедливо одно из утверждений:

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

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

Таким образом, достаточным условием корректности выполнения немодульных операций над модулярными числами  и  () с помощью их интервальных позиционных характеристик  и  является пустое пересечение .

Следующая теорема обобщает необходимое и достаточное условия корректного выполнения немодульных операций.

Теорема. Если интервальные позиционные характеристики  и  не равных между собой модулярных чисел  и  корректны (в смысле, определенном ранее) и не пересекаются, то результат всякой немодульной операции над  и , выполняемой при помощи  и , будет корректным.

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

.

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

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

Арифметические операции сложения и вычитания интервальных позиционных характеристик определяются следующими формулами [6, 7]:

                           ,                      (6)

                           .                      (7)

Умножение и деление определяется аналогичным образом [6, 7].

Правила выполнения основных немодульных операций в СОК с использованием интервальных позиционных характеристик аналогичны известным правилам, справедливым для точечного представления приближенной позиционной характеристики, представленным в работах [4, 5]. Пусть, например,  и  – модулярные числа, а  и  – их интервальные позиционные характеристики, вычисленные в соответствии с (4), и отвечающие необходимому и достаточному условиям корректности немодульных операций. Тогда сравнение по величине  и  определится следующим образом:

Определение переполнения при сложении модулярных чисел выполняется тривиальным анализом условий:

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

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

1) Выполним сравнение модулярных чисел  и . Для этого определим их интервальные позиционные характеристики в соответствии с выражениями (4) с округлением границ до двух значимых разрядов после точки: , , , . Таким образом, , . Данные характеристики достоверны, а  , поэтому заключаем, что операция сравнения чисел  и  с их помощью будет выполнена корректно. Выполняя вычитание в соответствии с (7), получим , поэтому . И действительно, , .

2) Пусть ,  и требуется определить, произойдет ли переполнение при сложении. Определяем интервальные позиционные характеристики: , . Данные характеристики отвечают необходимому и достаточному условиям корректности выполнения немодульной операции. В соответствии с (6): , следовательно, при сложении  и  произойдет переполнение. Выполним проверку, преобразовав слагаемые в позиционную систему: , . Произведение модулей СОК составляет 9009, следовательно, при сложении   и  действительно произойдет переполнение. □

Алгоритм вычисления каждой границы интервальной позиционной характеристики требует n обращений к подстановочной памяти за значениями мультипликативных инверсий, n умножений, n делений, и одну операцию n-операндного суммирования с отбрасыванием целой части, которая выполнится так же за n тактов. Таким образом, последовательный алгоритм вычисления каждой границы интервальной характеристики требует выполнения 4n арифметических операций над числами, не превышающими разрядность вычислительных устройств. Соответственно, вычисление двух границ потребует выполнения 8n арифметических операций, где n – количество модулей СОК. Таким образом, предлагаемый метод выполнения немодульных операций обладает линейной сложностью . Для сравнения, алгоритм Гарнера [3, 10], основанный на использовании в качестве позиционной характеристики коэффициентов ОПСС, требует для их определения приблизительно   операций.

 

Заключение

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

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

 

Литература:

1. Акушский И.Я. Машинная арифметика в остаточных классах / И.Я. Акушский, Д.И. Юдицкий. – М.: Советское радио, 1968. – 440 с.

2. Omondi A. Residue Number Systems theory and Implementation. – London : Imperial College Press, 2007. – 312 p.

3. Кнут Д. Искусство программирования для ЭВМ. Т. 2. Получисленные алгоритмы. Пер. с англ. – М.: Мир, 1977. – 728 с.

4. Приближенный метод выполнения немодульных операций в системе остаточных классов / Червяков Н.И., Авербух В.М., Бабенко М.Г., Ляхов П.А., Гладков А.В., Гапочкин А.В. // Фундаментальные исследования. – 2012. – №6. – С. 189–193.

5. Червяков Н.И. Методы, алгоритмы и техническая реализация основных проблемных операций, выполняемых в системе остаточных классов // Инфокоммуникационные технологии. – 2011. – №4. – С. 4–12.

6. Алефельд Г. Введение в интервальные вычисления / Г. Алефельд, Ю. Херцбергер. – М.: Мир, 1987. – 360 с.

7. Кулиш У. Достоверные вычисления. Базовые численные методы [Текст] / У. Кулиш, Д. Рац, Р. Хаммер, М. Хокс. – Пер. с англ. – Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика», 2005. – 496 с. – ISBN: 0-387-57118-3.

8. I. Kupka. Simulation reeller Arithmetik und reeller funktionen in endlichen Mengen [Text] /  Ivan Kupka // Numerische Mathematik, 1971, Vol. 17, Issue 2, pp. 143–152.

9. J. H. Wilkinson. Rounding Errors in algebraic processes [Text] / James Hardy Wilkinson // London: H.M. Stationery Office, 1968. Print.

10. Нестеренко А. Введение в современную криптографию. Теоретико-числовые алгоритмы [Электронный ресурс] / Алексей Нестеренко. – URL: http://img0.liveinternet.ru/images/attach/c/4//3908/3908902_ntheory.pdf, 2011. – 190 с.