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

Версия 14:13, 15 октября 2014

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

Пусть СОК задается основаниями $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}$ – коэффициенты (цифры) ОПС.

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

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

$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$ – число модулей системы.

@@ Строка 1: / Строка 1: @@
 Рассмотрим метод определения величины числа связанный с переводом числа из системы остаточных классов в обобщенную позиционную систему (ОПС). Для этого выявим связь между представлением некоторого числа в этих двух системах.
-Пусть СОК задается основаниями <math>p_1, p_2, \ldots, p_n</math> и <math>A = {\alpha}_1, {\alpha}_2, \ldots, {\alpha}_n</math> - число в этой системе. И пусть <math>p_1, p_2, \ldots, p_n</math> являются также основаниями ОПС, тогда число <math>A</math> можно представить в виде
+Пусть СОК задается основаниями <math>p_1, p_2, \ldots, p_n</math> и <math>A = ({\alpha}_1, {\alpha}_2, \ldots, {\alpha}_n)</math> - число в этой системе. И пусть <math>p_1, p_2, \ldots, p_n</math> являются также основаниями ОПС, тогда число <math>A</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>
@@ Строка 9: / Строка 9: @@
 Очевидно, что диапазоны чисел, представимых в СОК и ОПС совпадают, т.е. можно говорить о наличии взаимно однозначного соответствия между множеством представлений чисел в СОК и ОПС.
-Это равенство можно переписать в следующем виде:
+Предыдущее равенство можно переписать в следующем виде:
 :<math>A = a_1 + p_1(a_2 + p_2(a_3 + \ldots +p_{n-2}(a_{n-1} + p_{n-1} a_n) \ldots ))</math>,
@@ Строка 27: / Строка 27: @@
 Причем при определении цифр <math>a_i</math> по этим формулам все вычисления можно вести в СОК.
-Действительно, из формул следует, что <math>a_1 = {|A|}_{p_1}</math>, т.е.
+Действительно, из формул следует, что <math>a_1 = {|A|}_{p_1}</math>, т.е. <math>a_1</math> - первая СОК цифра, или <math>a_1 = {\alpha}_1</math>.
+Для получения <math>a_1</math> сперва представим <math>A - a_1</math> в остаточном коде. Очевидно, что <math>A - a_1</math> делится на <math>p_1</math>. Более того, <math>p_1</math> взаимно просто со всеми другими модулями. Следовательно, для нахождения цифры <math>a_2</math> может быть использована процедура деления без остатка:
+:<math>a_2 = \left|\frac{A - a_1}{p_1}\right|_{p_2}</math>.
+Таким путем, с помощью вычитаний и делений в остаточной записи все цифры ОПС могут быть получены. При этом замечено, что
+:<math>a_1 = |A|_{p_1}</math>, <math>a_2 = \left|\left[\frac{A}{p_1}\right]\right|_{p_2}</math>, <math>a_3 = \left|\left[\frac{A}{p_1\cdot p_2}\right]\right|_{p_3}</math>
+и, вообще, для <math> i > 1 </math>
+:<math>a_i = \left|\left[\frac{A}{p_1\cdot p_2 \cdot \ldots \cdot p_{i-1}}\right]\right|_{p_i}</math>.
+Перевод, осуществляемый согласно описанному алгоритму,содержит всего <math>2 \cdot (n-1)</math> остаточных арифметических операций вычитания и деления без остатка, где <math>n</math> – число модулей системы.

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

Версия 14:13, 15 октября 2014

Персональные инструменты

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация