BC/NW 2022 № 1 (39):3.1

УСКОРЕНИЕ ВЫПОЛНЕНИЯ ОПЕРАЦИЙ НАД ЧИСЛАМИ БОЛЬШОЙ РАЗРЯДНОСТИ С ПОМОЩЬЮ СИСТЕМЫ ОСТАТОЧНЫХ КЛАССОВ

Новичков М.Д., Орлов Д.А.

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

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

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

В данной работе проводится сравнительный анализ методов и алгоритмов выполнения арифметических операций в СОК и позиционной системе счисления. В частности, рассматривается алгоритмы SRT и подобные методу Баррета для позиционной операции деления, а для деления в СОК выбран алгоритм, представленный в работе [3].

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

Литература

1. Маркова В.П. Применение модулярной арифметики для моделирования диффузии.  Автометрия, 2003, Т. 39, № 3, С. 60-71.

2. Червяков Н.И. О выборе диапазона системы остаточных классов для цифровой обработки изображений / Н.И. Червяков, П.А. Ляхов, Д.И. Калита // Инфокоммуникационные технологии. 2016. Т. 14. No2. С. 111-122.

3. Новичков М.Д. Исследование и разработка методов реализации операции деления в системе остаточных классов. Магистерская диссертация, Москва, 2019.