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

Размещено на http://www.allbest.ru/

СОДЕРЖАНИЕ

• ВВЕДЕНИЕ
• 1 АНАЛИТИЧЕСКИЙ ОБЗОР МЕТОД И АЛГОРИТМОВ ОБРАБОТКИ ЧИСЕЛ
• 1.1 Арифметические операции над числами, представленными в позиционных системах счисления
• 1.2 Представление и обработка целых чисел в системе остаточных классов
• 1.3 Методы перевода чисел из системы остаточных классов в позиционную систему счисления
• 1.3.1 Метод ортогональных базисов
• 1.3.2 Перевод в обобщенную позиционную систему счисления
• 1.3.3 Интервальный метод перевода
• 1.4 Постановка цели и задач исследования
• Выводы по первому разделу
• 2 АНАЛИЗ РАЗЛИЧНЫХ СЛУЧАЕВ ДЕЛЕНИЯ ЦЕЛЫХ ЧИСЕЛ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ
• 2.1 Формальное деление, деление на произведение модулей системы остаточных классов, масштабирование
• 2.2 Деление произвольных чисел в системе остаточных классов на основе метода Ферма
• 2.3 Программная реализация и анализ метода Ферма в системе компьютерной алгебры Maple
• Выводы по второму разделу
• ЗАКЛЮЧЕНИЕ
• СПИСОК ЛИТЕРАТУРЫ
• ПРИЛОЖЕНИЕ
• ВВЕДЕНИЕ
• В современных цифровых вычислительных машинах, работающих в позиционной системе счисления, операция деления занимает особое место, и время ее выполнения примерно на порядок выше времени выполнения большинства элементарных операций. Время выполнения операции деления существенно возрастает в случае многоразрядных чисел.
• В системе остаточных классов время, затрачиваемое на выполнение операций, не зависит от разрядности числа, но трудности деления усугубляются тем, что эта операция в общем случае не является модульной, т.е. цифра частного по отдельному основанию уже не определяется только цифрами делимого и делителя по этому основанию, а требует в той или иной форме информации о значениях делимого и делителя в целом.
• Цель работы: повышение скорости выполнения операции деления в системе остаточных классов.
• Объект исследования: модулярные вычислительные структуры.
• Предмет исследования: методы и алгоритмы выполнения операции деления в системе остаточных классов.
• Основные задачи:

· анализ методов и алгоритмов обработки чисел в позиционных системах счисления;

· обзор представления и обработки чисел в системе остаточных классов;

· развитие методов деления в системе остаточных классов;

· моделирование и анализ метода деления Ферма в системе остаточных классов.

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

1 АНАЛИТИЧЕСКИЙ ОБЗОР МЕТОД И АЛГОРИТМОВ ОБРАБОТКИ ЧИСЕЛ

Системой счисления называется совокупность приемов наименования и записи чисел. В любой системе счисления для представления чисел выбираются некоторые символы (их называют цифрами), а остальные числа получаются в результате каких-либо операций над цифрами данной системы счисления. От особенностей системы счисления зависят наглядность представления числа при помощи цифр и сложность выполнения арифметических операций.

1.1 Арифметические операции над числами, представленными в позиционных системах счисления

Система называется позиционной, если значение каждой цифры (ее вес) изменяется в зависимости от ее положения (позиции) в последовательности цифр, изображающих число. Число единиц какого-либо разряда, объединяемых в единицу более старшего разряда, называют основанием позиционной системы счисления. Если число таких единиц равно , то система счисления называется p-ичной. Основание системы счисления совпадает с количеством цифр, используемых для записи чисел в этой системе счисления. Запись произвольного числа в p-ичной позиционной системе счисления основывается на представлении этого числа в виде многочлена

(1.1)

Позиционная система счисления обладает рядом важных свойств:

1) Основание системы счисления в ней самой всегда записывается как ; например, в двоичной системе счисления означает число .

2) Для записи числа в p-ичной системе счисления требуется цифр, где - целая часть числа.

3) Сравнение чисел производится поразрядно слева направо.

В настоящее время для большинства вычислительных машин основной системой счисления является позиционная двоичная система счисления.

Существуют два основных формата представления чисел в памяти компьютера. Один из них используется для кодирования целых чисел (формат с фиксированной точкой), второй (так называемое представление числа в формате с плавающей точкой) используется для задания некоторого подмножества действительных чисел. Все целые числа хранятся в памяти компьютера в формате с фиксированной точкой. В этом случае каждому разряду ячейки памяти соответствует всегда один и тот же разряд числа, а точка “располагается” справа от младшего разряда (вне разрядной сетки). Целые числа обычно занимают в памяти один или два байта и принимают в однобайтовом формате значения от () до (), а в двухбайтовом формате - от () до (). Таким образом, множество целых чисел, которые могут быть представлены в памяти компьютера, ограничено. Диапазон значений зависит от размера области памяти, используемой для размещения чисел. Для хранения целых чисел используется также формат длинных целых. Для хранения таких чисел отводится 4 ячейки памяти (32 бита). Достоинством представления чисел в формате с фиксированной точкой является простота и наглядность представления чисел, а недостатком - относительно небольшой диапазон представления величин.

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

,

где - мантисса числа; - основание системы счисления; - порядок числа.

Пример. .

Но представление числа в форме с плавающей точкой неоднозначно (), поэтому чаще всего в ЭВМ используют нормализованное представление числа в форме с плавающей точкой. Мантисса числа в таком представлении должна удовлетворять условию:

.

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

Пример. Нормализованное представление чисел:

; .

Число в формате с плавающей точкой занимает в памяти компьютера 4 байта. При этом отдельно выделяются разряды для хранения знака числа, знака порядка, порядка и самой мантиссы. Чем больше разрядов отводится под запись мантиссы, тем выше точность представления числа. Чем больше разрядов занимает порядок, тем шире диапазон от наименьшего отличного от нуля числа до наибольшего числа, представимого в машине при заданном формате [8].

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

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

1) если переводится целая часть числа, то она делится на , после чего запоминается остаток от деления. Полученное частное вновь делится на , остаток запоминается. Процедура продолжается до тех пор, пока частное не станет равным нулю. Остатки от деления на выписываются в порядке, обратном их получению;

2) если переводится дробная часть числа, то она умножается на , после чего целая часть запоминается и отбрасывается. Вновь полученная дробная часть умножается на и т.д. Процедура продолжается до тех пор, пока дробная часть не станет равной нулю. Целые части выписываются после запятой в порядке их получения. Результатом может быть либо конечная, либо периодическая дробь в системе счисления с основанием . Поэтому, когда дробь является периодической, приходится обрывать умножение на каком-либо шаге и довольствоваться приближенной записью исходного числа в системе с основанием .

Пример. Переведем число из десятичной системы счисления в двоичную (получив пять знаков после запятой в двоичном представлении).

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

При переводе чисел из системы счисления с основанием в десятичную систему счисления необходимо пронумеровать разряды целой части справа налево, начиная с нулевого, и в дробной части, начиная с разряда сразу после запятой слева направо (начальный номер ). Затем вычислить сумму произведений соответствующих значений разрядов на основание системы счисления в степени, равной номеру разряда. Это и есть представление исходного числа в десятичной системе счисления.

Пример. Переведем число из двоичной системы счисления в десятичную.

.

Получаем .

Арифметические действия над числами в любой позиционной системе счисления производятся по тем же правилам, что и в десятичной системе, так как все они основываются на правилах выполнения действий над соответствующими многочленами вида (1.1).

Все математические операции в процессоре сводятся к сложению. Для представления чисел со знаками в памяти ЭВМ используют прямой код. Правило представления p-ичного кода числа в прямом коде имеет вид:

где - значение цифры в i-ом разряде исходного кода.

Сложение в прямом коде чисел с одинаковыми знаками выполняется достаточно просто. Числа складываются и сумме присваивается код знака слагаемых.

Пример. Найдем сумму чисел и . Действительно,

Значительно более сложной является операция алгебраического сложения в прямом коде чисел с различными знаками. В этом случае приходится определять большее по модулю число, производить вычитание чисел и присваивать разности знак большего по модулю числа. Для упрощения выполнения операций алгебраического сложения в ЭВМ используются так называемые специальные коды. Они позволяют заменить арифметическую операцию вычитания операцией сложения. В качестве специальных в ЭВМ применяются обратный и дополнительный коды. Они образуются из прямых кодов чисел, причем специальный код положительного числа равен его прямому коду. Правило представления p-ичного кода числа в обратном коде имеет вид:

где - инверсия цифры , определяемая из соотношения:

- основание системы счисления;

- значение цифры в i-ом разряде исходного кода.

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

Правило представления p-ичного кода числа в дополнительном коде имеет вид:

где - инверсия цифры , определяемая из соотношения:

- основание системы счисления;

- значение цифры в i-ом разряде исходного кода.

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

При выполнении операции сложения чисел, представленных специальными p-ичными кодами знаковые разряды участвуют в операции наряду с цифровыми разрядами. При этом цифровые разряды слагаемых складываются как модули чисел по правилам p-ичной арифметики. Знаковые разряды и цифры переноса из младшего цифрового разряда при любом основании системы счисления складываются как одноразрядные p-ичные коды. Если при этом формируется перенос из знакового разряда, то он имеет вес единицы младшего разряда () при использовании обратного кода и должен быть добавлен в младший разряд результата. При использовании же дополнительного кода единица переноса из знакового разряда не принимается во внимание, т.е. отбрасывается.

Пример. Найдем разность и , используя обратный код. В обратном коде

, , тогда

При сложении сформировался перенос единицы из знакового разряда, имеющей вес младшего разряда , тогда искомая разность , т.е. .

Пример. Найдем разность и , используя дополнительный код. В дополнительном коде

, , тогда

При сложении сформировался перенос единицы из знакового разряда, которая отбрасывается, тогда .

Умножение и деление в любой позиционной системе счисления производится по тем же правилам, как в десятичной системе (цифры знаковых разрядов суммируются, при этом если формируется единица переноса из знакового разряда, то она отбрасывается) [13].

Пример. Умножим на :

Действительно,

Пример. Разделим число на число :

Действительно, .

Деление в ЭВМ сводится к выполнению последовательности вычитаний делителя сначала из делимого, а затем из образующихся в процессе деления частичных остатков и сдвига частичных остатков на один разряд влево (как показано в примере выше). Если в результате вычитания выясняется, что делимое или очередной частичный остаток больше или равны делителю, то в очередной разряд частного записывается единица и полученный в результате вычитания частичный остаток сдвигается влево на один разряд. Если в результате вычитания выясняется, что делимое или очередной частичный остаток меньше делителя, то в очередной разряд частного записывается нуль, к полученной разрядности добавляется делитель, чтобы восстановить предыдущий частичный остаток, и результат сдвигается влево на один разряд. Метод выполнения деления, когда в случае получения отрицательного остатка при вычитании (частичный остаток меньше делимого) к нему прибавляется делитель, называется методом деления с восстановлением остатка.

Деление с восстановлением остатка требует в наиболее неблагоприятном случае трёх тактов для формирования одного разряда частного: такта вычитания, такта сложения и такта сдвига. Недостатком этого метода является необходимость введения специального третьего такта для восстановления остатка, который значительно замедляет ход вычисления.

Обычно в вычислительных машинах для деления широко используется другой метод, называемый методом выполнения деления без восстановления остатка. Этот метод основан на прямом копировании действий при ручном делении («в столбик»). При реализации этого метода, если результат вычитания получился отрицательный, частичный остаток не восстанавливается путём прибавления делителя, а на следующем шаге деления вместо вычитания делимого производится его прибавление к частичному остатку. Если результат при этом остался отрицательным, то в очередную цифру частного записывается нуль и на следующем шаге также выполняется сложение. Если результат сложения получился положительным, то в очередной разряд частного записывается единица и на следующем шаге производится вычитание. Частичные остатки при делении без восстановления остатка получаются такими же, как и остатки после сдвига восстановленного остатка при делении с восстановлением остатка.

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

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

Позиционные системы счисления, в которых представляется и обрабатывается информация в современных вычислительных машинах, обладают существенным недостатком - наличием межразрядных связей, которые накладывают свой отпечаток на способы реализации арифметических операций, усложняют аппаратуру и ограничивают быстродействие. Особенно этот недостаток проявляется при работе с многоразрядными числами. Поиски новых путей повышения производительности вычислительных устройств привели исследователей к объективному выводу, что в этом направлении позиционная система счисления свои возможности исчерпала. Поэтому для того чтобы значительно повысить производительность вычислительных устройств необходимо применение систем счисления лишенных подобного недостатка [4].

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

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

Теория чисел применительно к представлению и обработке информации модулярными кодами начинается с элементарной идеи деления.

Пусть А и р - два произвольных целых числа, причем р - положительное число. Тогда в результате деления числа А на число р получаются частное и остаток. Делимость А на р удовлетворяет равенству

(1.2)

и неравенству

(1.3)

где l носит название частного, а - остатка.

Согласно (1.2) величина называется также наименьшим неотрицательным вычетом целого числа А по и обозначается символом .

Если остаток , то р и l - делители числа А; тогда говорят, что р делит А и пишут . Итак,

.

Без учета отрицательных делителей можно сказать, что каждое целое число имеет по крайней мере два делителя:

 (1.4)

Это не исключает существования других делителей.

Если А не имеет делителей, отличных от 1 и А, то А - простое число. Число 1 не считается простым, а 2 является единственным четным простым числом. Другие целые числа, имеющие несколько делителей, называются составными. Например, первыми в натуральном ряду составными числами являются 4, 6, 8, 9,... .

Допустим, что А - составное число, а р - его делитель. Тогда

(1.5)

где l - другой делитель.

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

Пример., .

Каждое составное число может быть представлено в виде произведения степеней простых чисел c положительными целыми :

(1.6)

Основная теорема арифметики утверждает, что это представление единственно.

Наибольшее положительное целое , делящее целые числа А и р, называется наибольшим общим делителем (НОД) и обозначается



Если , то А и р не имеют общих делителей, отличных от 1, и называются взаимно-простыми.

Наибольший общий делитель чисел находится с помощью алгоритма Евклида. Если в (1.2) и (1.3) число р - фиксированное, то оно называется модулем. Тогда для бесконечного числа вариантов выбора можно получить один и тот же остаток . В таких случаях говорят, что все эти числа А сравнимы по модулю р. Все целые числа А, дающие при делении на р один и тот же остаток, образуют класс вычетов по модулю р.

Пример. Если , то , , дают один и тот же остаток, так что 17, 22, 32 сравнимы по модулю 5. Для заданного модуля р имеется р таких классов, по одному на каждый возможный остаток, который может быть равен 0, 1, 2, ...,.

Классом по данному модулю р называется множество всех чисел, сравнимых с некоторым данным целым числом А.

Число классов по модулю р конечно и равно р.

Классами, взаимно простыми с модулем, называются классы, у которых наибольший делитель равен 1.

Приведенной системой вычетов по некоторому модулю является система чисел, взятых по одному из каждого класса, взаимно простого с модулем.

Число классов, взаимно простых с модулем р, равно числу целых чисел, не превосходящих р и взаимно простых с р. Число таких классов зависит от величины модуля и является функцией модуля. Эту функцию обычно называют функцией Эйлера и обозначают через .

Функцией Эйлера называется число натуральных чисел, не превосходящих р и взаимно простых с р.

Рассмотрим некоторые свойства этой функции, которые в дальнейшем будут играть важную роль.

Пример. . Чтобы определить функцию Эйлера , необходимо выписать натуральные числа от 1 до 24 и вычеркнуть числа, имеющие не равные единице общие делители с 24, т. е. числа, делящиеся на 2 и на 3. Оставшиеся числа (1, 5, 7, 11, 13, 17, 19, 23) образуют приведенную систему вычетов по модулю 24; равно числу этих чисел, т.е.

.

Функция Эйлера - мультипликативная, т. е.

при . (1.7)

Пример. , , , , , .

Два целых числа и , имеющие одинаковые остатки при делении на р, называются сравнимыми по модулю р.

Отношения сравнимости обозначают следующим образом:

. (1.8)

Выражение (1.8) эквивалентно выражению .

Если , то .

Соотношение сравнимости во многом сходно с равенством, однако оно менее сильное в том смысле, что равные величины сравнимы, а сравнимые не обязательно равны.

С точки зрения сравнимости чисел мы используем только остаток , получающийся при делении числа А на число р. Очевидно, что

. (1.9)

Операция взятия вычета определяется правилом

. (1.10)

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

При выполнении вычислений всегда можно заменить сравнение, которое устанавливает связь между целыми классами чисел с одним и тем же вычетом, равенством, включающим этот вычет.

Например, если

(1.11)

(1.12)

Вычисления с вычетами обычно достаточно просты, поскольку не имеют дела с числами, большими, чем модуль. Очевидно, что

(1.13)

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

Допустим, что , где ; тогда каждый элемент А из единственным образом представлен в виде

(1.14)

.

Линейная форма (1.14) при всех возможных принимает значения из диапазона , так как .

Различным наборам констант , где , соответствуют различные значения линейной формы (1.14).

Если в (1.14) положить , то получим р-адический (позиционный) код. При невыполнении этого условия код называется полиадическим (позиционным).

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

Как будет показано ниже, полиадическая система счисления широко применяется при определении позиционных характеристик непозиционного кода.

Если модули - попарно взаимно простые, то возможна новая, отличная от позиционной, машинная арифметика вычетов по , которая порождает непозиционный код. Преимуществом непозиционной арифметики является полное распараллеливание операций.

Представление чисел в СОК обеспечивается наименьшими неотрицательными вычетами по системе взаимно простых модулей :

(1.15)

Такое представление позволяет выполнять операции с большой скоростью вследствие отсутствия переносов от цифры к цифре.

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

выбрано как произведение большого числа малых модулей , то даже действия с весьма большими числами могут быть выполнены в такой системе с большим числом малых по величине модулей. P - объем диапазона представимых чисел. Как и в обобщенной позиционной системе, диапазон представимых чисел растет как произведение оснований , а разрядность чисел A растет как сумма разрядностей тех же оснований. В этой системе счисления путем выбора достаточно больших взаимно простых множителей можно представить какие угодно большие числа. Выбор взаимно простых множителей может быть осуществлен путем выбора чисел в натуральном ряду. Последовательность простых чисел неограниченна.

Для того, чтобы из множества натуральных чисел выделить простые, можно воспользоваться способом решета Эратосфена, суть которого состоит в следующем: если во множестве натуральных чисел 2, 3, 4, ..., N зачеркнуть числа, кратные первым r простым числам - 2, 3, ..., р, то первое (наименьшее) незачеркнутое число будет простым.

Если вычеркнуть все числа, кратные всем простым числам до , т.е. выбрать r так, что , то оставшиеся числа будут совпадать с множеством всех простых чисел р таких, что .

Алгоритм нахождения простых чисел в множестве натуральных чисел 2, 3, 4, 5, 6, ..., N следующий. Первое число 2 - простое. Вычеркиваются все числа, кратные 2; первое невычеркнутое число 3 - простое. Вычеркиваются все числа, кратные 3; первое невычеркнутое число 5 - простое и т. д. Продолжаем этот процесс, пока не вычеркнем все числа, кратные найденным простым числам 2, 3, ..., р, где , а следующее простое . Все оставшиеся невычеркнутыми числа дадут нам множество простых чисел, лежащих между и (включая N, если оно простое), а вместе с ранее найденными простыми 2, 3, ..., р будут получены все простые числа, не превосходящие N.

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

Рассмотрим правила выполнения операций сложения и умножения в системе остаточных классов в случае, если оба числа и результат операции находятся в диапазоне . Пусть операнды A и B представлены соответственно остатками и по основаниям при . Результаты операций сложения и умножения и представлены соответственно остатками и по тем же основаниям , т. е.

;

;

;

.

и при этом имеют место соотношения:

, , ,

Утверждается, что

.

при этом в качестве цифры результата берется соответственно

(1.16)

(1.17)

Эти операции относят к числу модульных операций, они могут быть распараллелены по каждому модулю. Таким образом, одно из достоинств СОК - это независимость образования разрядов числа, в силу чего каждый разряд несет информацию обо всем числе, а следовательно, возникает возможность независимой параллельной обработки разрядов, то есть поразрядного выполнения операций. При выполнении сложения, вычитания, умножения каждая цифра зависит лишь от соответствующих цифр операндов.

Рассмотрим примеры, иллюстрирующие приведенные выше правила выполнения операций сложения и умножения.

Пример. Пусть основаниями системы являются

. Диапазон системы определится как . Сложим число с числом .

По выбранным основаниям числа A и B в системе остаточных классов будут представлены как

В соответствии с (2.20) получим . Легко проверяется, что число есть и равно сумме операндов.

Пример. Умножим число на число (основания прежние).

В системе остаточных классов числа и будут представлены как

.

В соответствии с (2.21) получим . Легко проверяется, что число есть и равно произведению операндов [11].

1.3 Методы перевода чисел из системы остаточных классов в позиционную систему счисления

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

Рассмотрим основные методы перевода чисел из СОК в ПСС. Система остаточных классов обладает одной особенностью, которую можно отнести к недостаткам этой системы: нельзя визуально определить величину числа, представленного в СОК, а следовательно затруднительно и выполнение таких операций, как сравнение чисел, определение знака числа. Один из путей решения этой проблемы состоит в преобразовании чисел из СОК в позиционную систему счисления. Оценим существующие способы перевода, как традиционные (метод ортогональных базисов; перевод числа в ОПС), так и недавно появившиеся интервальные методы перевода.

1.3.1 Метод ортогональных базисов

Метод восстановления числа по его остаткам был найден ещё в Китае 2 тыс. лет назад. Основой этого метода является теорема, названная поэтому Китайской теоремой об остатках (КТО).

Теорема. Пусть - попарно взаимно простые числа,

тогда существует единственное неотрицательное решение по модулю P следующей системы сравнений:

,

,

…

,

, где .

Эта теорема лежит в основе метода ортогональных базисов при переводе из системы остаточных классов в позиционную систему счисления [7].

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

Пусть основания системы остаточных классов ;

объём диапазона системы. С выбором системы определяются её основные константы - базисы , . Задача перевода числа в ПСС заключается в определении таких чисел , чтобы . Для однозначного определения на базисы системы накладывается ряд ограничений, которым соответствуют базисы

,

,

…

которые являются ортогональными.

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

, . (1.18)

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

. (1.19)

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

Если система нормирована по наибольшему основанию, то такую систему оснований будем называть просто нормированной системой.

Согласно Китайской теореме об остатках, число

.

Т.о., если найдены ортогональные базисы для системы оснований, то для перевода числа достаточно вычислить и ввести эту сумму в диапазон вычитанием величины, кратной Р, т.е.

(1.20)

где - ранг числа А, показывающий сколько раз надо вычесть величину диапазона Р из полученного числа, чтобы вернуть его в диапазон.

Так как ортогональные базисы полностью определяются выбором оснований системы, то они могут быть заранее вычислены, причём единственный раз. Решения сравнений (1.19) предлагается искать с помощью расширенного алгоритма Евклида.

Пример. Пусть дана система оснований , , объём диапазона . Перевести число в позиционную систему.

Вычислим ортогональные базисы.

Для этого найдём величины

,,,,

.

Ищем веса базисов по (1.19):

;

;

;

.

Тогда по (1.18) получаем сами базисы:

,

,

,

,

.

Вычислим величину числа А, согласно (1.20):

.

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

1.3.2 Перевод в обобщенную позиционную систему счисления

Другой метод определения величины числа связан с переводом числа из системы остаточных классов в обобщенную позиционную систему счисления (ОПСС). Для того чтобы рассмотреть этот метод, выявим связь между представлением некоторого числа A в этих двух системах.

Пусть СОК задаётся основаниями и - число в этой системе. И пусть, - также основания ОПСС, тогда число A можно представить в виде

(1.21)

где () - коэффициенты (цифры) ОПСС.

Очевидно, что диапазоны чисел, представимых в СОК и ОПСС совпадают, т.е. можно говорить о наличии взаимооднозначного соответствия между множеством представлений чисел в СОК и ОПСС.

Равенство (1.21) можно переписать в виде

,

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

, где ,

, где ,

…

, где (1.22)

Причём при определении цифр по формулам (1.22) все вычисления можно вести в СОК.

Действительно, из (1.22) следует, что , т.е. - первая СОК цифра или . Для получения , сперва представим в остаточном коде. Очевидно делится на . Более того, взаимно просто со всеми другими модулями. Следовательно, для нахождения цифры может быть использована процедура деления без остатка: . Таким путём, с помощью вычитаний и делений в остаточной записи все цифры ОПСС могут быть получены. При этом замечено, что , , и, вообще, для .

Перевод, осуществляемый согласно алгоритму (1.22), содержит всего остаточные арифметические операции вычитания и деления без остатка, где n - число модулей системы. Может быть предложена некоторая модификация рассмотренного алгоритма в том плане, что операция деления заменяется операцией умножения. Для этого предварительно вычисляется констант , которые удовлетворяют условию

, . (1.23)

Эти константы можно, например, получить из расширенного алгоритма Евклида.

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

Если константы вычислены, то вычисление цифр ОПСС по алгоритму (1.22) может быть переписано в виде:

,

,

,

…

. (1.24)

Константы принято также записывать в виде и называть обратными элементами по умножению для чисел по модулю .

Пример. Пусть дана система оснований , , объём диапазона . Перевести число в позиционную систему. Перевод в ОПСС удобно осуществлять, записывая промежуточные вычисления в таблицу.

Таблица 1.1

Действия	Модули	Цифры
						ОПС
A	1	3	8	7	15
-
	1	1	1	1	1
	0	2	7	6	14
		6	7	10	22
		1	10	3	7
-
		1	1	1	1
		0	9	2	6
			6	7	4
			2	14	24
-
			2	2	2
			0	12	22
				3	10
				17	5
-
				17	17
				0	31
					34
					22

Согласно (1.21):

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

1.3.3 Интервальный метод перевода

Достаточно эффективными методами перевода чисел из СОК в ПСС являются интервальные методы, основанные на интервальных характеристиках чисел. Одна из таких характеристик - номер интервала.

Пусть СОК задана системой оснований , с объёмом диапазона . Выберем дробирующий модуль и проведём дробление заданного диапазона на интервалы путём деления P на модуль . Тогда количество интервалов , а длина интервала определяется величиной модуля. В результате величину любого числа А, заданного в СОК по выбранным основаниям можно определить по номеру интервала:

, (1.25)

в котором находится число А и по цифре числа Ав СОК по модулю , т.е.

. (1.26)

Так как , то по теореме Эйлера:

 (1.27)

где - функция Эйлера. Причём если - простое число, то . Подставляя (1.27) в (1.20), учитывая (1.18) и (1.19) число А можно записать в виде:

(1.28)

Для определения номера интервала подставим (1.28) в (1.25):

(1.29)

Учитывая, что , перепишем (1.29) в виде:

(1.30)

Так как является делителем чисел , , P, то

,

где , и - постоянные коэффициенты, определённые системой оснований.

Таким образом,

(1.31)

Подставляя (1.31) в (1.26), получим позиционное представление числа А:

(1.32)

Пример. Пусть дана система оснований , , объём диапазона . Перевести число в позиционную систему.

Выберем в качестве дробирующего основания , согласно (1.31)

тогда .

Вычисляем значение функции Эйлера для каждого из модулей



, тогда

.

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

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

1.4 Постановка цели и задач исследования

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

К достоинствам системы остаточных классов следует отнести:

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

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

К недостаткам СОК следует отнести:

· невозможность визуального сопоставления чисел, так как внешняя запись числа не дает представления о его величине;

· отсутствие простых признаков выхода результатов операций за пределы диапазона;

· ограниченность действия системы сферой целых положительных чисел;

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

Основным из достоинств СОК является независимость образования разрядов числа, в силу чего каждый разряд несет информацию обо всем числе, следовательно, возникает возможность независимой параллельной обработки разрядов, то есть поразрядного выполнения операций. При выполнении модульных операций: сложения, вычитания, умножения, применение аппарата СОК существенно облегчает нахождение результата, особенно в случае многоразрядных чисел. Однако, из-за невозможности визуального сопоставления чисел и, прежде всего, ограниченности действия системы сферой целых положительных чисел, усложняется реализация в СОК немодульных операций, основными из которых являются перевод чисел в позиционную систему счисления и операция деления.

Даже в цифровых вычислительных машинах, работающих в позиционной системе счисления (например, в двоичной), операция деления стоит особняком и время ее выполнения примерно на порядок выше времени выполнения большинства элементарных операций.

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

В общем случае деления числа А на константу d следует различать две возможности: когда d не является основанием системы и когда d входит в систему оснований.

В первом случае трудность состоит в установлении самого факта делимости A на d или, что то же, в приведении числа к ближайшему к нему числу А', делящемуся нацело на d. Само же деление может производиться поразрядно.

Во втором случае легко определяется, делится ли А на d, также легко определяется и ближайшее к А число А', делящееся нацело на d, но зато определение цифры частного по основанию требует раскрытия неопределенности , для чего и возникает необходимость привлечения информации о всем числе [6].

Цель исследования: анализ основных методов и алгоритмов деления произвольных целых положительных чисел в системе остаточных классов.

Задачи исследования:

1) рассмотреть вышеперечисленные случаи деления в системе остаточных классов;

2) изучить метод деления Ферма произвольных чисел в системе остаточных классов;

3) реализовать и проанализировать метод деления Ферма произвольных чисел в системе остаточных классов.

Выводы по первому разделу

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

2 АНАЛИЗ РАЗЛИЧНЫХ СЛУЧАЕВ ДЕЛЕНИЯ ЦЕЛЫХ ЧИСЕЛ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ

2.1 Формальное деление, деление на произведение модулей системы остаточных классов, масштабирование

Рассмотрим наиболее простой случай, когда делимое нацело делится на делитель.

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

Пусть даны два числа в системе с основаниями , а именно:

,

и пусть число есть частное от деления А на В, т.е.

(2.1)

или .

Для произведения получим выражение

, (2.2)

где - целое неотрицательное число, удовлетворяющее условию ,

. Приравнивая ВС к A, получим:

(2.3)

Выражение (2.3) однозначно определяет цифры частного. Таким образом, деление в случае, когда оно точно выполнимо (т. е. когда А кратно В), может осуществляться поразрядным делением цифр на . Здесь поразрядное деление понимается в том смысле, что если непосредственно не делится нацело на , то к прибавляется столько раз , чтобы делилось нацело на ().

При условии такое деление единственным образом определит цифру . Заметим, что такое деление возможно при дополнительном условии .

Пример. Пусть дана система оснований , объём диапазона . Разделим число на .

Подбираем числа : получаем

. Используя любой из рассмотренных выше методов перевода, можно убедиться, что

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

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

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

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

Другой метод расширения системы оснований позволяет определить цифру числа по новому основанию, базируясь на таких позиционных характеристиках числа, как ранг числа, след числа, которые требуют расчёта ряда параметров (ортогональных базисов, их весов, минимальных псевдоортогональных чисел, их рангов с кратностями), вычисление которых может показаться громоздким. Однако все эти параметры определяются только основаниями системы, поэтому могут быть рассчитаны заранее. Более того, с помощью указанных позиционных характеристик могут быть организованы и другие немодульные процедуры, что позволяет построить машинную арифметику.

Еще один путь решения поставленной задачи представляет собой перевод числа из СОК в ОПСС с дополнительным финальным шагом, причем данный метод обладает рядом преимуществ перед прочими:

во-первых, все вычисления идут в параллельных каналах по отдельным модулям;

во-вторых, не требуется вычисления большого количества дополнительных величин (необходимо наличие в памяти только констант );

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

Рассмотрим этот метод.

Пусть СОК состоит из оснований . Объем диапазона этой системы будет . Добавим к числу оснований СОК новое основание . Объем диапазона этой системы . Тогда любое число A из диапазона в обобщенной позиционной системе счисления представимо в виде . Если число A будет лежать в первоначальном диапазоне , то в ОПСС цифра . Этот факт и используется для получения остатка от деления числа A на новое основание СОК .

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

Для определения этой цифры рассматриваем алгоритм перевода числа из СОК в ОПСС, включая неизвестную цифру в проводимые операции. При этом мы последовательно будем получать цифры ОПСС и выражение для цифры . Но так как по предположению число , то цифра . Из полученного соотношения и определяем искомую цифру .

Этот алгоритм может быть несколько видоизменен за счет следующего свойства:

Фактически величина используется только на последнем шаге определения цифры . Поэтому в столбце по новому основанию с самого начала можно записать ноль и применить алгоритм перевода числа из СОК в ОПСС.

Пусть по этому алгоритму будет получено что для числа . Тогда для числа A можно найти из соотношения:

Так как результат образования цифры в СОК по новому основанию зависит только от первых цифр, то операцию расширения можно проводить сразу по нескольким основаниям.

Пример. Пусть задана система оснований , , ,

, объем диапазона . И пусть задано число в этой системе оснований. Найдем расширенное представление этого числа, добавляя модули и .

Для этого запишем нули в качестве неизвестных цифр и применим вышерассмотренный алгоритм расширения системы оснований.

Константы вычислены заранее и записаны в виде матрицы

.

Тогда получаем:

Таблица 2.1

Действия	Модули	Цифры
							ОПС
A	1	3	10	8	0	0
-
	1	1	1	1	1	1
	0	2	9	7	-1	-1
		6	7	10	22	9
		1	11	13	21	8
-
		1	1	1	1	1
		0	10	12	20	7
			6	7	4	14
			8	8	-6	-4
-
			8	8	8	8
			0	0	-14	5
				3	10	4
				0	-11	3
-
				0	0	0
				0	-11	3
					34	9
					13	10

Цифры по основаниям и находим из соотношений:

Откуда получаем и .

Таким образом, число в системе оснований , , , , и .

Сформулируем важную теорему о делении без остатка, которая будет играть значительную роль в дальнейшем.

Теорема 1.

 (2.4)

для всех модулей тогда и только тогда, когда a делится на b (без остатка) и .

Проиллюстрируем деление без остатка на примере.

Пример. Пусть основания системы , , , , объём диапазона . Разделим число на число .

Вычисляем обратные элементы по умножению:

Будем теперь делить число A на модуль или произведение первых степеней модулей СОК. Это деление основано на теореме о делении с остатком.

Теорема 2. Для любых двух целых чисел A и B всегда возможно причём единственным образом деление с остатком, т.е.

(2.5)

где A - делимое; B - делитель; - неполное частное; - остаток. Из (2.5)



где величины - целые числа.

Если делитель B есть модуль или произведение первых степеней модулей, то нетрудно найти.

Тогда по теореме 1 для всех i, для которых получаем

(2.6)

По формуле (2.6) можно вычислить все СОК цифры , для которых . Цифры по остальным модулям могут быть определены при помощи расширения системы оснований. Таким образом, алгоритм деления на модуль СОК, или произведение первых степеней модулей СОК, состоит из двух операций, а именно, деления без остатка и расширения системы оснований.

Рассмотрим пример, иллюстрирующий приведённый алгоритм.

Пример 1. Пусть основания системы , , , , объём диапазона . Разделим число на число . Сперва найдём число , которое делится на 61, оно равно , так как , то . Это число делится на . Исключая модуль , который сам является делителем, все модули взаимно просты с делителем. Поэтому, деление без остатка может быть применено для нахождения цифр частного, кроме цифры по модулю . Умножая , получим

Учитывая, что объём диапазона , то мы работаем с числами из интервала . Так как A расположено в этом интервале, то должно быть в интервале . Так как модули , , , дают интервал расширений , то СОК представление

единственно. Цифра по модулю, может быть найдена с помощью алгоритма расширения диапазона. Применим метод расширения системы оснований с помощью ОПС, записывая вместо недостающей СОК цифры по модулю . Дальнейшие вычисления приведены в таблице.

Таблица 2.2

Действия	Модули	Цифры ОПС
	1	5	7	4	0
-
	1	1	1	1	1
	0	4	6	3	-1
		6	7	10	31
		2	3	11	30
-
		2	2	2	2
		0	1	9	28
			6	7	50
			6	6	-3
-
			6	6	6
			0	0	-9
				3	47
				0	4
-
				0	0
				0	4
					45
					-3

Если обозначить , то получим:

откуда . Следовательно,

Пример 2. Пусть основания системы , , , , объём диапазона . Разделим число

на число .

Обозначим результат .

Решение примера приведём в таблице. возьмем из предыдущего примера.

Таблица 2.3

Действия	Модули
	1	5	7	4	-
-
	1	5	5	5	-
	0	0	2	-1	-
	1	-	6	7	-
	0	-	12	12	-

Записываем в недостающие столбцы для расширения оснований.

Таблица 2.4

Действия	Модули	Цифры ОПС
	0	0	12	12	0
-
	0	0	0	0	0
	0	0	12	12	0
		6	7	10	31
		0	6	6	0
-
		6	6	6	6
		5	0	0	55
		6		3	47
		8		0	23
-
		0		0	0
		8		0	23
		7			45
		1			-2

Цифры по основаниям и находим из соотношений:

и

Откуда и . Следовательно,

Из примеров 1 и 2 следует, что они содержат не более n сложений и такое же число умножений. Кроме того, в конце алгоритма необходимо решить уравнение для Z. Важно заметить, что число операций не зависит от того, является ли делителем один модуль или произведение модулей. Вначале мы заметили, что делитель должен состоять только из n первых степеней модулей. Если , где , то не содержит информацию, необходимую для определения . Следовательно, не может быть определено непосредственно. Операцию деления на степень модуля можно осуществить только через повторение операции деления.

Можно отметить два важных недостатка рассмотренного алгоритма: округление результата всегда происходит с недостатком, и этот алгоритм применим только для положительных чисел. Первый недостаток можно устранить: если при делении числа на основание остаток то в качестве ближайшего целого числа, делящегося на следует выбирать ; если же то в качестве ближайшего целого числа, делящегося на нацело, следует выбрать

.

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