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

Материал из Модулярная арифметики
Перейти к: навигация, поиск
Строка 57: Строка 57:
 
В этом случае вектор A можно представить в следующем виде:  
 
В этом случае вектор A можно представить в следующем виде:  
  
−
:<math> (a_1, a_2, \ldots , a_{i-1}, (a_{i,1}, a_{i,2}, \ldots , a_{i,k}), a_{i+1}, \ldots , a_n) </math> , см. рис. 1.
+
:<math> (a_1, a_2, \ldots , a_{i-1}, (a_{i,1}, a_{i,2}, \ldots , a_{i,k}), a_{i+1}, \ldots , a_n) </math> , см. рисунок 1.
 +
 
 +
[[изображение:RecModArith_01.png|frame|center|Рис.1. Иерархия в модулярной арифметике]]
 +
 
  
 
Назовем систему из m младших модулей системой базовых модулей, а их произведение обозначим  <math> Q = (p_1 \cdot p_2 \cdot \ldots \cdot  p_m) </math> .  
 
Назовем систему из m младших модулей системой базовых модулей, а их произведение обозначим  <math> Q = (p_1 \cdot p_2 \cdot \ldots \cdot  p_m) </math> .  
  
 
Пусть <math> P_{i,1} = p_i, p_{i,2} = p_2, \ldots , p_{i,i-1} = p_{i-1} </math> , а <math> k = i-1 </math> , тогда при <math> i = m+1, \ldots , n  </math> имеет место рекурсия. <math> a_i = (a_1, a_2, \ldots , a_m, a_{m+1}, \ldots , a_{i-1}) </math> по системе модулей <math> p_1, p_2, \ldots , p_m, p_{m+1}, \ldots , p_{i-1} </math> или, раскрывая рекурсию: <math> a_i = (a_1, a_2, \ldots , a_m, (a_{m+1,1}, a_{m+1,2}, \ldots , a_{m+1,m} ),  \ldots) </math> . На рис.2 приведен частный случай разложения элемента <math> a_i </math> для случая <math> n=6 </math> и <math> m=3 </math>.
 
Пусть <math> P_{i,1} = p_i, p_{i,2} = p_2, \ldots , p_{i,i-1} = p_{i-1} </math> , а <math> k = i-1 </math> , тогда при <math> i = m+1, \ldots , n  </math> имеет место рекурсия. <math> a_i = (a_1, a_2, \ldots , a_m, a_{m+1}, \ldots , a_{i-1}) </math> по системе модулей <math> p_1, p_2, \ldots , p_m, p_{m+1}, \ldots , p_{i-1} </math> или, раскрывая рекурсию: <math> a_i = (a_1, a_2, \ldots , a_m, (a_{m+1,1}, a_{m+1,2}, \ldots , a_{m+1,m} ),  \ldots) </math> . На рис.2 приведен частный случай разложения элемента <math> a_i </math> для случая <math> n=6 </math> и <math> m=3 </math>.
 +
 +
[[изображение:RecModArith_02.png|frame|center|Рис.2. Рекурсивное разложение элемента p6 через систему субмодулей (p1,p2,p3)]]
  
  
Строка 116: Строка 121:
  
 
Поскольку все числа в этом векторе не превышают 3, то для хранения вектора потребуется 16*2=32 бит вместо 20 бит для хранения числа в позиционной системе счисления. Степень избыточности составит 1.6. Иллюстрацию к примеру смотрите на рисунке 3.
 
Поскольку все числа в этом векторе не превышают 3, то для хранения вектора потребуется 16*2=32 бит вместо 20 бит для хранения числа в позиционной системе счисления. Степень избыточности составит 1.6. Иллюстрацию к примеру смотрите на рисунке 3.
 +
 +
[[изображение:RecModArith_03.png|frame|center|Рис.3. Разложение числа в системе (2,3,5,29,863) через систему базовых модулей (2,3)]]
 +
  
 
== Ограничения на выбор базиса ==
 
== Ограничения на выбор базиса ==
Строка 150: Строка 158:
  
 
Процесс обратного преобразования приведен на рисунке 4. В позиционной системе счисления искомый вектор равен 13357.
 
Процесс обратного преобразования приведен на рисунке 4. В позиционной системе счисления искомый вектор равен 13357.
 +
 +
[[изображение:RecModArith_04.png|frame|center|Рис.4. Процесс обратного преобразования вектора]]
  
  

Версия 12:08, 29 апреля 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). Для выбора ближайшего рабочего модуля необходимо \sqrt \frac{Q}{1024}.

Получаем p_{i}-1 < 32 . Выбираем p_{i} = 31 .

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

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

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


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

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

Пусть задана система модулей p_1, p_2, \ldots, p_i, \ldots , p_n и задан некоторый вектор A = (a_1, a_2, \ldots , a_n) . Выразим a_i через систему субмодулей

p_i = (p_{i,1}, p_{i,2}, \ldots , p_{i,k}) , где P_i = p_{i,1}, p_{i,2}, \ldots , p_{i,k} и a_i < P_i  : a_i = (a_{i,1}, a_{i,2}, \ldots , a_{i,k}) .

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

(a_1, a_2, \ldots , a_{i-1}, (a_{i,1}, a_{i,2}, \ldots , a_{i,k}), a_{i+1}, \ldots , a_n) , см. рисунок 1.
Рис.1. Иерархия в модулярной арифметике


Назовем систему из m младших модулей системой базовых модулей, а их произведение обозначим Q = (p_1 \cdot p_2 \cdot \ldots \cdot p_m) .

Пусть P_{i,1} = p_i, p_{i,2} = p_2, \ldots , p_{i,i-1} = p_{i-1} , а k = i-1 , тогда при i = m+1, \ldots , n имеет место рекурсия. a_i = (a_1, a_2, \ldots , a_m, a_{m+1}, \ldots , a_{i-1}) по системе модулей p_1, p_2, \ldots , p_m, p_{m+1}, \ldots , p_{i-1} или, раскрывая рекурсию: a_i = (a_1, a_2, \ldots , a_m, (a_{m+1,1}, a_{m+1,2}, \ldots , a_{m+1,m} ), \ldots) . На рис.2 приведен частный случай разложения элемента a_i для случая n=6 и m=3 .

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


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

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

a_{m+1} = (a_{m+1,1}, a_{m+1,2}, \ldots , a_{m+1,m}) .

(m+2)-й элемент содержит 2 \cdot m элементов, поскольку выражается через m элементов системы субмодулей и m элементов вектора a_{m+1} . Таким образом, продолжая рассуждения, можно заключить, что число элементов L_i для вектора a_i может быть выражено следующей формулой:

L_i = \begin{cases} 1, & \mbox{if } i \le m ; \\ 2^{i-m-1} \cdot m, & \mbox{if } m<i<n \end{cases}

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

L = \sum_{i=1}^{n} L_i = m+m \cdot (2^0+2^1+ \ldots +2^{n-m+1}) = m \cdot (1+ \frac{2^{n-m}-1}{2-1}) = 2^{n-m} \cdot m


Рассмотрим численный пример. Пусть задана система модулей: (p_1, p_2, p_3, p_4, p_5) = (2,3,5,29,863) . P = 2 \cdot 3 \cdot 5 \cdot 29 \cdot 863 = 750810 . Также необходимо убедиться что 2 \cdot 3 >5, 2 \cdot 3 \cdot 5 >29 , 2 \cdot 3 \cdot 5 \cdot 29 >863 .

Выберем систему базовых модулей (p_1, p_2) . В этом случае Q = p_1 \cdot p_2 = 6 , n = 5, m = 2 . Число элементов вектора L = 2^3 \cdot 2 = 16 .


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


A = ( |865|_2, |865|_3, |865|_5, |865|_29, |865|_863 ) = ( 1, 1, 0, 24, 2 ) .


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


A = ( |865|_2, |865|_3, ( | |865|_5|_2, | |865|_5|_3 ),
( | |865|_29|_2, | |865|_29|_3 , ( | | |865|_29|_5|_2, | | |865|_29|_5|_3 ) ) ,
( | |865|_863|_2, | |865|_863|_3 , ( | | |865|_863|_5|_2, | | |865|_863|_5|_3 ) ) ,
( | | |865|_863|_29|_2, | |865|_863|_29|_3 ,
( | | | |865|_863|_29|_5|_2, | | | |865|_863|_29|_5|_3 ) ) ) ) .


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

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


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

Максимальное значение, которое можно представить с помощью P_{m+1} , равно max = p_{m+1} - 1 . Чтобы была возможность выполнять арифметические операции над числами, требуется, чтобы результат операции для p_{m+1} -го элемента был меньше Q = (p_1 \cdot p_2 \cdot \ldots \cdot p_m) .Для сложения это будет 2 \cdot max , а для умножения - max^2 . Рассмотрим следующий пример. Пусть задан базис (2, 3, 5) . Выберем систему базовых модулей (2, 3) . В этом случае Q = 2 \cdot 2 = 6 , max = 4 . Поскольку для сложения потребуется максимально представимое число 8, что больше 6, а для умножения 16, что тоже больше 6, то в таком базисе можно выполнять взаимно-однозначное разложение чисел, но для базовых арифметических операций он не подходит. Для реальных задач требуется увеличение числа Q . Как именно выбирать элементы базиса? Рассмотрим следующий пример. Пусть задана система базовых модулей (4, 5, 7) . Требуется определить p_4 таким образом, чтобы в рамках полученного рекурсивного базиса можно было использовать операцию умножения.

Q > MAX => Q > max^2 => Q > (p_{4}-1)^2 => p_4 < \sqrt{Q} + 1 => p_4 < \sqrt{140} + 1 => p_4 < 12.8 .

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

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

Для обратного представления также требуется рекурсивная реализация на базе того же метода, который используется для преобразования из вектора традиционной модулярной арифметики в позиционную систему счисления. Пусть задан некоторый вектор A = (a_1, a_2, \ldots , a_n) .

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

A = (a_1, a_2, \ldots , a_n) = (a_1, 0, \ldots , 0) + (0, a_2, 0, \ldots , 0) + \ldots + (0, 0, \ldots , a_n) = |\sum_{i=1}^n{a_i \cdot b_i}| ,

где

B_0 = (1, 0, \ldots , 0) , B_1 = (0, 1, \ldots , 0) , \ldots , B_n = (0, 0, \ldots , 1) - система ортогональных базисов.

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

(p_1, p_2, \ldots , p_m), (p_1, p_2, \ldots , p_{m+1}), \ldots + (p_1, p_2, \ldots , p_n) .


Рассмотрим пример. Пусть задан базис (3, 5, 7, 11, 13) с системой базовых модулей (3, 5, 7) . И пусть требуется преобразовать вектор (1, 2, 1, (0, 3, 3), (0, 1, 6, (0, 1, 6))) в позиционную систему счисления. Для обратного преобразования требуется найти ортогональные базисы для каждой из следующих систем остаточных классов:

S_1 = (3, 5, 7) => B_{1,1} = (1, 0, 0) \equiv 70 ; B_{1,2} = (0, 1, 0) \equiv 21 ; B_{1,3} = (0, 0, 1) \equiv 15 ;
S_2 = (3, 5, 7, 11) => B_{2,1} \equiv 385 ; B_{2,2} \equiv 231 ; B_{2,3} \equiv 330 ; B_{2,4} \equiv 210 ;
S_3 = (3, 5, 7, 11, 13) => B_{3,1} \equiv 5005 ; B_{3,2} \equiv 6006 ; B_{3,3} \equiv 10725 ; B_{3,4} \equiv 1365 ; B_{3,5} \equiv 6930 ;

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

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


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

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

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