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

Isaeva в 13:35, 28 мая 2014

2014-05-28T13:35:02Z

Isaeva в 08:48, 7 мая 2014

2014-05-07T08:48:19Z

Isaeva в 08:15, 30 апреля 2014

2014-04-30T08:15:15Z

Внесённые изменения

Isaeva в 12:08, 29 апреля 2014

2014-04-29T12:08:21Z

Isaeva в 10:22, 29 апреля 2014

2014-04-29T10:22:30Z

Isaeva в 09:46, 29 апреля 2014

2014-04-29T09:46:24Z

Isaeva в 08:55, 29 апреля 2014

2014-04-29T08:55:32Z

Isaeva в 08:25, 29 апреля 2014

2014-04-29T08:25:43Z

Isaeva в 08:04, 29 апреля 2014

2014-04-29T08:04:43Z

Isaeva в 16:56, 28 апреля 2014

2014-04-28T16:56:03Z

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

@@ Строка 3: / Строка 3: @@
 Система модулей традиционной модулярной арифметики может быть выражена через систему субмодулей меньшей размерности с использованием рекурсии.
 Рекурсивная модулярная арифметика основана на принципе глубокого распараллеливания модульных операций модулярной арифметики с основаниями <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> с вычислительными диапазонами по соответствующим комплексам базисных оснований.
 Принцип согласования гарантирует, во-первых, изоморфизм кольцевых операций по соответствующим им комплексам базисных оснований, и во-вторых, выполнимость обращения каждого шага рекурсии посредством перевода соответствующих модулярных кодов по базисным основаниям в позиционный код (например, на основе китайской теоремы об остатках, или переводом их в полиадический код).
 Несмотря на ограничения, которые накладываются на систему модулей, предложенный метод обеспечивает выигрыш по скорости и может быть применен в параллельных высокоскоростных вычислительных устройствах.
@@ Строка 43: / Строка 46: @@
 Заметим, что все вычислители будут иметь высокую скорость модульных операций (суперраспараллеливание) и небольшие аппаратные затраты в силу малости базисных модулей или их близости к степеням двойки.
 Таким образом, предложенный аппарат рекурсивных модулярных вычислений дает следующие преимущества:
@@ Строка 177: / Строка 181: @@
 Если выполнены ограничения, наложенные на базис, то сложение и умножение чисел выполняются так же, как и в традиционной модулярной арифметике. Чтобы сложить (умножить) два числа, требуется сложить (умножить) соответствующие элементы вектора по модулю <math> p_i </math>. А поскольку все элементы вектора имеют малую разрядность, параллельное сложение (умножение) выполняется очень быстро.

@@ Строка 57: / Строка 57: @@
 В этом случае вектор 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.
 Назовем систему из 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>.
@@ Строка 116: / Строка 121: @@
 Поскольку все числа в этом векторе не превышают 3, то для хранения вектора потребуется 16*2=32 бит вместо 20 бит для хранения числа в позиционной системе счисления. Степень избыточности составит 1.6. Иллюстрацию к примеру смотрите на рисунке 3.
 == Ограничения на выбор базиса ==
@@ Строка 150: / Строка 158: @@
 Процесс обратного преобразования приведен на рисунке 4. В позиционной системе счисления искомый вектор равен 13357.

← Предыдущая		Версия 10:22, 29 апреля 2014
Строка 128:		Строка 128:

	== Обратное преобразование числа из рекурсивного представления в позиционное ==		== Обратное преобразование числа из рекурсивного представления в позиционное ==
		+
		+	Для обратного представления также требуется рекурсивная реализация на базе того же метода, который используется для преобразования из вектора традиционной модулярной арифметики в позиционную систему счисления.
		+	Пусть задан некоторый вектор <math> A = (a_1, a_2, \ldots , a_n) </math>.
		+
		+	Из свойств систем остаточных классов известно, что
		+	: <math> 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}\| </math>,
		+	где
		+	:<math> B_0 = (1, 0, \ldots , 0) , B_1 = (0, 1, \ldots , 0) , \ldots , B_n = (0, 0, \ldots , 1) </math> - система ортогональных базисов.
		+
		+	В рекурсивной модулярной арифметике требуется найти набор ортогональных базисов для следующих систем остаточных классов:
		+	:<math> (p_1, p_2, \ldots , p_m), (p_1, p_2, \ldots , p_{m+1}), \ldots + (p_1, p_2, \ldots , p_n) </math>.
		+
		+
		+	Рассмотрим пример. Пусть задан базис <math> (3, 5, 7, 11, 13) </math> с системой базовых модулей <math> (3, 5, 7) </math>. И пусть требуется преобразовать вектор <math> (1, 2, 1, (0, 3, 3), (0, 1, 6, (0, 1, 6))) </math> в позиционную систему счисления. Для обратного преобразования требуется найти ортогональные базисы для каждой из следующих систем остаточных классов:
		+
		+	:<math> S_1 = (3, 5, 7) </math> => <math> B_{1,1} = (1, 0, 0) \equiv 70 </math>; <math> B_{1,2} = (0, 1, 0) \equiv 21 </math>; <math> B_{1,3} = (0, 0, 1) \equiv 15 </math>;
		+
		+	:<math> S_2 = (3, 5, 7, 11) </math> => <math> B_{2,1} \equiv 385 </math>; <math> B_{2,2} \equiv 231 </math>; <math> B_{2,3} \equiv 330 </math>; <math> B_{2,4} \equiv 210 </math>;
		+
		+	:<math> S_3 = (3, 5, 7, 11, 13) </math> => <math> B_{3,1} \equiv 5005 </math>; <math> B_{3,2} \equiv 6006 </math>; <math> B_{3,3} \equiv 10725 </math>; <math> B_{3,4} \equiv 1365 </math>; <math> B_{3,5} \equiv 6930 </math>;
		+
		+	Процесс обратного преобразования приведен на рисунке 4. В позиционной системе счисления искомый вектор равен 13357.
		+

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

@@ Строка 123: / Строка 123: @@
 Как именно выбирать элементы базиса? Рассмотрим следующий пример. Пусть задана система базовых модулей <math> (4, 5, 7) </math> . Требуется определить <math>p_4 </math> таким образом, чтобы в рамках полученного рекурсивного базиса можно было использовать операцию умножения.
-<math> Q > MAX </math> => <math> Q > max^2 </math> => <math> Q > (p_4 – 1)^2 </math> => <math> p_4 < \sqrt{Q} + 1 </math> => <math>  p_4 < \sqrt{140} + 1 </math> => <math>  p_4 < 12.8 </math>
+<math> Q > MAX </math> => <math> Q > max^2 </math> => <math> Q > (p_{4}-1)^2 </math> => <math> p_4 < \sqrt{Q} + 1 </math> => <math>  p_4 < \sqrt{140} + 1 </math> => <math>  p_4 < 12.8 </math> .
 == Обратное преобразование числа из рекурсивного представления в позиционное ==
 == Сложение и умножение в рекурсивной модулярной арифметике ==

@@ Строка 29: / Строка 29: @@
 Таким образом, выбираем <math> p_{i} = 11 </math> (ближайшее к 7 простое число). Далее совокупность рабочих модулей строится с помощью аналогичного расчета, пока не будет достигнут требуемый вычислительный диапазон.
-Наконец рассмотрим реальный случай. Пусть нам нужно реализовать преобразователь Фурье для 24-битных аргументов при количестве точек 1024.
+Наконец, рассмотрим реальный случай. Пусть нам нужно реализовать преобразователь Фурье для 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> \sqrt \frac{Q}{1024}</math>.
 Получаем <math>p_{i}-1 < 32 </math>.
@@ Строка 118: / Строка 118: @@
 == Ограничения на выбор базиса ==
 == Обратное преобразование числа из рекурсивного представления в позиционное ==
 == Сложение и умножение в рекурсивной модулярной арифметике ==

← Предыдущая		Версия 08:25, 29 апреля 2014
Строка 82:		Строка 82:

	:<math>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 </math>		:<math>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 </math>
		+
		+
		+	Рассмотрим численный пример. Пусть задана система модулей:
		+	<math> (p_1, p_2, p_3, p_4, p_5) = (2,3,5,29,863) </math> .
		+	<math> P = 2 \cdot 3 \cdot 5 \cdot 29 \cdot 863 = 750810 </math> .
		+	Также необходимо убедиться что
		+	<math> 2 \cdot 3 >5, 2 \cdot 3 \cdot 5 >29 </math>, <math> 2 \cdot 3 \cdot 5 \cdot 29 >863 </math> .
		+
		+	Выберем систему базовых модулей <math> (p_1, p_2) </math> .
		+	В этом случае <math> Q = p_1 \cdot p_2 = 6 </math> , <math> n = 5, m = 2 </math> .
		+	Число элементов вектора <math> L = 2^3 \cdot 2 = 16 </math> .
		+
		+
		+	Разложим число <math> A = 865 </math> , заданное в позиционной системе счисления в вектор по обычному базису.
		+
		+
		+	:<math> A = ( \|865\|_2, \|865\|_3, \|865\|_5, \|865\|_29, \|865\|_863 ) = ( 1, 1, 0, 24, 2 )</math> .
		+
		+
		+	Теперь разложим число <math> A </math> по рекурсивному базису:
		+
		+
		+	:<math> A = ( \|865\|_2, \|865\|_3, ( \| \|865\|_5\|_2, \| \|865\|_5\|_3 ), </math>
		+
		+	::<math> ( \| \|865\|_29\|_2, \| \|865\|_29\|_3 , ( \| \| \|865\|_29\|_5\|_2, \| \| \|865\|_29\|_5\|_3 ) ) , </math>
		+
		+	::<math> ( \| \|865\|_863\|_2, \| \|865\|_863\|_3 , ( \| \| \|865\|_863\|_5\|_2, \| \| \|865\|_863\|_5\|_3 ) ) , </math>
		+
		+	::<math> ( \| \| \|865\|_863\|_29\|_2, \| \|865\|_863\|_29\|_3 , </math>
		+
		+	::<math> ( \| \| \| \|865\|_863\|_29\|_5\|_2, \| \| \| \|865\|_863\|_29\|_5\|_3 ) ) ) ) </math> .
		+
		+
		+	Поскольку все числа в этом векторе не превышают 3, то для хранения вектора потребуется 16*2=32 бит вместо 20 бит для хранения числа в позиционной системе счисления. Степень избыточности составит 1.6. Иллюстрацию к примеру смотрите на рисунке 3.

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

@@ Строка 34: / Строка 34: @@
 Получаем <math>p_{i}-1 < 32 </math>.
 Выбираем <math>p_{i} = 31 </math>.
 Аналогичным расчетом реализуем рекурсивное дерево рабочих оснований целиком.
 Чтобы сделать такое устройство, нужно спроектировать блок из 6 вычислителей (для каждого базисного модуля) и таких блоков нужно будет 16. Вот где работает регулярность.
@@ Строка 50: / Строка 51: @@
 Идея, на которой базируется рекурсивная модулярная арифметика: выразить систему модулей через систему субмодулей, имеющую меньшую размерность.
-Пусть задана система модулей <math> (p_1, p_2, \ldots, p_i, \ldots , p_n) </math> и задан некоторый вектор <math> A = (a_1, a_2, \ldots , a_n) </math>. Выразим <math> a_i </math> через систему субмодулей <math> p_i = (p_{i,1}, p_{i,2}, \ldots , p_{i,k}) </math> , где <math> P_i = p_{i,1}, p_{i,2}, \ldots , p_{i,k} </math> и a_i < P_i </math> : <math> a_i = (a_{i,1}, a_{i,2}, \ldots , a_{i,k}) </math> . В этом случае вектор 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> p_1, p_2, \ldots, p_i, \ldots , p_n </math> и задан некоторый вектор <math> A = (a_1, a_2, \ldots , a_n) </math>. Выразим <math> a_i </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 = (p_{i,1}, p_{i,2}, \ldots , p_{i,k}) </math> , где <math> P_i = p_{i,1}, p_{i,2}, \ldots , p_{i,k} </math> и <math> a_i < P_i </math> : <math> a_i = (a_{i,1}, a_{i,2}, \ldots , a_{i,k}) </math> .
@@ Строка 58: / Строка 67: @@
 Если в традиционной модулярной арифметике число элементов вектора равно числу элементов в системе модулей, то в рекурсивной модулярной арифметике количество элементов вектора увеличивается в зависимости от заданных <math>n</math> и <math>m</math> .
-Очевидно, что каждый из первых <math>m</math> элементов представляется в виде одного числа. <math>(m+1)</math>-й элемент содержит <math>m</math> элементов, поскольку выражается через <math>m</math> элементов системы субмодулей: <math> a_{m+1} = (a_{m+1,1}, a_{m+1,2}, \ldots , a_{m+1,m}) </math> . <math>(m+2)</math>-й элемент содержит <math>2 \cdot m</math> элементов, поскольку выражается через <math>m</math> элементов системы субмодулей и <math>m</math> элементов вектора<math> a_{m+1} </math> . Таким образом, продолжая рассуждения, можно заключить, что число элементов <math> L_i </math> для вектора <math> a_i </math> может быть выражено следующей формулой:
+Очевидно, что каждый из первых <math>m</math> элементов представляется в виде одного числа. <math>(m+1)</math>-й элемент содержит <math>m</math> элементов, поскольку выражается через <math>m</math> элементов системы субмодулей:
-<math>L_i = \{ 1, i \le m ; 2^{i-m-1} \cdot m, m<i<n </math>
+:<math>L_i = \begin{cases}
 Общее же число элементов<math> L </math>вектора <math> A </math> можно рассчитать, воспользовавшись формулой суммы геометрической прогрессии:
-<math>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 </math>
+:<math>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 </math>
 == Ограничения на выбор базиса ==

@@ Строка 39: / Строка 39: @@
 Заметим, что все вычислители будут иметь высокую скорость модульных операций (суперраспараллеливание) и небольшие аппаратные затраты в силу малости базисных модулей или их близости к степеням двойки.
 = Представление данных и основные операции рекурсивной модулярной арифметики =
 == Прямое преобразование числа из позиционной системы счисления в представление рекурсивной модулярной арифметики ==
 == Ограничения на выбор базиса ==