Аннотация:
Операция сравнения чисел широко используется при реализации большинства современных алгоритмов. Реализация алгоритма сравнения чисел в системе остаточных классов (СОК) состоит из двух этапов. Первый этап — вычисление позиционной характеристики модулярного числа. Второй этап — сравнение позиционных характеристик модулярных чисел в позиционной системе счисления. В статье предлагается новый эффективный алгоритм вычисления позиционной характеристики числа в СОК, основанный на использовании приближенного метода. Использование этого метода не требует дорогостоящих модульных операций, которые заменяются быстрыми битовыми операциями сдвиг вправо и взятия младших бит. Доказано, что в случае, когда динамический диапазон СОК является нечетным числом, размер операндов уменьшается на размер модуля. Если одно из оснований СОК является степенью двойки, то размер операндов меньше динамического диапазона.
Работа выполнена при поддержке стипендии Президента РФ молодым ученым и аспирантам, МК-341.2019.9, СП-2236.2018.5, а также грантов РФФИ 18-07-01224, 18-07-00109.
Реферативные базы данных:
Тип публикации:
Статья
Образец цитирования:
М. Г. Бабенко, А. Н. Черных, Н. И. Червяков, В. А. Кучуков, В. Миранда-Лопес, Р. Ривера-Родригес, Чж. Ду, “Эффективное сравнение чисел в системе остаточных классов на основе позиционной характеристики”, Труды ИСП РАН, 31:2 (2019), 187–202
\RBibitem{BabTchChe19}
\by М.~Г.~Бабенко, А.~Н.~Черных, Н.~И.~Червяков, В.~А.~Кучуков, В.~Миранда-Лопес, Р.~Ривера-Родригес, Чж.~Ду
\paper Эффективное сравнение чисел в системе остаточных классов на основе позиционной характеристики
\jour Труды ИСП РАН
\yr 2019
\vol 31
\issue 2
\pages 187--202
\mathnet{http://mi.mathnet.ru/tisp417}
\crossref{https://doi.org/10.15514/ISPRAS-2019-31(2)-13}
\elib{https://elibrary.ru/item.asp?id=38469696}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/tisp417
https://www.mathnet.ru/rus/tisp/v31/i2/p187
Эта публикация цитируется в следующих 5 статьяx:
Andrei Tchernykh, Mikhail Babenko, Egor Shiriaev, Bernardo Pulido-Gaytan, Jorge M. Cortés-Mendoza, Arutyun Avetisyan, Alexander Yu Drozdov, Viktor Kuchukov, “An Efficient Method for Comparing Numbers and Determining the Sign of a Number in RNS for Even Ranges”, Computation, 10:2 (2022), 17
М. Сафьян, С. Сарвар, З. У. Кайюм, М. Икбал, С. Ли, М. Кашиф, “Изучение видов деятельности на основе машинного обучения в поведенческих контекстах Интернета вещей”, Труды ИСП РАН, 33:1 (2021), 47–58
А. С. Коржавина, В. С. Князьков, “Реализация высокоточных вычислений в базисе
модулярно-интервальной арифметики”, Программные системы: теория и приложения, 10:3 (2019), 81–127
Mikhail Babenko, Maxim Deryabin, Andrei Tchernykh, 2019 International Conference on Engineering and Telecommunication (EnT), 2019, 1
Viktor Kuchukov, Mikhail Babenko, 2019 Ivannikov Ispras Open Conference (ISPRAS), 2019, 49
Цитирование в формате AMSBIB
Обратная связь: