Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Модулярная арифметика




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

Китайская теореме об остатках.

 

Пусть n1 ,n2, …, nr - попарно взаимно простые числа. Пусть а12, …, аr произвольно целые числа. Тогда система

имеет по крайней мере одно решение. Кроме того, если х' – другое решение этой системы, то хºх'(mod n1·n2··nr ).

 

 

Смешанная система счисления.

 

Идея, принадлежавшая Л.Гарнеру и представленная у Д.Кнута, состоит в том, чтобы связать с модулярным представлением еще одно представление, называемое смешанной системой счисления.

Основанием смешанной системы счисления называется множество из r³2 целых чисел n1,n2,…,nr, не обязательно взаимно простых. Если положим и n=n1·n2·…·nr, то имеется биекция (взаимно однозначное соответствие):

Обратное отображение определяется при помощи евклидовых делений:

x=q1n1+z1, q1= q2n2+z2, … , qr-1= qrnr+zr.

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

 

Формулы определения цифр.

 

Пусть n1,n2,…,nr – попарно взаимно простые числа. Пусть и Ci – обратные к Ni по модулю ni.

Рассмотрим целое число x, модулярные компоненты которого x1,x2,…,xr тогда цифры x в системе со смешанным основанием ni обозначим через zi ; они находятся по формулам:

z1= x1mod n1,

z2= C2(x2-z1) mod n2,

z3= C3(x3-(N2z2+z2)) mod n3,

……………

zr= Cr(xr-(Nr-1zr-1+…+ N2z2+z1)) mod nr.

Чтобы осуществить обратный переход от системы со смешанным основанием к модулярному представлению, достаточно провести следующие вычисления:

x1=z1,

x2=(z1+z2n1)mod n2,

x3=(z1+z2n1+z3n1n2)mod n3,

xr=(z1+z2n1+…+zrn1n2…nr-1)mod nr.

 

 

Сравнение чисел, определение цифр в позиционной системе счисления.

 

Пусть имеются два целых числа x и x', заданные своими модулярными компонентами, и мы хотели узнать, которое из этих чисел (можем считать, что они оба лежат в [0,m)) больше, по возможности не вычисляя явный вид этих чисел. Вычислим сначала цифры zi и zi', соответствующие x и x' в смешанной системе счисления, определяемой модулями. В этом случае x<x' тогда и только тогда, когда наибольший вес i, на котором различаются эти числа, таков, что zi<zi'.


Дата добавления: 2015-04-18; просмотров: 17; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты