Математические основы системы остаточных классов
откуда следует, что цифры ОПС могут быть получены из соотношений:
=
–![]()
=
–![]()
,
где
=
,
=
–
=
–![]()
,
где
=
,
(3.6ґ)
…
=
–

=
–![]()
,
где
=
.
Причем при
определении
цифр
по формулам
(3.6ґ) все
вычисления
можно вести
в СОК.
Действительно,
из (3.6ґ)
следует, что
=
,
т.е.
– первая СОК
цифра или
=
.
Для получения
,
сперва
–
представим
в остаточном
коде. Очевидно
–
делится на
.
Более того,
взаимно просто
со всеми другими
модулями.
Следовательно,
для нахождения
цифры
может быть
использована
процедура
деления без
остатка:
=
.
Таким путем,
с помощью вычитаний
и делений в
остаточной
записи все
цифры ОПС могут
быть получены.
При этом замечено,
что
=
,
=
,
=
и, вообще, для
> 1
=
.
Перевод,
осуществляемый
согласно алгоритму
(3.6ґ),содержит
всего 2(
–1)
остаточные
арифметические
операции вычитания
и деления без
остатка, где
– число модулей
системы. Можно
предложить
некоторую
модификацию,
т. е. операция
деления заменить
операцией
умножения. Для
этого предварительно
вычисляется
констант
,
которые удовлетворяют
условию
![]()
1(
),
1 ≤
<
≤
.
(3.7ґ)
Эти константы можно, например получить из расширенного алгоритма Евклида
![]()
=
1 (3.8ґ)
Здесь следует
заметить тот
факт, что константы
полностью
определяются
выбранной
системой оснований,
поэтому могут
быть вычислены
заранее и храниться
в некоторой
таблице. В приложении
к [90] для модулей
и
не превосходящих
31 представлена
таблица величин
.
Если константы
вычислены, то
вычисление
цифр
ОПС по алгоритму
(3.6ґ) может
быть переписано
в виде:
,
,
(3.9ґ)
,
.
Константы
принято также
записывать
в виде
=
и называть
обратными
элементами
по умножению
для чисел
по модулю
(multiplicative
inverse).
Рассмотрим алгоритм (3.9ґ) на примере.
Пример. Пусть
дана система
оснований
=
2,
=
3,
=
5,
=
7,
=
11. Объем диапазона
=
2310. переведем
число
=(1,
1, 3, 5, 4) в ОПС.
Найдем сначала
константы
:
=
=2,
=
=3,
=
=4,
=
=6,
=
=2,
=
=5,
=
=4,
=
=3,
=
=9,
=
=8.
Для удобства
константы
запишем в виде
матрицы
:

Выполнение алгоритма (3.9ґ) представлено в таблице
Перевод числа из СОК в ОПС
Действия |
Модули | Цифры ОПС |
||||
|
|
|
|
|
|
||
|
–
|
1
|
2 1 |
1 1 |
4 1 |
7 1 |
|
|
|
0 |
1 2 |
0 3 |
3 4 |
6 6 |
|
|
–
|
– |
2 2 |
0 2 |
5 2 |
3 2 |
|
|
|
0 |
3 2 |
3 5 |
1 4 |
||
|
–
|
– |
1
|
1 1 |
4 1 |
|
|
|
|
0 |
0 3 |
3 9 |
|||
|
–
|
0
|
5 0 |
|
|||
|
|
0 |
5 8 |
||||
|
7 – |
|
||||
Таким образом,
+
+
+
+
=
= 7 · 2 · 3 ·5 · 7 + 0 · 2 · 3 · 5 + 1 · 2 · 3 + 2 · 2 + 1 = 1481.
Преимущество
рассмотренного
метода перед
методом ортогональных
базисов состоит
в том, что все
вычисления
выполняются
в модулярной
арифметике,
причем в отдельных
каналах, соответствующих
модулям
,
правда, к сожалению,
не параллельно.
Рассмотрим
некоторые
модификации
изложенного
метода.
Один из вариантов уменьшения числа операций в рассмотренном алгоритме может быть достигнут путём особого выбора системы оснований. Выберем систему оснований СОК следующим образом:

Очевидно,
что основания
такой системы
взаимно простые
числа. Эта система
обладает той
особенностью,
что
,
т.е. из сравнений
получаем, что
все константы
![]()
= 1.
При таком выборе
системы оснований
алгоритм можно
видоизменить
следующим
образом: вычисления
начинают со
старших модулей,
тогда, т.к. константы
= 1,
то в алгоритме
отпадает
необходимость
умножать на
,
т.е.
(3.10ґ)
где
![]()
Пример. Выберем систему оснований по указанному принципу:
![]()
![]()
Объём диапазона
Введем новые обозначения
Пусть в системе
оснований
задано число
(27,
0, 1, 1). Переведём
его в ОПС с той
же системой
оснований.
Метод перевода чисел из СОК в ОПС на основе выбора системы оснований
| Действия | Модули | Цифры ОПС | |||
|
|
|
|
|
||
|
–
|
27 27 |
0 6 |
1 0 |
1 1 |
|
|
–
|
– |
|
1 1 |
0 1 |
|
|
–
|
– |
|
1 0 |
|
|
|
|
– | 1 |
|
Таким образом,

Как видно,
при указанном
выборе системы
оснований число
операций уменьшается
вдвое, т.к. необходимо
для осуществления
перевода совершить
операцию вычитания,
против
операций в
общем случае.
Кроме того
отпадает
необходимость
вычислять и
хранить константы
.
Похожим свойством
обладают системы
оснований
,
для которых
все константы
.
Однако, главный
недостаток
указанных
систем состоит
в быстром росте
оснований
системы, так
как
.
Один из способов
достижения
компромисса
в создавшемся
положении это
выбор такой
системы оснований,
для которой
лишь часть
констант
.
Другая модификация алгоритма (3.9ґ) основывается на факте, что если в процессе перевода появляется определенная комбинация цифр, то оставшиеся цифры числа в ОПС можно сразу определить и процесс перевода может быть завершен. К условиям, которые могут завершить процесс перевода до выполнения последнего шага алгоритма (3.9ґ) можно отнести следующие:
Если при определении цифры
оказалось, что
все другие
остаточные
цифры равны
,
где
– другие основания
СОК (
<
),
тогда остальные
цифры ОПС будут
нули.Если при определении цифры
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.


