2018 г., Том 23, № 3, с.39-57

Рассмотрены два алгоритма масштабирования чисел в системе остаточных классов (СОК). В этих алгоритмах использована новая процедура определения остатка от деления масштабируемого числа X на коэффициент K , основанная на интервальной оценке относительной величины числа в СОК. Первый алгоритм эффективен для коэффициентов в пределах разрядной сетки компьютера. Второй алгоритм является обобщением первого для быстрого масштабирования степенью двойки в СОК. Он позволяет без реинициализации системы в качестве коэффициента масштабирования использовать любое число K = 2 D в диапазоне от 2 до M - 1, где M - произведение всех модулей. В процессе вычислений требуются только стандартные операции с плавающей точкой и целочисленные модулярные операции. Оба алгоритма позволяют эффективно использовать параллелизм СОК. Представлены CPU- и CUDA-реализации разработанных алгоритмов и рассмотрены их особенности. Эксперименты на CPU Intel Xeon X5650 и GPU NVIDIA Tesla M2050 показали, что предложенные алгоритмы обладают высоким быстродействием по сравнению с известными алгоритмами масштабирования, основанными на преобразовании в двоичную систему счисления и контроле четности.