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

Материал из Модулярная арифметики
Перейти к: навигация, поиск
Строка 26: Строка 26:
  
 
Возьмем в качестве базисных модулей все взаимно простые трехбитные числа: 4, 5 и 7. В этом случае <math>Q=4\cdot 5\cdot 7=140</math>.
 
Возьмем в качестве базисных модулей все взаимно простые трехбитные числа: 4, 5 и 7. В этом случае <math>Q=4\cdot 5\cdot 7=140</math>.
 +
 +
Таким образом, выбираем <math> p_{i} = 11 </math> (ближайшее к 7 простое число). Далее совокупность рабочих модулей строится с помощью аналогичного расчета, пока не будет достигнут требуемый вычислительный диапазон.
 +
 +
Наконец рассмотрим реальный случай. Пусть нам нужно реализовать преобразователь Фурье для 24-битных аргументов при количестве точек 1024.
 +
Для этого потребуется вычислять сумму 1024 произведений, т.е. обеспечить <math> 1024 \cdot max^2 < Q </math>. Здесь уже не обойтись системой только трехбитных базисных модулей. Добавим к ним четырехбитные: 5, 7, 8, 9, 11 и 13 (Q = 360360).
 +
Для выбора ближайшего рабочего модуля необходимо <math>\frac{\sqrt Q}{1024}</math>.
 +
 +
Получаем <math>p_{i}-1 < 32 </math>.
 +
Выбираем <math>p_{i} = 31 </math>.
 +
Аналогичным расчетом реализуем рекурсивное дерево рабочих оснований целиком.
 +
Чтобы сделать такое устройство, нужно спроектировать блок из 6 вычислителей (для каждого базисного модуля) и таких блоков нужно будет 16. Вот где работает регулярность.
 +
Заметим, что все вычислители будут иметь высокую скорость модульных операций (суперраспараллеливание) и небольшие аппаратные затраты в силу малости базисных модулей или их близости к степеням двойки.
 +
  
  

Версия 16:31, 28 апреля 2014

Принцип рекурсивных модулярных вычислений

Рекурсивная модулярная арифметика основана на принципе глубокого распараллеливания модульных операций модулярной арифметики с основаниями p_1,p_2,\ldots,p_n посредством сведения модульных операций по каждому рабочему основанию p_j, i<=j<=n к модульным вычислениям по предшествующим рабочим основаниям p_1,p_2,\ldots,p_{i-1}, имеющим то или иное технологическое преимущество (например, малобитным), которые называются базисными основаниями. Такая редукция допустима только при выполнении так называемого условия согласования вычислительных диапазонов по каждому рабочему модулю p_j с вычислительными диапазонами по соответствующим комплексам базисных оснований. Принцип согласования гарантирует, во-первых, изоморфизм кольцевых операций по соответствующим им комплексам базисных оснований, и во-вторых, выполнимость обращения каждого шага рекурсии посредством перевода соответствующих модулярных кодов по базисным основаниям в позиционный код (например, на основе китайской теоремы об остатках, или переводом их в полиадический код). Несмотря на ограничения, которые накладываются на систему модулей, предложенный метод обеспечивает выигрыш по скорости и может быть применен в параллельных высокоскоростных вычислительных устройствах.

Пример

Поясним процедуру рекурсивных преобразований на простом примере. Возьмем в качестве базисных модулей двухбитные простые числа p_1=2, p_2=3. Очевидно, что вычетами по модулям 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) Столь малая разрядность базовых модулей позволяет эффективно реализовать модульные операции по базисным модулям в комбинационных схемах.

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

Пусть есть система базисных модулей p_1,p_2,\ldots,p_m и необходимо представить вычеты по модулю p_{m+1} через вычеты по этой системе базовых модулей. Очевидно, что максимальный вычет по модулю p_{m+1} равен max=p_{m+1}-1. Зная это значение и последовательность выполняемых операций, можно рассчитать максимальное значение MAX результата арифметической операции. Очевидно, что для однозначного представления результата арифметических операций необходимо, чтобы MAX<Q, где Q=p_1\cdot p_2\cdot \ldots \cdot p_m. Для остальных модулей расчет производится аналогично.

Для примера с базовыми модулями 2 и 3 Q=2\cdot 3 = 6. Наименьшее простое число (после 2 и 3) - это 5, следовательно, max=4. Нельзя выполнить ни операцию сложения, т.к. 2\cdot max > Q (8 > 6) , ни, тем более, операцию умножения, т.к. max^2 > Q (16 > 6). Чтобы выполнять любую из арифметических операций (сложение или умножение) надо увеличить число Q (т.е. увеличить значения базисных модулей и/или их количество).

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

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

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

Получаем p_{i}-1 < 32 . Выбираем p_{i} = 31 . Аналогичным расчетом реализуем рекурсивное дерево рабочих оснований целиком. Чтобы сделать такое устройство, нужно спроектировать блок из 6 вычислителей (для каждого базисного модуля) и таких блоков нужно будет 16. Вот где работает регулярность. Заметим, что все вычислители будут иметь высокую скорость модульных операций (суперраспараллеливание) и небольшие аппаратные затраты в силу малости базисных модулей или их близости к степеням двойки.


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

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

Ограничения на выбор базиса

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

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

Источник — «https://vscripts.ru/w/index.php?title=Рекурсивная_модулярная_арифметика&oldid=827»