Page 16 - Kotov

RNS-Based Computer
A residue number system (RNS) represents a large integer using a set of smaller integers, so that computation
may be performed more efficiently. A RNS is defined by a set of N integer constants, {m , m , m , ... , m }, re-
3
2
1
N
ferred to as the moduli. Let M be the least common multiple of all the m . Any arbitrary integer X smaller than
i
M can be represented in the defined residue number system as a set of N smaller integers {x , x , x , ... , x } with
2
N
1
3
x = X modulo m representing the residue class of X to that modulus.
i i
Israel Akushsky got the idea to build a RNS-based computer in 1954. By decomposing large integers into a set
of smaller integers, a large calculation can be performed as a series of smaller calculations that can be done in-
dependently and in parallel. Because of this, it can be particularly suitable for hardware implementations. The
use of RNS should increase the speed of certain operations and reduce the logic element count of the arithmetic
units. The RNS arithmetic would have the following speeds contrasted to a comparable conventional fixed-point
computer of reasonable range:

• Addition and subtraction - twice as fast
• Multiplication - ten times as fast
• Division - one-third as fast
• Sign determination - five to ten times slower

It took some time to persuade other people that the idea had merits. Finally, the project was approved and RNS
computers (Т-340А and К-340А ) were built and successfully used in the national air defense system. For the
first time in the USSR and in the world, K-340A has achieved performance of more than 1 million instructions
per second and reliability of the thousands of hours (a typical computer performance for those days was in the
tens of thousands) . More than 50 K-340As were built. Using RNS, Akushsky developed numerical methods for
super-large ranges of numbers, which consisted of hundreds of thousands of digits.

– 14 –