Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!ames!ll-xn!mit-eddie!bloom-beacon!gatech!hao!noao!mcdsun!mcdchg!clyde!gwu
From: gwu@clyde.ATT.COM (George Wu)
Newsgroups: comp.arch
Subject: Re: Performance increase - a suggestion
Message-ID: <21246@clyde.ATT.COM>
Date: 3 Feb 88 17:31:55 GMT
References: <235@unicom.UUCP> <28200089@ccvaxa> <3127@phri.UUCP> <230@m2.mfci.UUCP>
Reply-To: gwu@clyde.UUCP (George Wu)
Organization: AT&T Bell Laboratories, Whippany NJ
Lines: 17
Keywords: fp fast multiplier
Summary: Use a matrix for fast multiplies.

Robert Colwell posted:

> If we're only discussing addition, subtraction, and multiplication,
> then I still don't believe it.  There's an adder at the heart of each
> of those, and its width decides its speed -- the wider, the slower
> (more levels of carry-lookahead).

     You can significantly reduce the time it takes to do a multiply by
using a faster algorithm. The bottleneck here is the carry-lookahead. A
matrix of carry-save adders eliminates this, giving you O(log2(n)) instead
of O(n). So the difference between 32 and 64 bits becomes trivial.

     Sorry I don't have more detail on the CSA matrix, but this is all
from a dim memory. If anyone wishes, *email* me a request, and I'll
provide more information after digging out my notes.

						George J Wu
						rutgers!clyde!gwu