Рекурсивная модулярная арифметика

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Принцип рекурсивных модулярных вычислений[править | править вики-текст]

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

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

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

Представление данных и основные операции рекурсивной модулярной арифметики[править | править вики-текст]

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

Пусть задана система модулей и задан некоторый вектор . Выразим через систему субмодулей

, где и : .

В этом случае вектор A можно представить в следующем виде:

, см. рисунок 1.


Рис.1. Иерархия в модулярной арифметике


Назовем систему из m младших модулей системой базовых модулей, а их произведение обозначим .

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


Рис.2. Рекурсивное разложение элемента p6 через систему субмодулей (p1,p2,p3)

Пример представления данных[править | править вики-текст]

Поясним процедуру рекурсивных преобразований на простом примере. Возьмем в качестве базисных модулей двухбитные простые числа . Очевидно, что вычетами по модулям 2 и 3 можно однозначно представить любой вычет по модулю 5. В то же время вычетами по модулям 2, 3 и 5, где вычеты по модулю 5 представимы по модулям 2 и 3, можно однозначно представить любой вычет по модулю 29. Вычетами по модулям 2, 3, 5 и 29 можно однозначно представить любой вычет по модулю 863. И так далее пока не получим нужный набор рабочих оснований: 2, 3, 5, 29, 863,… Данный пример наглядно иллюстрирует 4 факта:

1) Аппаратные и временные затраты на представление чисел по базовым модулям 2 и 3 примерно одинаковы (оба базисных модуля двухбитные);

2) Наблюдается более высокая степень распараллеливаемости;

3) Появляется регулярность (все вычисления проводятся по модулям 2 и 3);

4) Столь малая разрядность базовых модулей позволяет эффективно реализовать модульные операции по базисным модулям в комбинационных схемах.

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

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

Для примера с базовыми модулями 2 и 3 . Наименьшее простое число (после 2 и 3) - это 5, следовательно, . Нельзя выполнить ни операцию сложения, т.к. , ни, тем более, операцию умножения, т.к. . Чтобы выполнять любую из арифметических операций (сложение или умножение) надо увеличить число (т.е. увеличить значения базисных модулей и/или их количество).

Возьмем в качестве базисных модулей все взаимно простые трехбитные числа: 4, 5 и 7. В этом случае .

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

Наконец, рассмотрим реальный случай. Пусть нам нужно реализовать преобразователь Фурье для 24-битных аргументов при количестве точек 1024. Для этого потребуется вычислять сумму 1024 произведений, т.е. обеспечить . Здесь уже не обойтись системой только трехбитных базисных модулей. Добавим к ним четырехбитные: 5, 7, 8, 9, 11 и 13 (Q = 360360). Для выбора ближайшего рабочего модуля необходимо .

Получаем . Выбираем .

Аналогичным расчетом реализуем рекурсивное дерево рабочих оснований целиком.

Чтобы сделать такое устройство, нужно спроектировать блок из 6 вычислителей (для каждого базисного модуля), потребуется 16 таких блоков. Вот где работает регулярность.

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

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

1. Устранение дисбаланса в операциях с малыми и большими модулями
2. Существенно более высокая степень распараллеливаемости
3. Появляется регулярность (большое количество одинаковых базисных модулей)
4. Малая разрядность базисных модулей

Прямое преобразование числа из позиционной системы счисления в представление рекурсивной модулярной арифметики[править | править вики-текст]

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

.

-й элемент содержит элементов, поскольку выражается через элементов системы субмодулей и элементов вектора . Таким образом, продолжая рассуждения, можно заключить, что число элементов для вектора может быть выражено следующей формулой:

Общее же число элементоввектора можно рассчитать, воспользовавшись формулой суммы геометрической прогрессии:


Рассмотрим численный пример. Пусть задана система модулей: . .

Также необходимо убедиться, что , .

Выберем систему базовых модулей . В этом случае , . Число элементов вектора .


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


.


Теперь разложим число по рекурсивному базису:


.


Поскольку все числа в этом векторе не превышают 3, то для хранения вектора потребуется 16*2=32 бит вместо 20 бит для хранения числа в позиционной системе счисления. Степень избыточности составит 1.6. Иллюстрацию к примеру смотрите на рисунке 3.

Рис.3. Разложение числа в системе (2,3,5,29,863) через систему базовых модулей (2,3)

Ограничения на выбор базиса[править | править вики-текст]

Максимальное значение, которое можно представить с помощью , равно . Чтобы была возможность выполнять арифметические операции над числами, требуется, чтобы результат операции для -го элемента был меньше . Для сложения это будет , а для умножения - .

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

Как именно выбирать элементы базиса? Рассмотрим следующий пример.

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

=> => => => => .

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

Обратное преобразование числа из рекурсивного представления в позиционное[править | править вики-текст]

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

Пусть задан некоторый вектор .

Из свойств систем остаточных классов известно, что

,

где

- система ортогональных базисов.

В рекурсивной модулярной арифметике требуется найти набор ортогональных базисов для следующих систем остаточных классов:

.


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

=> ; ; ;
=> ; ; ; ;
=> ; ; ; ; ;

Процесс обратного преобразования приведен на рисунке 4. В позиционной системе счисления искомый вектор равен 13357.

Рис.4. Процесс обратного преобразования вектора

Сложение и умножение в рекурсивной модулярной арифметике[править | править вики-текст]

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

См. также[править | править вики-текст]

Система остаточных классов

Ссылки[править | править вики-текст]

Подход предложен академиком Стемпковским Александром Леонидовичем из ИППМ РАН.

1. А.Л.Стемпковский, В.М. Амербаев, Р.А. Соловьев // Принципы рекурсивных модулярных вычислений. Журнал «Информационные технологии», 2013, номер 2, стр. 22-27
2. A. L. Stempkovsky, V. M. Amerbaev, R. A. Solovyev, T. Y. Isaeva, E. S. Balaka, D.V. Telpukhov // Principles of recursive Residue Number System computation. CEET International conference on Advances in Computing , Electronics and Electrical Technology, Malaysia, Kuala Lumpur
3. Р.А. Соловьев, Д. В. Тельпухов // Методика выбора базисных оснований для рекурсивной модулярной арифметики. Журнал "Вычислительные технологии", Том 19 №4 2014