Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Система счисления в остаточных классах (СОК)
Поиски новых путей повышения эффективности выполнения арифметических операций привели к заключению, что в рамках обычной позиционной системы счисления ускорения операций добиться сложно. Следует отметить, что позиционные системы счисления обладают существенным недостатком – наличием межразрядных связей, влияющих на способы реализации арифметических операций. В конечном итоге это приводит к усложнению аппаратуры и снижению быстродействия. Оказалось, что арифметика, в которой межразрядные связи отсутствовали бы, может быть построена на основе непозиционной системы счисления, в частности системы счисления в остаточных классах. В системе остаточных классов числа представляются остатками от деления на выбранную систему оснований и все рациональные операции могут выполняться параллельно над цифрами каждого разряда в отдельности. В то же время системе остаточных классов присущи некоторые недостатки: ограниченность действий этой системы полем целых положительных чисел, трудность определения соотношений чисел по величине, определения выхода результата операции из диапазона и некоторые другие. Определение. Если задан ряд положительных целых чисел p1, p2,..., pn, называемых в дальнейшем основаниями системы, то под системой счисления в остаточных классах будем понимать такую систему, в которой целое положительное число представляется в виде набора остатков (вычетов) по выбранным основаниям N = (a1, a2,..., an), причем образование цифр ai осуществляется следующим образом: ai = N - , для i = 1, 2,..., n, (5) где [] означает целую часть, то есть цифра i-го разряда ai числа N есть наименьший положительный остаток от деления N на pi. Таким образом, в СОK в отличие от обобщенной позиционной системы счисления образование цифры каждого разряда производится независимо друг от друга. Очевидно, что ai < pi. В теории чисел доказано, что если числа pi взаимно простые между собой, то описанное цифрами a1, a2,..., an представление числа N -- единственно. Диапазон представимых чисел в СОK равен: = p1, p2,..., pn. Рассмотрим правила выполнения операций сложения и умножения в СОK в случае, если числа и результат находятся в диапазоне [O, ]. Пусть операнды A и B представлены соответственно остатками ai и bi по основаниям pi, i=1,2,...,n. Результаты операций A+B и A∙B представлены остатками gi и di по тем же основаниям pi, то есть
A=(a1 a2...,an), B=(b1, b2,...,bn), A+B=(g1, g2,...,gn), A∙B=(d1, d2,...,dn), при этом A < B < A+B < A∙B < gi º ai + bi (mod pi), то есть gi сравнимо с ai + bi по модулю pi; di º ai bi (mod pi). При этом gi º ai + bi - , di º ai bi - . С учетом (5) отсюда следует: gi = A+B - . (6) Из представления A и B следует: А = ki pi + ai, B = li pi + bi, где ki и li - целые неотрицательные числа. Тогда A + B = (ki + li) pi + ai + bi, =ki + li + , A + B = (ki + li)pi + . Подставляя полученные выражения в (6), получим: gi º ai + bi - . (7) В случае умножения di º ai bi - . Аналогично сложению (A + B) получим: A∙B = ki li pi2 + (ai li +bi ki)pi + ai bi, = ki li pi + ai li +bi ki + . Таким образом, di º ai bi - . (8) Пример. Сложить числа А = 23 и В = 48 в СОК. Пусть основаниями системы являются p1 = 3, p2 = 5, p3 = 7. По выбранным основаниям числа А и В в СОК примут вид: А = 23 = (2, 3, 2), B = 48 = (0, 3, 6), получим А + В = (2, 1, 1). Легко проверить, что 23 + 48 = 71, а число 71 = (2, 1, 1) в СОК. Пример. Умножить число А=14 на В=8 в СОК. А=14=(2, 4, 0), B=8=(2, 3, 1). В соответствии с (4) получим: g1 = 4 - = 4 - 3 = 1, g2 = 12 - = 12 - 2∙5 = 2, g3 = 1 - = 1 - 0.7 = 1. Таким образом, А∙В = 122 = (1, 2, 1). Охарактеризуем в общих чертах достоинства и недостатки введенной СОK. Достоинства: § независимость образования разрядов числа, в силу чего каждый разряд несет информацию обо всем исходном числе, а не о промежуточном числе, получившемся в результате формирования младших разрядов (позиционная система счисления). Отсюда вытекает независимость разрядов числа друг от друга и возможность их параллельной обработки, что в свою очередь в дальнейшем позволяет вводить принципиально новые методы арифметического контроля. При введении дополнительного контрольного основания остаток, взятый по этому основанию, при его избыточности позволяет контролировать и исправлять ошибки в цифрах по рабочим основаниям; § малоразрядность остатков, представляющих число. Ввиду малого количества кодовых комбинаций открывается возможность построения табличной (не вычислительной) арифметики.
Недостатки: § невозможность визуального сопоставления чисел, так как внешняя запись числа не дает представления о его величине;
§ отсутствие простых признаков выхода результата операций за пределы [0,ρ]; § ограниченность действий системы сферой целых положительных чисел; § получение во всех случаях точного результата исключает возможность приближенных вычислений, округлений.
|
||||||
Последнее изменение этой страницы: 2016-04-08; просмотров: 303; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.129.70.157 (0.007 с.) |