Пример 3.30

Представление чисел в системе остаточных классов

Машинная арифметика в остаточных классах

Органическим недостатком любой позиционной системы счисления является наличие межразрядных связей. Действительно, результат сложения в i -м разряде зависит не только от значений i -х разрядов слагаемых, но и от переноса из i -1 разряда и, в конечном итоге — от значений всех младших разрядов слагаемых: i -1, i -2,..., 1, 0. Поэтому вычисление разрядов суммы мажет проходить только последовательно с учетом формирования переноса из предыдущего (младшего) разряда. Это обстоятельство препятствует распараллеливанию процесса вычисления и, естественно, снижает быстродействие процессора.

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

Поиск новых путей построения арифметических устройств ЭВМ, позволяющий исключить зависимость между разрядами при выполнении арифметических операций, привел к применению в машинной арифметике аппарата теории вычетов — одного из разделов теории чисел. В рамках этого аппарата разработана [1] непозиционная система счисления — система счисления в остаточных классах (СОК).

Будем говорить, что " а есть остаток числа A по модулю p " (иногда говорят, что " A сравнимо с a по модулю p "), если имеет место следующее равенство:

(3.33)

где — целая часть частного A/p, причем a — наименьший целый остаток от деления A на р.

Часто это соотношение записывают так:

(3.34)

(Страница83)

Для представления чисел в СОК необходимо выбрать т. н. систему оснований — множество целых чисел р₁, р₂,..., р_п. Тогда любое число A может быть представлено в СОК следующим образом:

A=(a₁, a₂,..., a_n), (3.35)

где

Обозначим произведение

(3.36)

Можно показать [1], что если все основания p_i — взаимно-простые числа, то между числами 0, 1, 2,..., (P -1) и числами, представленными в СОК согласно (3.35), имеет место взаимно-однозначное соответствие.

Пусть p ₁=3, p ₂⁼5, р₃=7 — взаимно-простые числа.

P =3*5*7=105.

Представим в СОК несколько десятичных чисел:

Заметим, что при выходе за пределы диапазона [0, (P - 1)] нарушается взаимно-однозначное соответствие между представлением чисел в позиционной системе счисления и СОК. Действительно.

и т. д. Очевидно, для расширения диапазона представления чисел в СОК следует увеличить число и/или значения оснований.

Дата добавления: 2015-04-25