Перевод числа из СОК в обобщенную позиционную систему
Isaeva (обсуждение | вклад) |
Isaeva (обсуждение | вклад) |
||
(не показаны 16 промежуточных версий 1 участника) | |||
Строка 8: | Строка 8: | ||
:<math>A = a_n\cdot p_1\cdot p_2\cdot \ldots \cdot p_{n-1} + a_{n-1}\cdot p_1\cdot p_2\cdot \ldots \cdot p_{n-2} + \ldots + a_3\cdot p_1\cdot p_2 + a_2\cdot p_1 + a_1</math> | :<math>A = a_n\cdot p_1\cdot p_2\cdot \ldots \cdot p_{n-1} + a_{n-1}\cdot p_1\cdot p_2\cdot \ldots \cdot p_{n-2} + \ldots + a_3\cdot p_1\cdot p_2 + a_2\cdot p_1 + a_1</math> | ||
− | где <math>0\le a_k<p_1\cdot p_2\cdot \ldots \cdot p_{k-1}</math> – коэффициенты (цифры) ОПС. | + | где <math>0\le a_k<p_1\cdot p_2\cdot \ldots \cdot p_{k-1} (k=1, \ldots, n)</math> – коэффициенты (цифры) ОПС. |
Очевидно, что диапазоны чисел, представимых в СОК и ОПС совпадают, т.е. можно говорить о наличии взаимно однозначного соответствия между множеством представлений чисел в СОК и ОПС. | Очевидно, что диапазоны чисел, представимых в СОК и ОПС совпадают, т.е. можно говорить о наличии взаимно однозначного соответствия между множеством представлений чисел в СОК и ОПС. | ||
Строка 23: | Строка 23: | ||
:<math>a_2 = A_1 - \left[ \frac{A_1}{p_2}\right] \cdot p_2 = A_1 - A_2\cdot p_2</math>, где <math>A_2 = \left[ \frac{A_1}{p_2}\right]</math>, | :<math>a_2 = A_1 - \left[ \frac{A_1}{p_2}\right] \cdot p_2 = A_1 - A_2\cdot p_2</math>, где <math>A_2 = \left[ \frac{A_1}{p_2}\right]</math>, | ||
− | <math>\ldots</math> | + | :<math>\ldots</math> |
:<math>a_n = A_{n-1} - \left[ \frac{A_{n-1}}{p_n}\right] \cdot p_n = A_{n-1} - A_n\cdot p_n</math>, где <math>A_n = \left[ \frac{A_{n-1}}{p_n}\right]</math>. | :<math>a_n = A_{n-1} - \left[ \frac{A_{n-1}}{p_n}\right] \cdot p_n = A_{n-1} - A_n\cdot p_n</math>, где <math>A_n = \left[ \frac{A_{n-1}}{p_n}\right]</math>. | ||
Строка 45: | Строка 45: | ||
Перевод, осуществляемый согласно описанному алгоритму,содержит всего <math>2 \cdot (n-1)</math> остаточных арифметических операций вычитания и деления без остатка, где <math>n</math> – число модулей системы. | Перевод, осуществляемый согласно описанному алгоритму,содержит всего <math>2 \cdot (n-1)</math> остаточных арифметических операций вычитания и деления без остатка, где <math>n</math> – число модулей системы. | ||
+ | |||
'''Модификация алгоритма перевода числа из СОК в обобщенную позиционную систему''' | '''Модификация алгоритма перевода числа из СОК в обобщенную позиционную систему''' | ||
Строка 60: | Строка 61: | ||
Если константы <math>\tau_{k,j}</math> вычислены, то вычисление цифр <math>a_i</math> ОПС по модифицированному алгоритму может быть переписано в виде: | Если константы <math>\tau_{k,j}</math> вычислены, то вычисление цифр <math>a_i</math> ОПС по модифицированному алгоритму может быть переписано в виде: | ||
− | <math>a_1 \equiv {\alpha}_1 \pmod p_1</math>, | + | :<math>a_1 \equiv {\alpha}_1 \pmod {p_1}</math>, |
+ | |||
+ | :<math>a_2 \equiv ({\alpha}_2 - a_1) \cdot \tau_{1,2} \pmod {p_2}</math>, | ||
+ | |||
+ | :<math>a_3 \equiv (({\alpha}_3 - a_1) \cdot \tau_{1,3} - a_2) \cdot \tau_{2,3} \pmod {p_3}</math>, | ||
+ | |||
+ | :<math>\ldots</math> | ||
+ | |||
+ | :<math>a_n \equiv (\ldots (({\alpha}_n - a_1) \cdot \tau_{1,n} - a_2) \cdot \tau_{2,n} - \ldots a_{n-1}) \cdot \tau_{n-1,n} \pmod {p_n}</math>. | ||
+ | |||
+ | |||
+ | Константы <math>\tau_{k,j}</math> принято также записывать в виде | ||
+ | |||
+ | <math>\tau_{k,j} = \left | \frac {1}{p_k} \right | \pmod {p_j} </math> | ||
+ | |||
+ | и называть обратными элементами по умножению для чисел <math>p_k</math> по модулю <math>p_j</math> (multiplicative inverse). | ||
+ | |||
+ | |||
+ | '''Пример''' | ||
+ | |||
+ | Пусть дана система оснований <math>p_1 = 2, p_2 = 3, p_3 = 5, p_4 = 7, p_5 = 11</math>. Объем диапазона <math>P = 2310</math>. Переведем число <math>A = (1,2,1,4,7)</math> в ОПС. | ||
+ | |||
+ | Найдем сначала константы <math>\tau_{k,j}</math>: | ||
+ | |||
+ | |||
+ | :<math>\tau_{1,2} = \left | \frac{1}{2} \right | \pmod 3 = 2</math>, <math>\tau_{1,3} = \left | \frac{1}{2} \right | \pmod 5 = 3</math>, | ||
+ | <math>\tau_{1,4} = \left | \frac{1}{2} \right | \pmod 7 = 4</math>, | ||
+ | <math>\tau_{1,5} = \left | \frac{1}{2} \right | \pmod {11} = 6</math>, | ||
+ | |||
+ | |||
+ | :<math>\tau_{2,3} = \left | \frac{1}{3} \right | \pmod 5 = 2</math>, | ||
+ | <math>\tau_{2,4} = \left | \frac{1}{3} \right | \pmod 7 = 5</math>, | ||
+ | <math>\tau_{2,5} = \left | \frac{1}{3} \right | \pmod {11} = 4</math>, | ||
+ | |||
+ | |||
+ | :<math>\tau_{3,4} = \left | \frac{1}{5} \right | \pmod 7 = 3</math>, <math>\tau_{3,5} = \left | \frac{1}{5} \right | \pmod {11} = 9</math>, | ||
+ | |||
+ | |||
+ | :<math>\tau_{4,5} = \left | \frac{1}{7} \right | \pmod {11} = 8</math>. | ||
+ | |||
+ | |||
+ | Для удобства запишем константы в виде матрицы: | ||
+ | |||
+ | |||
+ | <math>\left( \begin{array}{ccccc} 0 & 2 & 3 & 4 & 6 \\ 0 & 0 & 2 & 5 & 4 \\ 0 & 0 & 0 & 3 & 9 \\0 & 0 & 0 & 0 & 8 \end{array} \right)</math> | ||
+ | |||
+ | |||
+ | Выполнение алгоритма представлено в следующей таблице. | ||
+ | |||
+ | Перевод числа из СОК в ОПС. | ||
+ | |||
+ | <math> \begin{array}{|c|c|c|c|c|c|c|} \hline Operation & p_1=2 & p_2=3 & p_3=5 & p_4=7 & p_5=11 & a_i | ||
+ | \\ \hline A & 1 & 2 & 1 & 4 & 7 & a_1 = 1 | ||
+ | \\ - & & & & & & \\ a_1 & 1 & 1 & 1 & 1 & 1 & | ||
+ | \\ \hline A - a_1 & & 1 & 0 & 3 & 6 & | ||
+ | \\ \times & & & & & & | ||
+ | \\ {\tau}_{1,j} & 0 & 2 & 3 & 4 & 6 & | ||
+ | \\ \hline A_1 & & 2 & 0 & 5 & 3 & a_2 = 2 | ||
+ | \\ - & & & & & & \\ a_2 & & 2 & 2 & 2 & 2 & | ||
+ | \\ \hline A_1 - a_2 & & & 3 & 3 & 1 & | ||
+ | \\ \times & & & & & & | ||
+ | \\ {\tau}_{2,j} & & 0 & 2 & 5 & 4 & | ||
+ | \\ \hline A_2 & & & 1 & 1 & 4 & a_3 = 1 | ||
+ | \\ - & & & & & & \\ a_3 & & & 1 & 1 & 1 & | ||
+ | \\ \hline A_2 - a_3 & & & & 0 & 3 & | ||
+ | \\ \times & & & & & & | ||
+ | \\ {\tau}_{3,j} & & & 0 & 3 & 9 & | ||
+ | \\ \hline A_3 & & & & 0 & 5 & a_4 = 0 | ||
+ | \\ - & & & & & & | ||
+ | \\ a_4 & & & & 0 & 0 & | ||
+ | \\ \hline A_3 - a_4 & & & & 0 & 5 & | ||
+ | \\ \times & & & & & & | ||
+ | \\ {\tau}_{4,j} & & & & 0 & 8 & | ||
+ | \\ \hline A_4 & & & & & 7 & a_5 = 7 | ||
+ | \\ \hline \end{array} </math> | ||
+ | |||
+ | |||
+ | таким образом, | ||
+ | |||
+ | <math> A = a_5 \cdot p_1 \cdot p_2 \cdot p_3 \cdot p_4 + a_4 \cdot p_1 \cdot p_2 \cdot p_3 + a_3 \cdot p_1 \cdot p_2 + a_2 \cdot p_1 + a_1 = 7 \cdot 2 \cdot 3 \cdot 5 \cdot 7 + 0 \cdot 2 \cdot 3 \cdot 5 + 1 \cdot 2 \cdot 3 + 2 \cdot 2 + 1 = 1481 </math>. | ||
+ | |||
+ | |||
+ | Преимущество рассмотренного метода перед методом ортогональных базисов состоит в том, что все вычисления выполняются в модулярной арифметике, причем в отдельных каналах, соответствующих модулям <math>p_i</math>, правда, к сожалению, не параллельно. | ||
+ | |||
+ | |||
+ | '''Алгоритм перевода числа для специальных систем оснований''' | ||
+ | |||
+ | Один из вариантов уменьшения числа операций в рассмотренном алгоритме может быть достигнут путём особого выбора системы оснований. Выберем систему оснований СОК следующим образом: | ||
+ | |||
+ | :<math>p_1, p_2 = p_1+1, p_3 = p_1 \cdot p_2+1, p_4 = p_1 \cdot p_2 \cdot p_3+1, \ldots, p_n = p_1 \cdot p_2 \cdot p_3 \cdot \ldots \cdot p_{n-1}+1</math> | ||
+ | |||
+ | Очевидно, что основания такой системы взаимно простые числа. Эта система обладает той особенностью, что <math> p_j \equiv 1 \pmod {p_k} (1 \le k < j \le n) </math> | ||
+ | т.е. из сравнений <math> {\tau}_{j,k} \cdot p_j \equiv 1 \pmod {p_k} </math> получаем, что все константы <math> {\tau}_{j,k} = 1 </math>. При таком выборе системы оснований алгоритм можно видоизменить следующим образом: вычисления начинают со старших модулей, тогда, т.к. константы <math> {\tau}_{j,k} = 1 </math>, то в алгоритме отпадает необходимость умножать на <math> {\tau}_{j,k} </math>, т.е. | ||
+ | |||
+ | :<math>a_1 \equiv {\alpha}_1 \pmod {{p_1}'}</math>, | ||
+ | |||
+ | :<math>a_2 \equiv {\alpha}_2 - a_1 \pmod {{p_2}'}</math>, | ||
+ | |||
+ | :<math>a_3 \equiv {\alpha}_3 - a_1 - a_2 \pmod {{p_3}'}</math>, | ||
+ | |||
+ | :<math>\ldots</math> | ||
+ | |||
+ | :<math>a_n \equiv {\alpha}_n - a_1 - a_2 - \ldots a_{n-1} \pmod {{p_n}'}</math>, | ||
+ | |||
+ | |||
+ | :где <math> {{p_1}'} > {{p_2}'} > {{p_3}'} > \ldots > {{p_n}'} </math>. | ||
+ | |||
+ | |||
+ | '''Пример''' | ||
+ | |||
+ | Выберем систему оснований по указанному принципу: | ||
+ | |||
+ | :<math>p_1 = 2, p_2 = p_1+1 = 2+1 = 3, p_3 = p_1 \cdot p_2+1 = 2 \cdot 3 + 1 = 7, p_4 = p_1 \cdot p_2 \cdot p_3+1 = 2 \cdot 3 \cdot 7 + 1 = 43</math>. | ||
+ | |||
+ | Объем диапазона <math>P = 2 \cdot 3 \cdot 7 \cdot 43 = 1806</math>. | ||
+ | |||
+ | Введем новые обозначения | ||
+ | |||
+ | :<math>{{p_1}'} = p_4 = 43, {{p_2}'} = p_3 = 7, {{p_3}'} = p_2 = 3, {{p_4}'} = p_1 = 2</math>. | ||
+ | |||
+ | Пусть в системе оснований <math>{{p_1}'}, {{p_2}'}, {{p_3}'}, {{p_4}'}</math> задано число <math>A = (27, 0, 1, 1)</math>. Переведём его в ОПС с той же системой оснований. | ||
+ | |||
+ | Метод перевода чисел из СОК в ОПС на основе выбора системы оснований | ||
+ | |||
+ | <math> \begin{array}{|c|c|c|c|c|c|} \hline Operation & {{p_1}'}=43 & {{p_2}'}=7 & {{p_3}'}=3 & {{p_4}'}=2 & a_i | ||
+ | \\ \hline A & 27 & 0 & 1 & 1 & a_1 = 27 | ||
+ | \\ - & & & & & | ||
+ | \\ a_1 & 27 & 6 & 0 & 1 & | ||
+ | \\ \hline A_1 = A - a_1 & - & 1 & 1 & 0 & a_2 = 1 | ||
+ | \\ - & & & & & | ||
+ | \\ a_2 & & 1 & 1 & 1 & | ||
+ | \\ \hline A_2 = A_1 - a_2 & & - & 0 & 1 & a_3 = 0 | ||
+ | \\ - & & & & & | ||
+ | \\ a_3 & & & 0 & 0 & | ||
+ | \\ \hline A_3 = A_2 - a_3 & & & - & 1 & a_4 = 1 | ||
+ | \\ \hline \end{array} </math> | ||
+ | |||
+ | |||
+ | таким образом, | ||
+ | |||
+ | <math> A = a_4 \cdot {{p_1}'} \cdot {{p_2}'} \cdot {{p_3}'} + a_3 \cdot {{p_1}'} \cdot {{p_2}'} + a_2 \cdot {{p_1}'} + a_1 = 1 \cdot 43 \cdot 7 \cdot 3 + 0 \cdot 43 \cdot 7 + 1 \cdot 43 + 27 = 973 </math>. | ||
+ | |||
− | <math> | + | Как видно, при указанном выборе системы оснований число операций уменьшается вдвое, т.к. необходимо для осуществления перевода совершить <math>n-1</math> операцию вычитания, против <math>2 \cdot (n-1)</math> операций в общем случае. Кроме того отпадает необходимость вычислять и хранить константы <math> {\tau}_{j,k} </math>. |
− | + | Похожим свойством обладают системы оснований | |
− | <math>\ldots</math> | + | :<math>p_1, p_2 = p_1-1, p_3 = p_1 \cdot p_2-1, p_4 = p_1 \cdot p_2 \cdot p_3-1, \ldots, p_n = p_1 \cdot p_2 \cdot p_3 \cdot \ldots \cdot p_{n-1}-1</math>, |
− | <math> | + | для которых все константы <math> {\tau}_{j,k} = -1 (1 \le k <j \le n) </math>. |
− | + | Главный недостаток указанных систем - быстрый рост оснований системы, так как <math>p_n = p_1 \cdot p_2 \cdot p_3 \cdot \ldots \cdot p_{n-1} \pm 1</math>. Один из способов достижения компромисса - это выбор системы оснований, для которой лишь часть констант <math> {\tau}_{j,k} = \pm 1 </math>. |
Текущая версия на 11:33, 18 февраля 2015
Рассмотрим метод определения величины числа связанный с переводом числа из системы остаточных классов в обобщенную позиционную систему (ОПС). Для этого выявим связь между представлением некоторого числа в этих двух системах.
Алгоритм перевода числа из СОК в обобщенную позиционную систему
Пусть СОК задается основаниями и - число в этой системе. И пусть являются также основаниями ОПС, тогда число можно представить в виде
где – коэффициенты (цифры) ОПС.
Очевидно, что диапазоны чисел, представимых в СОК и ОПС совпадают, т.е. можно говорить о наличии взаимно однозначного соответствия между множеством представлений чисел в СОК и ОПС.
Предыдущее равенство можно переписать в следующем виде:
- ,
откуда следует, что цифры ОПС могут быть получены из соотношений:
- , где ,
- , где ,
- , где .
Причем при определении цифр по этим формулам все вычисления можно вести в СОК.
Действительно, из формул следует, что , т.е. - первая СОК цифра, или . Для получения сперва представим в остаточном коде. Очевидно, что делится на . Более того, взаимно просто со всеми другими модулями. Следовательно, для нахождения цифры может быть использована процедура деления без остатка:
- .
Таким путем, с помощью вычитаний и делений в остаточной записи все цифры ОПС могут быть получены. При этом замечено, что
- , ,
и, вообще, для
- .
Перевод, осуществляемый согласно описанному алгоритму,содержит всего остаточных арифметических операций вычитания и деления без остатка, где – число модулей системы.
Модификация алгоритма перевода числа из СОК в обобщенную позиционную систему
Можно предложить некоторую модификацию алгоритма с заменой операции деления операцией умножения. Для этого предварительно вычисляется констант , которые удовлетворяют условию
- .
Эти константы можно, например получить из расширенного алгоритма Евклида
- .
Здесь следует заметить тот факт, что константы полностью определяются выбранной системой оснований, поэтому могут быть вычислены заранее и храниться в некоторой таблице.
Если константы вычислены, то вычисление цифр ОПС по модифицированному алгоритму может быть переписано в виде:
- ,
- ,
- ,
- .
Константы принято также записывать в виде
и называть обратными элементами по умножению для чисел по модулю (multiplicative inverse).
Пример
Пусть дана система оснований . Объем диапазона . Переведем число в ОПС.
Найдем сначала константы :
- , ,
, ,
- ,
, ,
- , ,
- .
Для удобства запишем константы в виде матрицы:
Выполнение алгоритма представлено в следующей таблице.
Перевод числа из СОК в ОПС.
таким образом,
.
Преимущество рассмотренного метода перед методом ортогональных базисов состоит в том, что все вычисления выполняются в модулярной арифметике, причем в отдельных каналах, соответствующих модулям , правда, к сожалению, не параллельно.
Алгоритм перевода числа для специальных систем оснований
Один из вариантов уменьшения числа операций в рассмотренном алгоритме может быть достигнут путём особого выбора системы оснований. Выберем систему оснований СОК следующим образом:
Очевидно, что основания такой системы взаимно простые числа. Эта система обладает той особенностью, что т.е. из сравнений получаем, что все константы . При таком выборе системы оснований алгоритм можно видоизменить следующим образом: вычисления начинают со старших модулей, тогда, т.к. константы , то в алгоритме отпадает необходимость умножать на , т.е.
- ,
- ,
- ,
- ,
- где .
Пример
Выберем систему оснований по указанному принципу:
- .
Объем диапазона .
Введем новые обозначения
- .
Пусть в системе оснований задано число . Переведём его в ОПС с той же системой оснований.
Метод перевода чисел из СОК в ОПС на основе выбора системы оснований
таким образом,
.
Как видно, при указанном выборе системы оснований число операций уменьшается вдвое, т.к. необходимо для осуществления перевода совершить операцию вычитания, против операций в общем случае. Кроме того отпадает необходимость вычислять и хранить константы .
Похожим свойством обладают системы оснований
- ,
для которых все константы .
Главный недостаток указанных систем - быстрый рост оснований системы, так как . Один из способов достижения компромисса - это выбор системы оснований, для которой лишь часть констант .