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

 

 

Ш.А. Оцоков

 

 

(Москва, Московский энергетический институт (ТУ), Россия)

 

 

 

 

 

 

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

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

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

          Пусть множество входных данных (рациональные числа), с которыми проводятся арифметические операции:  сложений,  вычитаний,  умножений и М - модуль системы остаточных  классов [1,2].

          Справедливо следующее утверждение:         

 

 

          Утверждение 1.

 

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

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

и , тогда   искомый результат определяется  следующим образом:

 

         Доказательство: 

Пусть - дроби с которыми проводятся вычисления. Пусть требуется сложить  дробей, тогда искомый результат P/Q по определению равен:

Найдем

Рассмотрим 2 случая.

1.     случай. Если P/Q>0  и если B<M, то,  тогда

2.     случай. Если P/Q<0  и если B<M, то,  тогда

Аналогично можно доказать и другие арифметические операции.

Ч.т.д.

 

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

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

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

Суть данного метода  заключается в следующем:

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

Представим и в следующем виде:

Тогда  ,

,

Рассмотрим операцию сложения. Можно показать, что:

 

Операция вычитания аналогично сложению первого  числа   со вторым, но с противоположным знаком. 

Рассмотрим операцию умножения. Можно показать, что:

Рассмотрим операцию деления. Можно показать, что:

    Пример. Найти значение выражения.

Каждое число будем представлять в виде тройки (U,B,N).  Пусть модуль системы остаточных классов М=524269, 

Имеем:

1.     0.89+0.5=89/100 + 5/10=1,39 или (99612,100, 1) + (262135,10,1) = (361747,100,1)

2.     1,39-23,875=-22,485 или (361747,100,1)-(327692,1000,1)=(34055,1000,-1)

3.     -22,485+16=-6,485 или (34055,1000,-1) + (16,1,1) = (34071,1000,-1)

4.     -6,485*2,5=-16,2125 или (34071,1000,-1) * (262137,10)=(347312,10000,-1)

5.     -16,2125:5,095=-3,182041
или (347312,10000,-1): (128451,1000)= =-3,182041.

 

Разработанный метод позволяет существенно расширить диапазон представления рациональных чисел по сравнению с существующим в одномодульной системы остаточных классов [1].  

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

 

ЛИТЕРАТУРА

 

1.     Грегори Р, Кришнамурти Е. Безошибочные вычисления. Методы и приложения.М.:Мир,1988. –207 с.

2.     Дзегелёнок И.И, Оцоков Ш.А. Подход к решению проблемы безошибочных вычислений с использованием ускоренного алгоритма отображения дробей Фарея. // Труды научной конференции, посвященной 75-летию со дня рождения академика В.А.Мельникова. РАН. М. 2004.