Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!ames!ncar!tank!nic.MR.NET!shamash!nis!ems!srcsip!shankar
From: shankar@src.honeywell.COM (Subash Shankar)
Newsgroups: comp.arch
Subject: Re: Modular arithmetic, was Re: Trachtenberg System of Math
Keywords: Residue Arithmetic
Message-ID: <11010@srcsip.UUCP>
Date: 28 Oct 88 18:47:59 GMT
References: <6232@june.cs.washington.edu> <6821@pasteur.Berkeley.EDU> <6245@june.cs.washington.edu> <16310@prls.UUCP> <2817@ima.ima.isc.com>
Reply-To: shankar@haarlem.UUCP (Subash Shankar)
Organization: Honeywell Systems & Research Center, Camden, MN
Lines: 23

In article <2817@ima.ima.isc.com> johnl@ima.UUCP (John R. Levine) writes:
>In article <16310@prls.UUCP> gert@prls.UUCP (Gert Slavenburg) writes:
>>The technique I am referring to is called 'Residue Arithmetic' or 'Chinese
>>Remaindering'. ...
>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.

Residue arithmetic representations store a number by modding it with a
set of predefined radices (relatively prime).

I thought one of the problems with residual arithmetic is that overflow
detection isn't possible.  For example, assuming you use radix 2,3, and 5.
If x1=4, x2=19, y=2, they would be represented as
  x1   (0,1,4)
  x2   (1,1,4)
  y    (0,2,2)
Multiplying x1 and y results in (0,2,3) = 8
Multiplying x2 and y results in (0,2,3) = 8 + 2*3*5 = 38 should be overflow.
Overflow detection is difficult (impossible?) since you can't tell the
magnitude of a number by observing any of its "digits".  Anybody out there
know if this is correct, or has this problem been solved?