Article View: comp.arch
Article #21998Re: Integer multiply and killer micros
From: Esmond Pitt
Date: Tue, 09 Jan 1990 03:32
Date: Tue, 09 Jan 1990 03:32
15 lines
1109 bytes
1109 bytes
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
Technical Details
Message-ID:
<327@bohra.cpg.oz>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!samsung!munnari.oz.au!murtoa.cs.mu.oz.au!ditmela!yarra!bohra!ejpReferences:
<158@csinc.UUCP> <787@stat.fsu.edu> <42701@lll-winken.LLNL.GOV> <5842@ncar.ucar.edu> <490@qusunl.queensu.CA> <sZcrr1G00hMNI3EF5i@cs.cmu.edu>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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