Об одном алгоритме сравнения чисел в системе остаточных классов

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