Математические основы системы остаточных классов (стр. 12 из 19)

+ + + + =

= 7 · 2 · 3 ·5 · 7 + 0 · 2 · 3 · 5 + 1 · 2 · 3 + 2 · 2 + 1 = 1481.

Преимущество рассмотренного метода перед методом ортогональных базисов состоит в том, что все вычисления выполняются в модулярной арифметике, причем в отдельных каналах, соответствующих модулям

, правда, к сожалению, не параллельно. Рассмотрим некоторые модификации изложенного метода.

Один из вариантов уменьшения числа операций в рассмотренном алгоритме может быть достигнут путём особого выбора системы оснований. Выберем систему оснований СОК следующим образом:

Очевидно, что основания такой системы взаимно простые числа. Эта система обладает той особенностью, что

, т.е. из сравнений получаем, что все константы = 1. При таком выборе системы оснований алгоритм можно видоизменить следующим образом: вычисления начинают со старших модулей, тогда, т.к. константы = 1, то в алгоритме отпадает необходимость умножать на , т.е.

(3.10´)

где

Пример. Выберем систему оснований по указанному принципу:

Объём диапазона

Введем новые обозначения

Пусть в системе оснований

задано число (27, 0, 1, 1). Переведём его в ОПС с той же системой оснований.

Метод перевода чисел из СОК в ОПС на основе выбора системы оснований

Действия	Модули							Цифры ОПС
–	2727		06		10		11
–	–				11		01
–	–				10
	–		1

Таким образом,

Как видно, при указанном выборе системы оснований число операций уменьшается вдвое, т.к. необходимо для осуществления перевода совершить

операцию вычитания, против операций в общем случае. Кроме того отпадает необходимость вычислять и хранить константы . Похожим свойством обладают системы оснований

,

для которых все константы

. Однако, главный недостаток указанных систем состоит в быстром росте оснований системы, так как . Один из способов достижения компромисса в создавшемся положении это выбор такой системы оснований, для которой лишь часть констант .

Другая модификация алгоритма (3.9´) основывается на факте, что если в процессе перевода появляется определенная комбинация цифр, то оставшиеся цифры числа в ОПС можно сразу определить и процесс перевода может быть завершен. К условиям, которые могут завершить процесс перевода до выполнения последнего шага алгоритма (3.9´) можно отнести следующие:

1. Если при определении цифры

оказалось, что все другие остаточные цифры равны , где – другие основания СОК ( < ), тогда остальные цифры ОПС будут нули.

2. Если при определении цифры

оказалось, что все другие остаточные цифры равны , где – другие основания СОК ( > ), тогда = –1.

Рассмотрим примеры, иллюстрирующие эти случаи.

Пример. Пусть основания системы

= 2, = 3, = 5, = 7, = 11 объем диапазона = 2310.