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

 

СОДЕРЖАНИЕ


ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

.3 Программная реализация и анализ метода Ферма в системе компьютерной алгебры Maple

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

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ


ВВЕДЕНИЕ


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

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

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

Объект исследования: модулярные вычислительные структуры.

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

Основные задачи:

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

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

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

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

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


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


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


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


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


(1.1)


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

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

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

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

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

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

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


,


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

Пример. .

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


.


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

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

; .

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

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

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

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

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

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

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

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

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

.

Получаем .

Арифметические действия над числами в любой позиционной системе счисления производятся по тем же правилам, что и в десятичной системе, так как все они основываются на правилах выполнения действий над соответствующими многочленами вида (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 Методы перевода чисел из системы остаточных классов в позиционную систему счисления


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

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


.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

ДействияМодулиЦифры ОПСA138715-1111102761467102211037-1111092667421424-22201222310175-17170313422

Согласно (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 АНАЛИЗ РАЗЛИЧНЫХ СЛУЧАЕВ ДЕЛЕНИЯ ЦЕЛЫХ ЧИСЕЛ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ


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


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

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

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


,


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


(2.1)


или .

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


, (2.2)

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

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


(2.3)


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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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



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

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

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

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

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


.


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


Таблица 2.1

ДействияМодулиЦифры ОПСA1310800-1111110297-1-1671022911113218-11111010122076741488-6-4-888800-14531040-113-0000-1133491310

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



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

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

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

Теорема 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

ДействияМодулиЦифры ОПС15740-111110463-1671031231130-222201928675066-3-66600-934704-000445-3

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

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

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

на число .

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

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


Таблица 2.3

ДействияМодули1574--1555-002-1-1-67-0-1212-

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


Таблица 2.4

ДействияМодулиЦифры ОПС0012120-0000000121206710310660-66665005563478023-00080237451-2

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


и


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

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

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


.


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

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

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

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


(2.7)


Это можно переписать в виде


(2.8)

(2.9)


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

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

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

Пусть , тогда


(2.10)


где

Из (2.10) видно, что делится без остатка на .

На основании того, что


(2.11)


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

можно записать выражения для и :

(2.12)

(2.13)

где


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

1.Определение ранга числа, выражение (2.13).

2.Определение , выражение (2.12).

.Вычисление , выражение (2.10).

.Нахождение масштабированного числа от деления на .

При этом нахождение осуществляется с помощью совокупности модульных операций:


(2.14)


В случае, если - простое число


(2.15)


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

. Требуется число промасштабировать числом .

Согласно выражению (2.13) в условиях конкретного примера находим ранг числа. В соответствии с выражением (2.13) определяем а также Следовательно, выражение (2.13) в условиях примера имеет вид:



Далее находим и затем остаток от деления на величину по формуле (2.12):



По формуле (2.11) находим

На основе формулы (2.15) определяем и далее определяем по формуле (2.14):


т.е.


Полученное масштабированное число можно представить в сокращенной, либо в расширенной системе оснований.

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


2.2 Деление произвольных чисел в системе остаточных классов на основе метода Ферма


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

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

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

Допустим, что делимое и делитель являются положительными числами, и - модули СОК.

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


(2.16)


Далее определяется приблизительный делитель по формуле


(2.17)

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


(2.18)


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


и (2.19)


для получения , и так далее.

Эта повторяющаяся процедура продолжается до тех пор, пока или .

Если это возникает на r-м повторении, то


(2.20)


Так как является или модулем или произведением модулей СОК, то нахождение величины представляет собой деление на модуль или произведение модулей СОК [9].

Рассмотрим пример.

Пример. Пусть модули СОК и - диапазон. Разделим на и найдем округленное частное .

Представим в виде (2.16) в ОПСС в порядке уменьшаемой значимости:

,

где Тогда приблизительный делитель с учетом (2.17) и (2.18) будет равен .

Найдем и выполним действия с учетом рекурсивных соотношений (2.19)

Из (2.20) так как , , то . Тогда округленное частное будет Действительно


2.3 Программная реализация и анализ метода Ферма в системе компьютерной алгебры Maple


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

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

) выбор соответствующей системы оснований;

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

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

) определение приближенного делителя;

) нахождение частного от деления на приближенный делитель методом Ферма.

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


Таблица 2.5

ДелимоеДелитель815212835414816101418222711591216191116913171111469111117121111116

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

По данным таблицы 2.5 можно сделать вывод, что с увеличением разрыва между делимым и делителем (при условии, что делимое больше делителя), количество итераций возрастает. Т.е. число итераций будет бесконечно возрастать при увеличении разрыва между делимым и делителем.


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


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


ЗАКЛЮЧЕНИЕ


В рамках данной выпускной квалификационной работы были решены следующие задачи:

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

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

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

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

СПИСОК ЛИТЕРАТУРЫ

maple позиционный счисление деление

1. Акритас А. Основы компьютерной алгебры с приложениями. - М.: Мир, 1994. 544 с.

. Акушский И.Я., Юдицкий Д.М. Машинная арифметика в остаточных классах. - М.: Сов. радио, 1968. 440 с.

. Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. 168 с.

. Каган Б.М., Каневский М.М. Цифровые вычислительные машины и системы. - М.: Энергия, 1973.

. Копыткова Л.Б. Математические модели нейросетевой реализации модулярных вычислительных структур для высокоскоростной цифровой фильтрации: диссертация. - Ставрополь: СГУ, 2001, 264 с.

. Лобес М.В. Разработка методов и алгоритмов модулярных вычислений для задач большой алгоритмической сложности: диссертация. - Ставрополь: СГУ, 2009, 192 с.

. Макоха А.Н., Сахнюк П.А., Червяков Н.И. Дискретная математика: учебное пособие. - М.: ФИЗМАТЛИТ, 2005. 368 с.

. Фомин С.В. Популярные лекции по математике. Системы счисления. Выпуск 40 - М.: Наука, 1987. 48 с.

. Червяков Н. И., Лобес М. В. Алгоритм целочисленного деления в системе остаточных классов. - Инфокоммуникационные технологии, 2007. Том 5. №4. 8-13 с.

. Червяков Н.И., Сахнюк П.А., Шапошников А.В., Ряднов С.А. Модулярные параллельные вычислительные структуры нейропроцессорных систем. - М.: ФИЗМАТЛИТ, 2003. 288 с.

. Червяков Н.И. Применение системы остаточных классов в цифровых системах обработки и передачи информации. - Ставрополь: СВВИУС, 1985. 68 с.

. Чернова М.В., Сахнюк П.А. Методические рекомендации по выполнению дипломных работ для студентов специальности 010100 «Математика». - Ставрополь: Изд-во СГУ, 2011. 30 с.

. Шестаков А.П. Введение в информатику. Лабораторные работы. - Перм. ун-т: Пермь, 1999. Ч.I - 56 с.


ПРИЛОЖЕНИЕ


> restart:

> Prost:=array(1..10,[2,3,5,7,13,23,43,79,157,313]):

> #Ввод делимого А и делителя В:

> A:=36543268656;:=65555;

> #Выбор системы оснований:

> Modul:=array(1..10):

> P:=1::=0:i from 1 to 10 do(P<=A or P<=B) then:=P*Prost[i]:[i]:=Prost[i]::=n+1:if:do:

> #Перевод делителя В в СОК:

> Bs:=array(1..n):

> for i from 1 to n do[i]:=B mod Modul[i]:do:

> print(Bs);

> #Перевод делителя В в ОПСС:

> Bp:=array(1..n+1,1..n)::=array(1..n):

> for j from 1 to n do[1,j]:=Bs[j]:do:

> for i from 1 to n do[i]:=Bp[i,i]:j from 1 to n do(i<j) then[i+1,j]:=((Bp[i,j]-b[i])*((1/Modul[i]) mod Modul[j])) mod Modul[j][i+1,j]:=0if:do:do:

> print(b);

> #Определение приблизительного делителя:

> bpribl:=1:

Q:=n:

k:=1:

> while (b[Q]=0) do:=Q-1do:(b[Q]<Modul[1]) then:=Modul[1]:(bpribl=1) do(b[Q]>=Modul[k] and b[Q]<Modul[k+1]) then:=Modul[k+1]:=k+1if:do:if:i from (Q-1) to 1 by -1 do:=bpribl*Modul[i]:do:

> print(bpribl);

> #Деление методом Ферма:

> q:=1: aprom:=A: Ch:=0: i:=0:

> while (q<>0 and aprom<>0) do:=floor(aprom/bpribl)::=aprom::=aprom-B*q::=Ch+q::=i+1:do:

> if (q<>0 and aprom=0) then:=Ch+q:if:(q=0 and apromp>=B) then:=Ch+1:if:

> print(i);(Ch);


СОДЕРЖАНИЕ ВВЕДЕНИЕ АНАЛИТИЧЕСКИЙ ОБЗОР МЕТОД И АЛГОРИТМОВ ОБРАБОТКИ ЧИСЕЛ .1 Арифметические операции над числами, представленными в позиционных си

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ