Перевод числа из СОК в обобщенную позиционную систему

Рассмотрим метод определения величины числа связанный с переводом числа из системы остаточных классов в обобщенную позиционную систему (ОПС). Для этого выявим связь между представлением некоторого числа в этих двух системах.

Алгоритм перевода числа из СОК в обобщенную позиционную систему

Пусть СОК задается основаниями $p_1, p_2, \ldots, p_n$ и $A = ({\alpha}_1, {\alpha}_2, \ldots, {\alpha}_n)$ - число в этой системе. И пусть $p_1, p_2, \ldots, p_n$ являются также основаниями ОПС, тогда число $A$ можно представить в виде

$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$

где $0\le a_k<p_1\cdot p_2\cdot \ldots \cdot p_{k-1} (k=1, \ldots, n)$ – коэффициенты (цифры) ОПС.

Очевидно, что диапазоны чисел, представимых в СОК и ОПС совпадают, т.е. можно говорить о наличии взаимно однозначного соответствия между множеством представлений чисел в СОК и ОПС.

Предыдущее равенство можно переписать в следующем виде:

$A = a_1 + p_1(a_2 + p_2(a_3 + \ldots +p_{n-2}(a_{n-1} + p_{n-1} a_n) \ldots ))$,

откуда следует, что цифры ОПС могут быть получены из соотношений:

$a_1 = A - \left[ \frac{A}{p_1}\right] \cdot p_1 = A - A_1\cdot p_1$, где $A_1 = \left[ \frac{A}{p_1}\right]$,

$a_2 = A_1 - \left[ \frac{A_1}{p_2}\right] \cdot p_2 = A_1 - A_2\cdot p_2$, где $A_2 = \left[ \frac{A_1}{p_2}\right]$,

$\ldots$

$a_n = A_{n-1} - \left[ \frac{A_{n-1}}{p_n}\right] \cdot p_n = A_{n-1} - A_n\cdot p_n$, где $A_n = \left[ \frac{A_{n-1}}{p_n}\right]$.

Причем при определении цифр $a_i$ по этим формулам все вычисления можно вести в СОК.

Действительно, из формул следует, что $a_1 = {|A|}_{p_1}$, т.е. $a_1$ - первая СОК цифра, или $a_1 = {\alpha}_1$. Для получения $a_1$ сперва представим $A - a_1$ в остаточном коде. Очевидно, что $A - a_1$ делится на $p_1$. Более того, $p_1$ взаимно просто со всеми другими модулями. Следовательно, для нахождения цифры $a_2$ может быть использована процедура деления без остатка:

$a_2 = \left|\frac{A - a_1}{p_1}\right|_{p_2}$.

Таким путем, с помощью вычитаний и делений в остаточной записи все цифры ОПС могут быть получены. При этом замечено, что

$a_1 = |A|_{p_1}$, $a_2 = \left|\left[\frac{A}{p_1}\right]\right|_{p_2}$, $a_3 = \left|\left[\frac{A}{p_1\cdot p_2}\right]\right|_{p_3}$

и, вообще, для $i > 1$

$a_i = \left|\left[\frac{A}{p_1\cdot p_2 \cdot \ldots \cdot p_{i-1}}\right]\right|_{p_i}$.

Перевод, осуществляемый согласно описанному алгоритму,содержит всего $2 \cdot (n-1)$ остаточных арифметических операций вычитания и деления без остатка, где $n$ – число модулей системы.

Модификация алгоритма перевода числа из СОК в обобщенную позиционную систему

Можно предложить некоторую модификацию алгоритма с заменой операции деления операцией умножения. Для этого предварительно вычисляется $\frac{n\cdot (n-1)}{2}$ констант $\tau_{k,j}$, которые удовлетворяют условию

$\tau_{k,j}\cdot p_k \equiv 1\pmod p_j, 1 \le k < j \le n$.

Эти константы можно, например получить из расширенного алгоритма Евклида

$\tau_{k,j}\cdot p_k + \gamma \cdot p_j = HOD (p_k, p_j) = 1$.

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

Если константы $\tau_{k,j}$ вычислены, то вычисление цифр $a_i$ ОПС по модифицированному алгоритму может быть переписано в виде:

$a_1 \equiv {\alpha}_1 \pmod {p_1}$,

$a_2 \equiv ({\alpha}_2 - a_1) \cdot \tau_{1,2} \pmod {p_2}$,

$a_3 \equiv (({\alpha}_3 - a_1) \cdot \tau_{1,3} - a_2) \cdot \tau_{2,3} \pmod {p_3}$,

$\ldots$

$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}$.

Константы $\tau_{k,j}$ принято также записывать в виде

$\tau_{k,j} = \left | \frac {1}{p_k} \right | \pmod {p_j}$

и называть обратными элементами по умножению для чисел $p_k$ по модулю $p_j$ (multiplicative inverse).

Пример

Пусть дана система оснований $p_1 = 2, p_2 = 3, p_3 = 5, p_4 = 7, p_5 = 11$. Объем диапазона $P = 2310$. Переведем число $A = (1,2,1,4,7)$ в ОПС.

Найдем сначала константы $\tau_{k,j}$:

$\tau_{1,2} = \left | \frac{1}{2} \right | \pmod 3 = 2$, $\tau_{1,3} = \left | \frac{1}{2} \right | \pmod 5 = 3$,

$\tau_{1,4} = \left | \frac{1}{2} \right | \pmod 7 = 4$, $\tau_{1,5} = \left | \frac{1}{2} \right | \pmod {11} = 6$,

$\tau_{2,3} = \left | \frac{1}{3} \right | \pmod 5 = 2$,

$\tau_{2,4} = \left | \frac{1}{3} \right | \pmod 7 = 5$, $\tau_{2,5} = \left | \frac{1}{3} \right | \pmod {11} = 4$,

$\tau_{3,4} = \left | \frac{1}{5} \right | \pmod 7 = 3$, $\tau_{3,5} = \left | \frac{1}{5} \right | \pmod {11} = 9$,

$\tau_{4,5} = \left | \frac{1}{7} \right | \pmod {11} = 8$.

Для удобства запишем константы в виде матрицы:

$\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)$

Выполнение алгоритма представлено в следующей таблице.

Перевод числа из СОК в ОПС.

$\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}$

таким образом,

$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$.

Преимущество рассмотренного метода перед методом ортогональных базисов состоит в том, что все вычисления выполняются в модулярной арифметике, причем в отдельных каналах, соответствующих модулям $p_i$, правда, к сожалению, не параллельно.

Алгоритм перевода числа для специальных систем оснований

Один из вариантов уменьшения числа операций в рассмотренном алгоритме может быть достигнут путём особого выбора системы оснований. Выберем систему оснований СОК следующим образом:

$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$

Очевидно, что основания такой системы взаимно простые числа. Эта система обладает той особенностью, что $p_j \equiv 1 \pmod {p_k} (1 \le k < j \le n)$ т.е. из сравнений ${\tau}_{j,k} \cdot p_j \equiv 1 \pmod {p_k}$ получаем, что все константы ${\tau}_{j,k} = 1$. При таком выборе системы оснований алгоритм можно видоизменить следующим образом: вычисления начинают со старших модулей, тогда, т.к. константы ${\tau}_{j,k} = 1$, то в алгоритме отпадает необходимость умножать на ${\tau}_{j,k}$, т.е.

$a_1 \equiv {\alpha}_1 \pmod {{p_1}'}$,

$a_2 \equiv {\alpha}_2 - a_1 \pmod {{p_2}'}$,

$a_3 \equiv {\alpha}_3 - a_1 - a_2 \pmod {{p_3}'}$,

$\ldots$

$a_n \equiv {\alpha}_n - a_1 - a_2 - \ldots a_{n-1} \pmod {{p_n}'}$,

где ${{p_1}'} > {{p_2}'} > {{p_3}'} > \ldots > {{p_n}'}$.

Пример

Выберем систему оснований по указанному принципу:

$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$.

Объем диапазона $P = 2 \cdot 3 \cdot 7 \cdot 43 = 1806$.

Введем новые обозначения

${{p_1}'} = p_4 = 43, {{p_2}'} = p_3 = 7, {{p_3}'} = p_2 = 3, {{p_4}'} = p_1 = 2$.

Пусть в системе оснований ${{p_1}'}, {{p_2}'}, {{p_3}'}, {{p_4}'}$ задано число $A = (27, 0, 1, 1)$. Переведём его в ОПС с той же системой оснований.

Метод перевода чисел из СОК в ОПС на основе выбора системы оснований

$\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}$

таким образом,

$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$.

Как видно, при указанном выборе системы оснований число операций уменьшается вдвое, т.к. необходимо для осуществления перевода совершить $n-1$ операцию вычитания, против $2 \cdot (n-1)$ операций в общем случае. Кроме того отпадает необходимость вычислять и хранить константы ${\tau}_{j,k}$.

Похожим свойством обладают системы оснований

$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$,

для которых все константы ${\tau}_{j,k} = -1 (1 \le k <j \le n)$.

Главный недостаток указанных систем - быстрый рост оснований системы, так как $p_n = p_1 \cdot p_2 \cdot p_3 \cdot \ldots \cdot p_{n-1} \pm 1$. Один из способов достижения компромисса - это выбор системы оснований, для которой лишь часть констант ${\tau}_{j,k} = \pm 1$.