5

Wikipedia says:

A residue numeral system (RNS) is a numeral system representing integers by their values modulo several pairwise coprime integers called the moduli.

Bit widths of each of those "several integers" will be much smaller than the width of the represented integer, allowing efficient addition/subtraction and multiplication, at the cost of complicated division and value comparison.

Here is a hypothetical example. Suppose that we want to represent 30-bit integers using residues. We pick several co-prime numbers - e.g. 1023, 1024, 1025, and represent value N as a triple [N mod 1023, N mod 1024, N mod 1025]. Note that the mod operation always results values of the same sign as the divisor.

In this particular case converting from N to residue triple and back is easy, as N mod 1024 is just 10 lowest bits of N, N mod 1023 is (N[29:20] + N[19:10] + N[9:0]) mod 1023 which is very easy to calculate, and N mod 1025 is, similarly, (N[29:20] - N[19:10] + N[9:0]) mod 1025, pretty much the same way as we mentally compute mod 9 and mod 11 of numbers expressed in decimal.

Then, adding or multiplying triples is done as adding or multiplying individual unsigned values mod 1023, 1024 or 1025 respectively. For addition, this requires shorter carry chains (10-deep) than would be used for 30-bit integers — or much smaller carry prediction trees, — and, for multiplication, just three 10x10 multipliers, one of them partial: we only need 10 lowest bits of the product to find out its mod 1024.

Converting a triple back to an integer is akin to solving a simple linear equation, reversing the way the triple was constructed.

Division would be much more complex, and less-than comparisons would be done by converting triples back to integers.

However, it could still be beneficial to use it for specialized computations, and there was a project of a Soviet military computer for the anti-ballistic missile system using a residue number system: 5Э53, apparently unimplemented; a computer with a conventional number representation was used instead.

Were there any computers using a residue number system which made it to production?

5

First RNS machine seemed to be tube-based EPOS (Elektronický Počítací Stroj) made around 1963 in Czechoslovakia.

The successor of that machine, EPOS-2, was transistorized and was built around 1973.

In USSR, there was Т340А machine, built also around 1962 and used for prototyping radar station machines. Later that machine turned into production К340А system, used for the same task.

Links:

EPOS-related (russian and czech):

General info regarding existing and only prototyped machines in USSR (russian only):

  • Thanks! Surprisingly, the Czech wikipedia article doesn't highlight the uniqueness of the architecture of EPOS 1. It says "modular structure". That's why when I'd found that article before asking the question, I dismissed the Russian version as wishful thinking. – Leo B. Feb 14 at 18:07
  • In fairness, the T340A/K340A systems are not true stored program computers but rather plugboard-programmable calculators. – Leo B. Feb 15 at 1:35

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.