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

Пример. Пусть основания СОК

= 3, = 5, = 7, = 11, объём диапазона = 1155. Найдём величину числа = (1,2,0,8).

§ 4. Расширение диапазона представления чисел

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

Задачу расширения системы оснований можно сформулировать следующим образом: найти остаточное представление числа по новому основанию (новым основаниям), если известно представление числа по другим основаниям остатки от деления на другие числа.

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

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

с диапазоном Р, ортогональными базисами , веса которых . По определению, . Пусть в этой системе задано число . Расширим систему оснований, добавляя основание , тогда диапазон системы станет , ортогональные базисы системы , их веса , причём . Задача состоит в определении цифры числа по основанию называют цифру , при которой число находится в интервале , и что число , то определение цифры по основанию сводится к определению минимального следа числа А в расширенной системе оснований.

Чтобы получить формулы для цифры

запишем выражение для числа А в основной и расширенной системах:

и ,

где

и - ранги числа А в основной и расширенной системах.

Приравнивая правые части этих выражений, определяем

:

, или обозначая через

целое число , а через величину , получаем . Наконец, представляя в виде , где k, q – целые неотрицательные числа и , получаем

, или

. (4.1´)

Формула (4.1´) и есть формула расширения диапазона чисел.

Для практической реализации этой формулы поступают следующим образом:

1. Вычисляют параметры основной и расширенной систем (ортогональные базисы, их веса, минимальные псевдоортогональные числа с их рангами и кратности).

2. Конструируют число

из минимальных псевдоортогональных чисел , , с рангами , которые однозначно определяются выбранной системой оснований . В результате, получают число , где - след числа, а его ранг находят по теореме о ранге суммы:

, (4.2´)

где

- число переходов по основанию

3. Расширяют число

по формуле расширения (4.1´). Пользуясь величиной ранга , вычисленной по формуле (4.2´), получают число , которое отличается от искомого числа А цифрами по двум последним основаниям.

4. Если

, то , т. е. - искомое расширение числа А.

5. Если

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

6. Если кратность

, то число является искомым расширением числа А, так как к числу , не превышающему прибавили число , не превышающее , т. е. не превышает Р, т. е. величины 1-го интервала.

7. Если

, то число может располагаться либо в последних частях 1-го интервала [0; P), либо в младших частях второго интервала [P; 2P), а тогда искомым является число .