Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!samsung!munnari.oz.au!murtoa.cs.mu.oz.au!ditmela!yarra!bohra!ejp
From: ejp@bohra.cpg.oz (Esmond Pitt)
Newsgroups: comp.arch
Subject: Re: Integer multiply and killer micros
Message-ID: <327@bohra.cpg.oz>
Date: 9 Jan 90 03:32:44 GMT
References: <158@csinc.UUCP> <787@stat.fsu.edu> <42701@lll-winken.LLNL.GOV> <5842@ncar.ucar.edu> <490@qusunl.queensu.CA> <sZcrr1G00hMNI3EF5i@cs.cmu.edu>
Reply-To: ejp@bohra.cpg.oz (Esmond Pitt)
Organization: Computer Power Group, Melb, Australia
Lines: 15

In article <sZcrr1G00hMNI3EF5i@cs.cmu.edu> Daniel.Stodolsky@cs.cmu.edu writes:
>
>If my memory serves me correctly,  one should be able to compute a 32 x
>32 -> 64 bit multiply with four 16x16 -> 32  multiplies, 4 32 bit adds
[unfortunate spelling error deleted]

Why use a quadratic algorithm?  It can be done with THREE
multiplications. See Knuth Vol II, #4.3.3.  In general two 2N-bit
numbers can be multiplied using N-bit precision in O(log(2N)), or
better for large N.


-- 
Esmond Pitt, Computer Power Group
ejp@bohra.cpg.oz