Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uunet!ncrlnk!ncrcae!hubcap!tillamook!mohamed From: tillamook!mohamed@uunet.UU.NET (Moataz Mohamed) Newsgroups: comp.parallel Subject: Re: Parallel algorithms for integer multiplication: R.F.I. Message-ID: <7303@hubcap.clemson.edu> Date: 4 Dec 89 14:08:07 GMT Sender: fpst@hubcap.clemson.edu Lines: 36 Approved: parallel@hubcap.clemson.edu fagin@eleazar.dartmouth.edu (Barry S. Fagin) writes: >Anyone out there know the best parallel algorithm for large >integer multiplication, and where I could find a reference >for it? Shinji Nakamura "Algorithms for iterative array multiplication", IEEE Transaction of Computers, Aug 1986. The above paper presents iterative array (systolic) parallel algorithms for integer multiplication. One of the algorithms persented employs folding to reduce the carry delay to "n". However, if you are interested in building a chip, I would encourage you to think twice before doing it. I actually designed and implemented (layout and simulations) a chip for the algorithm. The problems arise from the fact that the folded array is triangular which creates lots of layout problems and thus the delays encoutered due to long wires actually exceed the predicted theoretical result. >--Barry Fagin >(barry.fagin@dartmouth.edu, ...!dartmouth!eleazar!fagin .. Moataz Mohamed mohamed@cs.uoregon.edu CIS Dept. Univ. of Oregon Eugene, OR 97403 ============================================================================= "People do different things out of the same motives, yet they sometimes do the same things for dramatically different reasons" --Nobody you know! ============================================================================= Brought to you by Super Global Mega Corp .com