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

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

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

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

(2.7)

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

(2.8)

(2.9)

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

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

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

Пусть , тогда

(2.10)

где

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

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

(2.11)

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

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

 (2.12)

(2.13)

где

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

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

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

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

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

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

(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 действия, которые и будут являться основными шагами алгоритма соответствующей программы:

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

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

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

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

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

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

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

Таблица 2.5

	Делимое
Делитель
		8	15	21	28	35	41	48
		1	6	10	14	18	22	27
		1	1	5	9	12	16	19
		1	1	1	6	9	13	17
		1	1	1	1	4	6	9
		1	1	1	1	1	7	12
		1	1	1	1	1	1	6

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПРИЛОЖЕНИЕ

> restart:

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

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

> A:=36543268656;

B:=65555;

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

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

> P:=1:

n:=0:

for i from 1 to 10 do

if (P<=A or P<=B) then

P:=P*Prost[i]:

Modul[i]:=Prost[i]:

n:=n+1:

end if:

end do:

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

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

> for i from 1 to n do

Bs[i]:=B mod Modul[i]:

end do:

> print(Bs);

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

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

b:=array(1..n):

> for j from 1 to n do

Bp[1,j]:=Bs[j]:

end do:

> for i from 1 to n do

b[i]:=Bp[i,i]:

for j from 1 to n do

if (i<j) then

Bp[i+1,j]:=((Bp[i,j]-b[i])*((1/Modul[i]) mod Modul[j])) mod Modul[j]

else

Bp[i+1,j]:=0

end if:

end do:

end do:

> print(b);

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

> bpribl:=1:

Q:=n:

k:=1:

> while (b[Q]=0) do

Q:=Q-1

end do:

if (b[Q]<Modul[1]) then

bpribl:=Modul[1]:

else

while (bpribl=1) do

if (b[Q]>=Modul[k] and b[Q]<Modul[k+1]) then

bpribl:=Modul[k+1]

else

k:=k+1

end if:

end do:

end if:

for i from (Q-1) to 1 by -1 do

bpribl:=bpribl*Modul[i]:

end do:

> print(bpribl);

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

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

> while (q<>0 and aprom<>0) do

q:=floor(aprom/bpribl):

apromp:=aprom:

aprom:=aprom-B*q:

Ch:=Ch+q:

i:=i+1:

end do:

> if (q<>0 and aprom=0) then

Ch:=Ch+q:

end if:

if (q=0 and apromp>=B) then

Ch:=Ch+1:

end if:

> print(i);

print(Ch);

Размещено на Allbest.ru