ОБ ОДНОМ АЛГОРИТМЕ СРАВНЕНИЯ ЧИСЕЛ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ

Модулярная арифметика (представление чисел в системах остаточных классов) обладает внутренним параллелизмом данных и поэтому является перспективным инструментом эффективной организации высокоточных вычислений. Однако из-за высокой сложности немодульных операций, таких как сравнение, вычисление знака, контроль переполнения динамического диапазона, масштабирование и деление, сфера эффективного применения модулярной обработки ограничена достаточно узким классом специфических задач. Рассмотрены способы оценки позиционной величины чисел в модулярном представлении. Приведена новая интервально-позиционная характеристика модулярной арифметики, обеспечивающая получение достоверной аппроксимации относительной величины числа за O(n) операций с плавающей точкой в последовательном случае и за O(log n) операций при использовании параллельного алгоритма, где n – количество модулей системы остаточных классов. Разработан новый алгоритм сравнения чисел в системе остаточных классов на основе вычисления и анализа интервально-позиционных характеристик. Предложенный алгоритм не требует хранения в памяти подстановочных таблиц больших размеров, обеспечивает корректность результата сравнения и отличается высоким быстродействием. Выполненный анализ вычислительной сложности показывает, что, в зависимости от сочетания входных данных, ускорение предлагаемого алгоритма может достигать 0,18n раз по сравнению с аналогичным алгоритмом на основе преобразования модулярных чисел в систему счисления со смешанными основаниями. Обсуждаются вопросы точности вычисления интервально-позиционной характеристики. Рассмотрен новый быстрый алгоритм, позволяющий в условиях ограниченной разрядности машинной арифметики вычислить интервально-позиционную характеристику с относительной погрешностью, не превышающей априорно заданного предела Сформулированы рекомендации по практическому применению полученных результатов.

• Исупов К.С.

• Общий отдел

• Технические науки. Промышленность
• Физико-математические науки
• Социальные (общественные) науки