Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!uwm.edu!wuarchive!uunet!dg!Publius
From: Publius@dg.dg.com (Publius)
Newsgroups: comp.arch
Subject: Re: What about hardware implementations of optimized algorithms?
Message-ID: <889@dg.dg.com>
Date: 31 Aug 90 19:45:15 GMT
References: <4047@husc6.harvard.edu>
Reply-To: publius@dg-gw.dg.com (Publius)
Organization: Data General, Westboro, MA.
Lines: 33

In article <4047@husc6.harvard.edu> cleary@husc9.UUCP (Kenneth Cleary) writes:
>While I find discussions of hardware optimizations achieved through
>improvement of the electronic circuitry (such as GaAs, and higher-density
>VLSI) and design improvements like pipelining or instruction caching, I
>would like to hear about examples of optimized algorithms implemented as
>digital circuits.


I would second your call for the discussion in this area.


>	Donald E. Knuth, The Art of Computer Programming, 
>	vol.2, Seminumerical Algorithms
>	page 278, section 4.3.3. How Fast Can We Multiply?
>Knuth talks about getting faster multiplication than order-n**2 behavior.
>He describes some methods of getting behavior of n**(lg3) or n**1.585


There is an algorithm that can do even faster than O(n**1.585).
I don't have the reference in front of me now and I don't remember
the exact time complexity.  But it can be found in Aho, Ullman, and Hopcroft's
book on algorithms.  That algorithm is based on number-theoretic FFT.
It takes advantage of the similarity between multiplication and convolution in
signal processing and the fact that the classic Convolution Theorem can be
extended to the abstract algebraic structures.






-- 
Disclaimer: I speak (and write) only for myself, not my employer.