Перевод числа из СОК в обобщенную позиционную систему
Isaeva (обсуждение | вклад) |
Isaeva (обсуждение | вклад) |
||
Строка 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> можно представить в виде | ||
Строка 42: | Строка 45: | ||
Перевод, осуществляемый согласно описанному алгоритму,содержит всего <math>2 \cdot (n-1)</math> остаточных арифметических операций вычитания и деления без остатка, где <math>n</math> – число модулей системы. | Перевод, осуществляемый согласно описанному алгоритму,содержит всего <math>2 \cdot (n-1)</math> остаточных арифметических операций вычитания и деления без остатка, где <math>n</math> – число модулей системы. | ||
+ | |||
+ | '''Модификация алгоритма перевода числа из СОК в обобщенную позиционную систему''' | ||
+ | |||
+ | Можно предложить некоторую модификацию алгоритма с заменой операции деления операцией умножения. Для этого предварительно вычисляется <math>\frac{n\cdot (n-1)}{2}</math> констант <math>\tau_{k,j}</math>, которые удовлетворяют условию | ||
+ | |||
+ | :<math>\tau_{k,j}\cdot p_k \equiv 1\pmod p_j, 1 \le k < j \le n</math>. | ||
+ | |||
+ | Эти константы можно, например получить из расширенного алгоритма Евклида | ||
+ | |||
+ | :<math>\tau_{k,j}\cdot p_k + \gamma \cdot p_j = HOD (p_k, p_j) = 1</math>. | ||
+ | |||
+ | Здесь следует заметить тот факт, что константы полностью определяются выбранной системой оснований, поэтому могут быть вычислены заранее и храниться в некоторой таблице. | ||
+ | |||
+ | Если константы <math>\tau_{k,j}</math> вычислены, то вычисление цифр <math>a_i</math> ОПС по модифицированному алгоритму может быть переписано в виде: | ||
+ | |||
+ | <math>a_1 \equiv {\alpha}_1 \pmod p_1</math>, | ||
+ | |||
+ | <math>a_2 \equiv ({\alpha}_2 - {\alpha}_1) \cdot \tau_{1,2} \pmod p_2</math>, | ||
+ | |||
+ | <math>a_3 \equiv (({\alpha}_3 - {\alpha}_1) \cdot \tau_{1,3} - {\alpha}_2) \tau_{2,3} \pmod p_3</math>, | ||
+ | |||
+ | <math>\ldots</math> | ||
+ | |||
+ | <math>a_n \equiv (\ldots (({\alpha}_n - {\alpha}_1) \cdot \tau_{1,n} - {\alpha}_2) \tau_{2,n} - \ldots {\alpha}_{n-1} \cdot \tau_{n-1,n} \pmod p_n</math>. | ||
+ | |||
+ | Константы <math>\tau_{k,j}</math> принято также записывать в виде <math>\tau_{k,j} = \left | \right | \pmod </math> и называть обратными элементами по умножению для чисел по модулю (multiplicative inverse). |
Версия 15:29, 15 октября 2014
Рассмотрим метод определения величины числа связанный с переводом числа из системы остаточных классов в обобщенную позиционную систему (ОПС). Для этого выявим связь между представлением некоторого числа в этих двух системах.
Алгоритм перевода числа из СОК в обобщенную позиционную систему
Пусть СОК задается основаниями и - число в этой системе. И пусть являются также основаниями ОПС, тогда число можно представить в виде
где – коэффициенты (цифры) ОПС.
Очевидно, что диапазоны чисел, представимых в СОК и ОПС совпадают, т.е. можно говорить о наличии взаимно однозначного соответствия между множеством представлений чисел в СОК и ОПС.
Предыдущее равенство можно переписать в следующем виде:
- ,
откуда следует, что цифры ОПС могут быть получены из соотношений:
- , где ,
- , где ,
- , где .
Причем при определении цифр по этим формулам все вычисления можно вести в СОК.
Действительно, из формул следует, что , т.е. - первая СОК цифра, или . Для получения сперва представим в остаточном коде. Очевидно, что делится на . Более того, взаимно просто со всеми другими модулями. Следовательно, для нахождения цифры может быть использована процедура деления без остатка:
- .
Таким путем, с помощью вычитаний и делений в остаточной записи все цифры ОПС могут быть получены. При этом замечено, что
- , ,
и, вообще, для
- .
Перевод, осуществляемый согласно описанному алгоритму,содержит всего остаточных арифметических операций вычитания и деления без остатка, где – число модулей системы.
Модификация алгоритма перевода числа из СОК в обобщенную позиционную систему
Можно предложить некоторую модификацию алгоритма с заменой операции деления операцией умножения. Для этого предварительно вычисляется констант , которые удовлетворяют условию
- .
Эти константы можно, например получить из расширенного алгоритма Евклида
- .
Здесь следует заметить тот факт, что константы полностью определяются выбранной системой оснований, поэтому могут быть вычислены заранее и храниться в некоторой таблице.
Если константы вычислены, то вычисление цифр ОПС по модифицированному алгоритму может быть переписано в виде:
,
,
,
.
Константы принято также записывать в виде Невозможно разобрать выражение (синтаксическая ошибка): \tau_{k,j} = \left | \right | \pmod
и называть обратными элементами по умножению для чисел по модулю (multiplicative inverse).