Исупов К. С. 4(2017)

УДК 004

К. С. Исупов, А. А. Завиялов

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

В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ*

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

       Ключевые слова: система остаточных классов, ранг числа, алгоритмы, эффективность.