Математические основы системы остаточных классов
Рассмотрим примеры, иллюстрирующие эти случаи.
Пример. Пусть
основания
системы
=
2,
=
3,
=
5,
=
7,
=
11 объем диапазона
=
2310.
Переведем
числа
=(1,
2, 3, 2, 1) и
=(1,
0, 2, 4, 8) в ОПС с той
же системой
оснований.
Учтем, что константы
для этой системы
вычислены
ранее, выпишем
их в виде матрицы
:

Для числа
получаем
Метод перевода
числа
в ОПС по условию
получения
комбинации
цифр
Действия |
Модули | Цифры ОПС |
||||
|
|
|
|
|
|
||
|
–
|
1
|
2 1 |
3 1 |
2 1 |
1 1 |
|
|
|
0 |
1 2 |
2 3 |
1 4 |
0 6 |
|
|
–
|
2
|
1 2 |
4 2 |
0 2 |
|
|
|
|
0 |
4 2 |
2 5 |
9 4 |
||
|
|
3 |
3 |
3 |
|
||
Тогда согласно
пункту 1,
=
=
0. Таким образом,
=(1,
2, 3, 2, 1)= = 0 · 2 · 3 ·5 · 7 + 0 · 2 ·
3 · 5 + 3 · 2 · 3 + 2 · 2 + 1 = 23.
Для числа
получаем
Метод перевода
числа
в ОПС по условию
получения
комбинации
цифр
Действия |
Модули | Цифры ОПС |
||||
|
|
|
|
|
|
||
|
–
|
1
|
0 1 |
2 1 |
4 1 |
8 1 |
|
|
|
0 |
2 2 |
1 3 |
3 4 |
7 6 |
|
|
–
|
1
|
3 1 |
5 1 |
9 1 |
|
|
|
|
0 |
2 2 |
4 5 |
8 4 |
||
|
|
4 |
6 |
10 |
|
||
Тогда согласно
пункту 2,
![]()
=
4,
=
6,
=
10.
Таким образом
,
=
(1, 0, 2, 4, 8) = 10 · 2 · 3 ·5 · 7 + 6 · 2
· 3 · 5 + 4 · 2 · 3 + 1 · 2 + 1 = 2307.
При использовании
предложенного
метода число
операций в
процессе перевода
чисел в ОПС
уменьшается.
Причем наибольшая
выгода наблюдается
при небольших
по абсолютной
величине основаниях
системы. Было
подсчитано,
что при использовании
рассмотренных
приемов число
операций в
процессе перевода
числа из СОК
в ОПС, например,
для системы
модулей
=
13,
=
11,
=
7,
=
5,
=
3,
=
2, будет в среднем
6,4, против 10 остаточных
операций при
применении
стандартного
метода. Однако,
для проверки
условий, позволяющих
завершить
процесс перевода.
Потребуется
наличие дополнительных
логических
устройств.
Еще можно
отметить, что
специальный
выбор оснований
СОК может позволить
вычисление
констант
.
Так, при кодировании
остатков в
двоичной системе
бывает удобно
выбирать модули
СОК в виде
=
.
(3.11ґ)
Тогда для
определения
констант
существует
достаточно
простая формула
=
1+
+…+
,
(3.12ґ)
где целые
числа
и
подбираются
из условий
![]()
,
![]()
.
(3.13ґ)
3). Достаточно эффективными методами перевода чисел из СОК в ПСС являются интервальные методы, основанные на интервальных характеристиках чисел. Одна из таких характеристик – номер интервала.
Рассмотрим
СОК, заданную
системой оснований
,
с объёмом диапазона
.
Выберем дробящий
модуль
и проведём
дробление
заданного
диапазона на
интервалы путём
деления
на модуль
.
Тогда количество
интервалов
,
а длина интервала
определяется
величиной
модуля. В результате
величину любого
числа
,
заданного в
СОК по выбранным
основаниям
можно определить
по номеру интервала:
,
(3.14ґ)
в котором
находится число
и по цифре
числа
![]()
в
СОК по модулю
,
т.е.
.
(3.15ґ)
Так как (
,
)
= 1, то по теореме
Эйлера:
,
(3.16ґ)
где
– функция Эйлера.
Причём если
– простое число,
то
=
–1.
Подставляя
(3.15ґ) в
(3.4ґ), учитывая
(3.1ґ) и
(3.4ґ) число
можно записать
в виде
.
(3.17ґ)
Для определения
номера интервала
подставим
(3.17ґ) в
(3.14ґ):
.
(3.18ґ)
Учитывая,
что
перепишем
(3.18ґ) в виде
.
(3.19ґ)
Так как
является делителем
чисел
то

![]()
где
и
–
постоянные коэффициенты, определённые системой оснований.
Таким образом,
.
(3.20ґ)
Подставляя
(3.20ґ) в
(3.15ґ), получим
позиционное
представление
числа
![]()
.
(3.21ґ)
В
качестве дробирующего
модуля целесообразнее
выбирать наибольший
из модулей
системы. В этом
случае модульные
операции выполняются
при меньшей
величине модуля,
что ведёт к
меньшим временным
и аппаратурным
затратам.
Целесообразно
также для упрощения
вычислений
и минимизации
времени выполнения
операций выбирать
в качестве
дробирующего
модуля
наибольшие
модули системы,
представляющие
числа Мерсенна
или Ферма
.
При этом предпочтение
отдаётся числам
Мерсенна, так
как арифметика
по этим модулям
проще.
Проиллюстрируем рассмотренный метод на примере.
Пример. Пусть
дана система
оснований
тогда
= 210.
Пусть надо
перевести число
=(0,1,4,3).
В качестве
дробирующего
модуля выберем
тогда
,
номер интервала
,
а само число
.
Определим
Так как
то

Тогда
![]()
Таким образом,
13·7
+ 3 = 94.
На основе
этой же характеристики
числа – номера
интервала, с
применением
теоремы Эйлера
предлагается
алгоритм перевода
числа в ПСС.
Разность между
модулями можно
представить
в виде
=
–
и тогда
,
(3.22ґ)
но с другой стороны
![]()
(![]()
).
(3.23ґ)
Из (3.22ґ)
и (3.23ґ)
следует, что
Так как
![]()
.
(3.24ґ)
Решение сравнения (3.24ґ) можно записать в виде
(3.25ґ)
где
– функция Эйлера.
Если
– простое число,
то
Поэтому в случае
простого
выражение
(2.3.13) примет вид:
![]()
Перепишем (3.15ґ) с учётом (3.25ґ)
(3.26ґ)
где
– константа,
определяемая
выбором оснований
СОК. Нетрудно
заметить, что
– наименьший
неотрицательный
вычет по составному
модулю
·
.
Исходя из этого
можно записать:
(3.27ґ)
где
показывает,
сколько раз
произведение
·
укладывается
в числе
.
Для нахождения
можно считать,
что число
представлено
в системе оснований
в виде
и после этого
можно воспользоваться
формулой (3.27ґ).
Проводя аналогичные
рассуждения,
после преобразований
получим:
(3.28ґ)
Где

(3.29ґ)
Тогда искомая
величина числа
(
– наименьший
неотрицательный
вычет числа
по составному
модулю
)
определяется
за
– 1
шагов, где
– число оснований
СОК.
Пример. Пусть
основания СОК
=
3,
=
5,
=
7,
=
11, объём диапазона
= 1155.
Найдём величину
числа
= (1,2,0,8).


