Алгоритм обратного преобразования из гибридной позиционно-остаточной системы счисления

Алгоритм обратного преобразования из гибридной позиционно-остаточной системы счисления

Герюгова А.Э. (СКФУ, Ставрополь, Россия)
Луценко В.В. (СКФУ, Ставрополь, Россия)
Синицын А.А. (ИСП РАН, Москва, Россия)

Аннотация

Современные высокопроизводительные вычислительные системы требуют эффективных методов представления и обработки числовой информации. Система остаточных классов обеспечивает высокий уровень параллелизма при выполнении арифметических операций, однако характеризуется высокой вычислительной сложностью обратного преобразования в позиционную систему счисления, что ограничивает её практическое применение. В качестве компромиссного подхода рассматривается гибридная позиционно-остаточная система счисления, сочетающая преимущества позиционных и непозиционных представлений. В работе предлагается алгоритм обратного преобразования из гибридной позиционно-остаточной системы счисления в позиционную систему счисления, основанный на представлении числа в виде взвешенной суммы разрядов и использовании параллельной структуры вычислений, интерпретируемой как линейная нейросетевая архитектура над конечным кольцом. Предложенный подход позволяет эффективно реализовать операцию суммирования с использованием параллельной и конвейерной обработки данных. Проведён теоретический анализ вычислительной сложности предложенного алгоритма, а также выполнено экспериментальное сравнение с классическими методами обратного преобразования из системы остаточных классов в позиционную систему счисления. Полученные результаты показывают, что предложенный метод обеспечивает значительное сокращение времени выполнения за счёт уменьшения количества операций над числами большой разрядности и эффективного использования параллелизма. Предложенный подход может быть использован при разработке аппаратных и программных решений для задач криптографии, цифровой обработки сигналов, высокопроизводительных и высокоточных вычислений.

Ключевые слова

система остаточных классов; гибридная позиционно-остаточная система счисления; высокопроизводительные вычисления; обратное преобразование.

Издание

Труды Института системного программирования РАН, том 38, вып. 5, 2026, стр. 7-20.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2026-38(5)-1

Для цитирования

Герюгова А.Э., Луценко В.В., Синицын А.А. Алгоритм обратного преобразования из гибридной позиционно-остаточной системы счисления. Труды Института системного программирования РАН, том 38, вып. 5, 2026, стр. 7-20. DOI: 10.15514/ISPRAS-2026-38(5)-1.

Полный текст статьи в формате pdf (на английском) Вернуться к содержанию тома