Рекурсивная модулярная арифметика — различия между версиями
Isaeva (обсуждение | вклад) |
Isaeva (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | Рекурсивная модулярная арифметика основана на принципе глубокого распараллеливания модульных операций модулярной арифметики с основаниями посредством сведения модульных операций по каждому рабочему основанию к модульным вычислениям по предшествующим рабочим основаниям, имеющим то или иное технологическое преимущество (например, малобитным), которые называются базисными основаниями. Такая редукция допустима только при выполнении так называемого условия согласования вычислительных диапазонов по каждому рабочему модулю с вычислительными диапазонами по соответствующим комплексам базисных оснований. | + | Рекурсивная модулярная арифметика основана на принципе глубокого распараллеливания модульных операций модулярной арифметики с основаниями <math>p_1,p_2,\ldots,p_n</math> посредством сведения модульных операций по каждому рабочему основанию <math>p_j</math>, <math>i<=j<=n</math> к модульным вычислениям по предшествующим рабочим основаниям <math>p_1,p_2,\ldots,p_{i-1}</math>, имеющим то или иное технологическое преимущество (например, малобитным), которые называются базисными основаниями. Такая редукция допустима только при выполнении так называемого условия согласования вычислительных диапазонов по каждому рабочему модулю <math>p_j</math> с вычислительными диапазонами по соответствующим комплексам базисных оснований. |
Принцип согласования гарантирует, во-первых, изоморфизм кольцевых операций по соответствующим им комплексам базисных оснований, и во-вторых, выполнимость обращения каждого шага рекурсии посредством перевода соответствующих модулярных кодов по базисным основаниям в позиционный код (например, на основе китайской теоремы об остатках, или переводом их в полиадический код). | Принцип согласования гарантирует, во-первых, изоморфизм кольцевых операций по соответствующим им комплексам базисных оснований, и во-вторых, выполнимость обращения каждого шага рекурсии посредством перевода соответствующих модулярных кодов по базисным основаниям в позиционный код (например, на основе китайской теоремы об остатках, или переводом их в полиадический код). | ||
Несмотря на ограничения, которые накладываются на систему модулей, предложенный метод обеспечивает выигрыш по скорости и может быть применен в параллельных высокоскоростных вычислительных устройствах. | Несмотря на ограничения, которые накладываются на систему модулей, предложенный метод обеспечивает выигрыш по скорости и может быть применен в параллельных высокоскоростных вычислительных устройствах. | ||
| Строка 6: | Строка 6: | ||
= Принцип рекурсивных модулярных вычислений = | = Принцип рекурсивных модулярных вычислений = | ||
| + | |||
| + | |||
| + | == Пример == | ||
| + | |||
| + | Поясним процедуру рекурсивных преобразований на простом примере. Возьмем в качестве базисных модулей двухбитные простые числа <math>p_1=2, p_2=3</math>. Очевидно, что вычетами по модулям 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) Столь малая разрядность базовых модулей позволяет эффективно реализовать модульные операции по базисным модулям в комбинационных схемах. | ||
| + | |||
= Представление данных и основные операции рекурсивной модулярной арифметики = | = Представление данных и основные операции рекурсивной модулярной арифметики = | ||
Версия 13:58, 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) Столь малая разрядность базовых модулей позволяет эффективно реализовать модульные операции по базисным модулям в комбинационных схемах.
