Residual Computing

Residual computing is an approach to processor design built on the Residue Number System (RNS). RNS is a non-positional number system where integers are represented not as strings of digits in a fixed base, but as tuples of remainders after division by a set of coprime moduli. Where conventional computers propagate carries from bit to bit in every arithmetic operation, a residual processor computes on each remainder independently and in parallel, with no interaction between channels.

The idea originated in the Soviet Union in the 1950s under mathematician Israel Yakovlevich Akushsky, and reached production hardware in the K340A, the military computer at the heart of the Duga over-the-horizon radar.¹ But the architecture was always broader than one machine. The most complete public description of the technology (a 1978 patent by Akushsky and four co-inventors) lays out a general-purpose residual CPU capable of multiplication, division, shifting, overflow detection, and sign determination.² Everything a real processor needs, reimagined from first principles for a number system most Western engineers hadn't dreamed of using.

The number system

The Residue Number System represents any integer as a tuple of remainders after division by a set of pairwise coprime bases (called moduli). Pick bases p₁ = 7, p₂ = 9, p₃ = 11. The product P = 7 × 9 × 11 = 693, which defines the system's range: it can unambiguously represent any integer from 0 to 692.

The number 128 becomes (2, 2, 7) — because 128 mod 7 = 2, 128 mod 9 = 2, 128 mod 11 = 7.

The consequences are what matter. Addition and multiplication of two RNS numbers are trivially parallel: just add or multiply the corresponding residues independently, each modulo its own base. No carries propagate between channels. All digit positions compute simultaneously.

Take A = 264 = (5, 3, 0) and B = 377 = (6, 8, 3):

• γ₁ = 5 + 6 = 4 mod 7
• γ₂ = 3 + 8 = 2 mod 9
• γ₃ = 0 + 3 = 3 mod 11

Result S = (4, 2, 3) = 641. Correct.

Multiplication works the same way. A = 23 = (2, 5, 1) times B = 25 = (4, 7, 3):

• γ₁ = 2 × 4 = 1 mod 7
• γ₂ = 5 × 7 = 8 mod 9
• γ₃ = 1 × 3 = 3 mod 11

Result S = (1, 8, 3) = 575. Correct.

Division? That's where things get ugly.

The five hard problems

The strength of RNS, throwing away positional information in exchange for parallel, carry-free arithmetic, is also its fundamental weakness. Five operations that are trivial or straightforward in positional systems become challenging:

1. Multiplication of arbitrarily large numbers: when the product A × B exceeds the range P, the result wraps around and becomes meaningless. There's no obvious overflow signal in RNS.
2. Division: you can't divide residues directly. Division requires knowing the magnitude of numbers, and magnitude information is precisely what RNS throws away.
3. Overflow detection: determining whether a result exceeds the representable range requires comparing a number's value against P, which means recovering positional information from a non-positional representation.
4. Sign determination: negative numbers in RNS are represented as their complement relative to P. The number −5 in the (7, 9, 11) system looks like 688 = (2, 4, 6). There's no sign bit. Telling positive from negative requires knowing whether the value is in the upper or lower half of the range.
5. Shifting: binary shifts (multiply or divide by 2) are trivial in positional systems but require actual arithmetic in RNS, since there's no concept of "moving digits left or right."

An earlier Soviet processor (described in U.S.S.R. Inventor's Certificate No. 419,891 (1972)) could perform modular addition, subtraction, and basic multiplication, but couldn't multiply or divide arbitrary numbers, and its analysis circuit processed information sequentially through a technique called "nullivization," which considerably reduced operating speed.³ The architecture described in the 1978 patent solves all five problems.

Abridged multiplication

The most elegant technique in residual computing is abridged multiplication. When you multiply two numbers A and B that are both within the range P, their product A × B can be up to P², far exceeding the representable range. A conventional computer handles this by widening the result register. In RNS, you can't just add more residue channels on the fly.

The solution: instead of computing A × B, compute:

S' = A × B / P

This is the "abridged product." Since both A and B are less than P, S' is always less than P; it fits in the range. The full product can be recovered from S' and the remainder, but for many applications (signal processing, correlation) the abridged product is exactly what you want.

The technique decomposes further. The range limit P is factored into two parts: P = Pⱼ × Pₖ, chosen so that Pⱼ ≈ √P. The multiplicand A is split into a first part Aⱼ (residues corresponding to Pⱼ) and a second part Aₖ (residues corresponding to Pₖ), and similarly for multiplier B. Correction values "a" and "b" are introduced such that (A − a) is divisible by Pⱼ and (B − b) is divisible by Pₖ. This transforms the multiplication into:

A × B / P = (A−a)(B−b)/P + a×B̃/Pⱼ + b×Ã/Pₖ + a×b/P

where à = (A−a)/Pⱼ and B̃ = (B−b)/Pₖ. Since a×b/P < 1 (because a < Pⱼ and b < Pₖ), that last term vanishes in integer arithmetic, and the multiplication reduces to operations on half-range numbers; computable with the same hardware used twice.⁴ In hardware, it's implemented using two correction generators (one for each factor), two division units (for the Pⱼ and Pₖ divisions), a multiplication unit with six decoder units and twelve AND-gates, and a modulo adders unit that accumulates the partial results.

Iterative division

Division in RNS is implemented by a dedicated divider subsystem. The algorithm works by iteratively extracting partial quotients through repeated analysis of the dividend's residues. The process has four stages per iteration, operating by the first base p₁ of the number system and by two:

Stage One: The divisor B is analyzed starting from its first residue β₁. If β₁ = 0, then B is divisible by p₁, and division proceeds directly. If β₁ ≠ 0, the divisor B is divided by 2 iteratively (using a "halver" circuit) until the quotient Bₖ equals 1, at which point the system knows how many times to divide. Concurrently, the dividend A is divided by the same factor (p₁ or 2).

Stage Two: The product of the current partial result Aₖ × B is computed using the multiplier and product analysis units. A new dividend is formed: A' = A − Aₖ × B (subtraction) or A' = Aₖ × B − A + P (if the intermediate result would go negative).

Stage Three: Same as Stage One but applied to the new dividend A'.

Stage Four: The product Aₖ' × B is calculated, forming yet another new dividend.

Iterations continue until the partial quotient Aₖ reaches zero, at which point the accumulated quotient C = A/B is read from the adder as C = (C₁, C₂, ... Cₙ). Dedicated "end of iteration" and "end of division" comparison circuits watch for termination conditions.⁵

Division is inherently iterative in RNS; this means it's slow compared to addition and multiplication. But it works for arbitrary operands, which is more than earlier RNS processors could claim.

The position attribute

The most theoretically interesting concept in residual computing is the position attribute R; Akushsky's solution to the fundamental problem of RNS: you've thrown away all positional information, but you still need to know things like "is this number bigger than that one?" and "did we overflow?"

The position attribute R of a number A = (α₁, α₂, ... αₙ) is defined through a formula involving the mixed-radix representation; essentially, a partial reconstruction of positional information using the Chinese Remainder Theorem, but computed incrementally rather than all at once.

In hardware, a "position attribute generator" is built from groups of lookup-table decoders and modular adders. Each residue calculating unit takes input residue values and produces intermediate terms that are combined through the adder chain. The output R tells the system where in the range [0, P) the number falls; not its exact value, but enough to make comparison and overflow decisions.

This is a critical enabler for using RNS on real-world workloads. Without position attributes, RNS can perform modular addition, subtraction, and multiplication within range, but cannot detect overflow, determine sign, compare magnitudes, or terminate division; these are the non-modular operations that a real CPU requires.

Overflow and sign detection

The analysis system is a substantial piece of hardware: eleven AND-gates, an operation decoder, two OR-gates, a modulo-2 adder, and an analysis unit that determines sign and overflow for every operation. The system uses a parity-based approach. For each operand, a parity generator computes ψ(A) — essentially whether A is even or odd when viewed in positional terms. The parity of the sum ψ(A + B) is compared against the individual parities and the position attributes to determine:

• Sign (Zₛ): Whether the result is positive or negative. This is derived from the position attributes and the operation type. For multiplication and division, Zₛ follows the standard sign rules (positive × negative = negative). For addition, it depends on whether the magnitudes cause a sign flip.
• Overflow (Ω): Whether the result exceeds the range P (Ω = 1 for overflow, Ω = 0 for no overflow). In the division context, an intermediate parity check Π = (ψ(A') & ψ(B)) ⊕ ψ(A'·B), where ⊕ is modulo-2 addition (XOR) and & is logical AND, determines whether the product exceeds the range. The parity generators feed into the analysis system's modulo-2 adder to produce the overflow decision.⁶

The overflow attribute register stores this result after every operation. For addition and subtraction, overflow detection follows a different path that accounts for the signs of both operands; all four sign combinations and their overflow implications are explicitly handled.

Shifting in residue space

A left shift (multiply by 2) and right shift (divide by 2) sound, and largely are, trivial in binary. In RNS, they're more expensive arithmetic operations requiring a dedicated shifting subsystem. The shifting device takes the operand B, its position attribute R_B, and a control signal indicating shift direction. It comprises two shift units: the first for right shift (divide by 2), containing a parity generator and a division-by-two unit; and the second for left shift (multiply by 2), containing a position attribute generator, a comparison circuit, and a shift circuit with its own group of decoders.

For a right shift: B is divided by 2 using the residue-domain equivalent; each residue β_i is halved modulo p_i. The parity value ψ(B) determines whether B is even (clean division) or odd (rounded). For a left shift: B is multiplied by 2 in each residue channel. If 2B > P, an overflow signal is generated. This is what allows the processor to interface with the positional world; shifting is how you align operands, extract bit fields, and perform the scaling operations that workloads like signal processing demand.

The complete CPU architecture

Putting these subsystems together yields a complete residual processor:

• Operand registers: Store the two input numbers as residue tuples.
• Sign registers: Store signs separately (since RNS can't encode sign directly).
• Position attribute generators: Calculate the position attributes of the operands.
• Modular arithmetic unit: The core ALU — performs addition, subtraction, and multiplication within the RNS range, operating on each residue channel independently.
• Multiplier: The abridged multiplication subsystem with correction generators, division units, and multiplication unit.
• Divider: The iterative division subsystem with divisor analysis, halvers, end-of-iteration and end-of-division detection.
• Shifting device: Two shift units for left and right binary shifts.
• Analysis system: The sign/overflow determination engine with parity generators, position attribute generators, operation decoder, and logical unit.
• Result register and result sign register: Output storage.
• Overflow attribute register: Stores the overflow flag Ω.
• Control bus: Routes operation codes to all subsystems.

The operation cycle works as follows: operands and their signs are loaded into registers. Position attributes are generated simultaneously. A control signal selects the operation. For addition, subtraction, and multiplication (where the result stays within range P), the modular arithmetic unit computes the result directly. For abridged multiplication and division, the respective subsystems take over. In all cases the analysis system runs in parallel to determine the sign and overflow attribute of the result.

The architecture is modular; individual subsystems can be included or omitted based on the application, and each residue channel can be implemented as a separate physical unit, enabling what we'd now call a "channel-type processor" where reliability and speed increase with the number of parallel channels.

The patent

The most detailed public document describing this architecture is US Patent 4,121,298: "Central Processing Unit for Numbers Represented in the System of Residual Classes", granted October 17, 1978. The patent has 22 drawing figures across 16 sheets, and contains 25 claims covering the complete processor and every subsystem described above.⁷

The listed lead inventor was Akushsky himself. His co-inventors were Vladimir Mikhailovich Burtsev (Moscow), and three Alma-Ata-based scientists at the Institute of Mathematics and Mechanics of the Kazakh SSR Academy of Sciences: Bulat Esenovich Duisenov, Ivan Timofeevich Pak, and Anurbek Orymbekovich Zhautykov.⁸ The priority date was April 30, 1976, a decade after the K340A entered production, suggesting the patent represents refined thinking developed after the K340A had transferred to production.

The patent's prior art section cites U.S.S.R. Inventor's Certificate No. 419,891 (1972), related to U.S. Patent 3,602,704 (also by Akushsky, with Yuditsky), as the closest predecessor. The patent was filed internationally: US4121298A (US), GB1507121A (UK), FR2305783A1 (France), DE2619307 (West Germany, later withdrawn), and SU601689A1 (USSR). All are now expired. The 25 claims expired in 1995 (17 years from the 1978 grant date, under pre-1995 US patent law). The ideas they protected (abridged multiplication, position-attribute-based overflow detection, iterative residue division) are now in the public domain.

Significance

The K340A had already proven the basic concept of residual computing in production. What the 1978 patent documented was the refined architecture; the version that handled every edge case, every overflow condition, every sign combination. It was the textbook for a computing paradigm that the rest of the world mostly ignored as binary computing and IBM clones rapidly became the model for computing through the remainder of the century.