FACTOID # 13: New York has America's lowest percentage of residents who are veterans.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Residue Number System

A residue number system (RNS) represents a large integer using a set of smaller integers, so that computation may be performed more efficiently. It relies on the Chinese Remainder Theorem of modular arithmetic for its operation, a mathematical idea from Sun Tsu Suan-Ching (Master Sun’s Arithmetic Manual) in the 4th century AD. Computation can be defined as finding a solution to a problem from given inputs by means of an algorithm. ... link titleThe Chinese remainder theorem (CRT) is the name for several related results in abstract algebra and number theory. ... Modular arithmetic is a system of arithmetic for integers, where numbers wrap around after they reach a certain value â€” the modulus. ...

## Defining a residue number system GA_googleFillSlot("encyclopedia_square");

A residue number system is defined by a set of N + 1 integer constants,

{m0, m1, m2, ... mN },

referred to as the moduli. The moduli must all be coprime; so in particular no modulus may be a factor of any other. Let M be the product of all the mi. Coprime - Wikipedia /**/ @import /skins-1. ...

Any arbitrary integer X smaller than M can be represented in the defined residue number system as a set of N + 1 smaller integers

{x0, x1, ... xN}

with

xi = X modulo mi

representing the residue class of X to that modulus. In computing, the modulo operation finds the remainder of division of one number by another. ...

The integer X can then be recovered from the set of the xi integers via the Chinese remainder theorem. link titleThe Chinese remainder theorem (CRT) is the name for several related results in abstract algebra and number theory. ...

## Operations on RNS numbers

Once represented in RNS, many arithmetic operations can be efficiently performed on the encoded integer. For the following operations, consider two integers, A and B, represented by ai and bi in an RNS system defined by mi (for i from 0 ≤ iN).

Addition can be accomplished by simply adding the small integer values together, modulo their specific moduli. For example, a sum can be computed by calculating a set of sumi values such that:

sumi = ( ai + bi ) % mi

Similarly, subtraction works the same way:

diffi = (ai - bi ) % mi

### Multiplication

Multiplication can be accomplished in a manner similar to addition and subtraction. To calculate PROD = A * B, we can calculate:

prodi = ( ai * bi ) % mi

### Division

Division in residue number systems is problematic. A paper describing one possible algorithm is available at [1]

In mathematics, a covering system is a collection of finitely many residue classes whose union covers all integers. ...

## Practical applications

RNS have applications in the field of digital computer arithmetic. By decomposing in this a large integer into a set of smaller integers, a large calculation can be performed as a series of smaller calculations that can be performed independently and in parallel. Because of this, it's particularly popular in hardware implementations. A digital system is one that uses numbers, especially binary numbers, for input, processing, transmission, storage, or display, rather than a continuous spectrum of values (an analog system) or non-numeric symbols such as letters or icons. ...

Results from FactBites:

 Hygiena - Products - Product List (1076 words) Designed with state-of-the-art electronics and improved functionality this palm-sized system is easy to use, extremely sensitive and affordable. The self-contained reagent turns from clear to green when food residue is present in a surface sample. QD-Loop is an all-in-one sterile system for accurate and convenient volumetric dilutions.
More results at FactBites »

Share your thoughts, questions and commentary here