Перевод числа из СОК в обобщенную позиционную систему
Isaeva (обсуждение | вклад) |
Isaeva (обсуждение | вклад) |
||
Строка 110: | Строка 110: | ||
Перевод числа из СОК в ОПС. | Перевод числа из СОК в ОПС. | ||
− | <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>. |
Версия 11:27, 30 октября 2014
Рассмотрим метод определения величины числа связанный с переводом числа из системы остаточных классов в обобщенную позиционную систему (ОПС). Для этого выявим связь между представлением некоторого числа в этих двух системах.
Алгоритм перевода числа из СОК в обобщенную позиционную систему
Пусть СОК задается основаниями и - число в этой системе. И пусть являются также основаниями ОПС, тогда число можно представить в виде
где – коэффициенты (цифры) ОПС.
Очевидно, что диапазоны чисел, представимых в СОК и ОПС совпадают, т.е. можно говорить о наличии взаимно однозначного соответствия между множеством представлений чисел в СОК и ОПС.
Предыдущее равенство можно переписать в следующем виде:
- ,
откуда следует, что цифры ОПС могут быть получены из соотношений:
- , где ,
- , где ,
- , где .
Причем при определении цифр по этим формулам все вычисления можно вести в СОК.
Действительно, из формул следует, что , т.е. - первая СОК цифра, или . Для получения сперва представим в остаточном коде. Очевидно, что делится на . Более того, взаимно просто со всеми другими модулями. Следовательно, для нахождения цифры может быть использована процедура деления без остатка:
- .
Таким путем, с помощью вычитаний и делений в остаточной записи все цифры ОПС могут быть получены. При этом замечено, что
- , ,
и, вообще, для
- .
Перевод, осуществляемый согласно описанному алгоритму,содержит всего остаточных арифметических операций вычитания и деления без остатка, где – число модулей системы.
Модификация алгоритма перевода числа из СОК в обобщенную позиционную систему
Можно предложить некоторую модификацию алгоритма с заменой операции деления операцией умножения. Для этого предварительно вычисляется констант , которые удовлетворяют условию
- .
Эти константы можно, например получить из расширенного алгоритма Евклида
- .
Здесь следует заметить тот факт, что константы полностью определяются выбранной системой оснований, поэтому могут быть вычислены заранее и храниться в некоторой таблице.
Если константы вычислены, то вычисление цифр ОПС по модифицированному алгоритму может быть переписано в виде:
- ,
- ,
- ,
- .
Константы принято также записывать в виде
и называть обратными элементами по умножению для чисел по модулю (multiplicative inverse).
Пример
Пусть дана система оснований . Объем диапазона . Переведем число в ОПС.
Найдем сначала константы :
- , ,
, ,
- ,
, ,
- , ,
- .
Для удобства запишем константы в виде матрицы:
Выполнение алгоритма представлено в следующей таблице.
Перевод числа из СОК в ОПС.
таким образом,
.