Algorithm for Reverse Conversion from Hybrid Positional-Residue Number System

Algorithm for Reverse Conversion from Hybrid Positional-Residue Number System

Geryugova A.E. (NCFU, Stavropol, Russia)
Lutsenko V.V. (NCFU, Stavropol, Russia)
Sinitsyn A.A. (ISP RAS, Moscow, Russia)

Abstract

Modern high-performance computing systems require efficient methods for representing and processing numerical information. The residue number system provides a high level of parallelism in performing arithmetic operations; however, it is characterized by high computational complexity of reverse conversion to the positional number system, which limits its practical application. As a compromise approach, the hybrid positional-residue number system is considered, combining the advantages of positional and non-positional representations. In this paper, we propose a reverse conversion algorithm from the hybrid positional-residue number system to the positional number system, based on representing a number as a weighted sum of digits and utilizing a parallel computation structure interpreted as a linear neural network architecture over a finite ring. The proposed approach enables efficient implementation of the summation operation using parallel and pipelined data processing. A theoretical analysis of the computational complexity of the proposed algorithm is performed, and an experimental comparison with classical methods of reverse conversion from the residue number system to the positional number system is carried out. The obtained results show that the proposed method provides a significant reduction in execution time by reducing the number of operations on large-bit numbers and efficiently exploiting parallelism. The proposed approach can be used in the development of hardware and software solutions for problems in cryptography, digital signal processing, high-performance and high-precision computing.

Keywords

residue number system; hybrid positional-residue number system; high performance computing; reverse conversion.

Edition

Proceedings of the Institute for System Programming, vol. 38, issue 5, 2026, pp. 7-20

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

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

For citation

Geryugova A.E., Lutsenko V.V., Sinitsyn A.A. Algorithm for Reverse Conversion from Hybrid Positional-Residue Number System. Proceedings of the Institute for System Programming, vol. 38, issue 5, 2026, pp. 7-20 DOI: 10.15514/ISPRAS-2026-38(5)-1.

Full text of the paper in pdf Back to the contents of the volume