Xreferat.com » Рефераты по математике » Математические основы системы остаточных классов

Математические основы системы остаточных классов

loading="lazy" src="http://xreferat.ru/image/54/1306471244_250.gif" alt="" width="43" height="31" align="BOTTOM" border="0" />(+)…)),


откуда следует, что цифры ОПС могут быть получены из соотношений:


=–=–, где =,

=–=–, где =, (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ґ) представлено в таблице


Перевод числа из СОК в ОПС


Действия

Модули

Цифры ОПС


= 2

= 3

= 5

= 7

= 11


–

1

2

1

1

1

4

1

7

1

==1

–


0

1

2

0

3

3

4

6

6


–


–

2

2

0

2

5

2

3

2

= 2 =

–



0

3

2

3

5

1

4


–



–

1

1

1

4

1

= 1 =

–




0

0

3

3

9


–




0

5

0

= 0 =

–




0

5

8







7

–

= 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ґ) можно отнести следующие:

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

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

    Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
    Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: