Рекурсивная модулярная арифметика — различия между версиями
Isaeva (обсуждение | вклад) |
Isaeva (обсуждение | вклад) |
||
| Строка 20: | Строка 20: | ||
Пусть есть система базисных модулей <math>p_1,p_2,\ldots,p_m</math> и необходимо представить вычеты по модулю <math>p_{m+1}</math> через вычеты по этой системе базовых модулей. Очевидно, что максимальный вычет по модулю <math>p_{m+1}</math> равен <math>max=p_{m+1}-1</math>. Зная это значение и последовательность выполняемых операций, можно рассчитать максимальное значение <math>MAX</math> результата арифметической операции. Очевидно, что для однозначного представления результата арифметических операций необходимо, чтобы <math>MAX<Q</math>, где <math>Q=p_1\cdot p_2\cdot \ldots \cdot p_m</math>. Для остальных модулей расчет производится аналогично. | Пусть есть система базисных модулей <math>p_1,p_2,\ldots,p_m</math> и необходимо представить вычеты по модулю <math>p_{m+1}</math> через вычеты по этой системе базовых модулей. Очевидно, что максимальный вычет по модулю <math>p_{m+1}</math> равен <math>max=p_{m+1}-1</math>. Зная это значение и последовательность выполняемых операций, можно рассчитать максимальное значение <math>MAX</math> результата арифметической операции. Очевидно, что для однозначного представления результата арифметических операций необходимо, чтобы <math>MAX<Q</math>, где <math>Q=p_1\cdot p_2\cdot \ldots \cdot p_m</math>. Для остальных модулей расчет производится аналогично. | ||
| + | |||
| + | Для примера с базовыми модулями 2 и 3 <math>Q=2\cdot 3 = 6</math>. Наименьшее простое число (после 2 и 3) - это 5, следовательно, <math>max=4</math>. | ||
| + | Нельзя выполнить ни операцию сложения, т.к. <math>2\cdot max > Q</math> <math>(8 > 6)</math> , ни, тем более, операцию умножения, т.к. <math>max^2 > Q</math> <math>(16 > 6)</math>. | ||
| + | Чтобы выполнять любую из арифметических операций (сложение или умножение) надо увеличить число <math>Q</math> (т.е. увеличить значения базисных модулей и/или их количество). | ||
= Представление данных и основные операции рекурсивной модулярной арифметики = | = Представление данных и основные операции рекурсивной модулярной арифметики = | ||
Версия 14:18, 23 апреля 2014
Содержание
Принцип рекурсивных модулярных вычислений
Рекурсивная модулярная арифметика основана на принципе глубокого распараллеливания модульных операций модулярной арифметики с основаниями 
посредством сведения модульных операций по каждому рабочему основанию 
, 
к модульным вычислениям по предшествующим рабочим основаниям 
, имеющим то или иное технологическое преимущество (например, малобитным), которые называются базисными основаниями. Такая редукция допустима только при выполнении так называемого условия согласования вычислительных диапазонов по каждому рабочему модулю с вычислительными диапазонами по соответствующим комплексам базисных оснований.
Принцип согласования гарантирует, во-первых, изоморфизм кольцевых операций по соответствующим им комплексам базисных оснований, и во-вторых, выполнимость обращения каждого шага рекурсии посредством перевода соответствующих модулярных кодов по базисным основаниям в позиционный код (например, на основе китайской теоремы об остатках, или переводом их в полиадический код).
Несмотря на ограничения, которые накладываются на систему модулей, предложенный метод обеспечивает выигрыш по скорости и может быть применен в параллельных высокоскоростных вычислительных устройствах.
Пример
Поясним процедуру рекурсивных преобразований на простом примере. Возьмем в качестве базисных модулей двухбитные простые числа 
. Очевидно, что вычетами по модулям 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, следовательно, 
.
Нельзя выполнить ни операцию сложения, т.к. 
, ни, тем более, операцию умножения, т.к. 
.
Чтобы выполнять любую из арифметических операций (сложение или умножение) надо увеличить число 
(т.е. увеличить значения базисных модулей и/или их количество).
