Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!ames!oliveb!pyramid!prls!gert
From: gert@prls.UUCP (Gert Slavenburg)
Newsgroups: comp.arch
Subject: Re: Trachtenberg System of Math
Summary: There is a system for digit parallel add/multiply
Keywords: Residue Arithmetic
Message-ID: <16310@prls.UUCP>
Date: 27 Oct 88 16:16:04 GMT
References: <6232@june.cs.washington.edu> <6821@pasteur.Berkeley.EDU> <6245@june.cs.washington.edu>
Reply-To: gert@prls.UUCP (Gert Slavenburg)
Organization: Philips Research Labs, Sunnyvale, California
Lines: 30

The Trachtenberg system may not do what you are looking for, however, there is
a technique which is interesting, and has some of the desired properties.

The technique I am referring to is called 'Residue Arithmetic' or 'Chinese
Remaindering'. It is a technique which allows you to do integer addition, 
subtraction and multiplication as concurrent operations (independent on each 
'digit', without inter 'digit' carry). Note the quoted use of 'digit'.... The 
catch is that conversion from/to other codes is *very* computationally 
intensive, that digit arithmetic requires table lookup, and that magnitude
comparison, sign test and division are prohibitively expensive.

However, the arithmetic system can (and has been) used in signal processing
systems that only require multiplication, addition and subtraction and that
have many more internal computations than input/output conversions.

For those interested, a pointer to a list of pointers :

  F.J. Taylor, 'Residue Arithmetic : A tutorial with examples', IEEE Computer,
  May 1984, pp. 50..62.

Let's see some postings of architects that have built actual hardware based
on this method !

By the way, this number system was first described in a 3'rd century Chines
book. They must have been doing advanced research in signal processing :-) :-).

Disclaimer : I am *not* a specialist on this topic. I just looked at it once
as a potential method for doing additive music synthesis (where you only have
real-time computations and output, no input). Don't ask me to explain how it 
works - just read the article yourself.