Path: utzoo!yunexus!geac!syntron!jtsv16!uunet!lll-winken!lll-tis!ames!nrl-cmf!mailrus!tut.cis.ohio-state.edu!bloom-beacon!spdcc!ima!johnl
From: johnl@ima.ima.isc.com (John R. Levine)
Newsgroups: comp.arch
Subject: Modular arithmetic, was Re: Trachtenberg System of Math
Keywords: Residue Arithmetic
Message-ID: <2817@ima.ima.isc.com>
Date: 27 Oct 88 22:32:22 GMT
Article-I.D.: ima.2817
References: <6232@june.cs.washington.edu> <6821@pasteur.Berkeley.EDU> <6245@june.cs.washington.edu> <16310@prls.UUCP>
Reply-To: johnl@ima.UUCP (John R. Levine)
Organization: Not much
Lines: 24

In article <16310@prls.UUCP> gert@prls.UUCP (Gert Slavenburg) writes:
>The technique I am referring to is called 'Residue Arithmetic' or 'Chinese
>Remaindering'. ...

Modular arithmetic is discussed at some length in Knuth's second volume,
"Seminumerical Algorithms" in sections 4.3.2 and 4.3.3.  He points out that
it can be a convenient way to represent large integers, particularly in
problems that involve exact rational answers to sets of linear equations.
Since you add, subtract, and multiply numbers by adding, subtracting, or
multiplying the sets of remainders component-wise without any sort of carry,
you can solve the equations independently for each component, then (slowly)
convert the components back into the large integers.  This is obviously
useful for parallel processors, and also handy for conventional machines
since the entries in the component arrays can be moderate sized integers
which are easier to manipulate in languages like Fortran than are multiple-
precision integers.

As noted elsewhere, the idea of modular arithmetic has been known for
centuries, and was proposed for computers in 1955.  Apparently there has
been a lot of discussion of hardware implementation but I've never seen
anything.  Reports from hardware designers are invited.
-- 
John R. Levine, IECC, PO Box 349, Cambridge MA 02238-0349, +1 617 492 3869
{ bbn | think | decvax | harvard | yale }!ima!johnl, Levine@YALE.something
Rome fell, Babylon fell, Scarsdale will have its turn.  -G. B. Shaw