Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uunet!ncrlnk!ncrcae!hubcap!pratt From: pratt@polya.Stanford.EDU (Vaughan R. Pratt) Newsgroups: comp.parallel Subject: Re: Parallel algorithms for integer multiplication: R.F.I. Message-ID: <7302@hubcap.clemson.edu> Date: 4 Dec 89 14:08:05 GMT Sender: fpst@hubcap.clemson.edu Lines: 30 Approved: parallel@hubcap.clemson.edu The best parallel algorithm for integer multiplication requires time O(log n) on n^3 processors (whence this problem is in NC). It is due to the Australian computer scientist Chris Wallace, who found it in 1964 or so while working in the US on the Illiac I. This gave rise to the so-called Wallace tree, for which one can buy an integrated circuit off the shelf any number of which can be connected together to form an O(log n) multiplier. Multiplication of a*b can be described as adding together up to n copies of a, one copy for each 1 bit of b, each copy shifted according to the position of that 1 bit. Forming these addends takes constant time with unbounded fanout, or log n with fanout 2. By balancing the n additions they can be carried out in parallel in time log n times the time for one addition. By using one of various carry-save schemes involving redundant representation (e.g. Avizienis notation, sum-carry representation, etc.) each addition can be performed in constant time. Conversion from the redundant form to binary at the end takes an additional log n; if sum-carry representation is used this simply amounts to adding the sum vector to the shifted carry vector as ordinary binary numbers. I don't know who first adapted Wallace's hardware method to SIMD parallel computation. An early paper doing so appears in STOC-74, the journal version of which is Pratt and Stockmeyer, "A Characterization of the Power of Vector Machines", JCSS, 12, 2, 1976, 198-221. Vaughan Pratt -- _______________________________________________________ Vaughan Pratt pratt@polya.stanford.edu 415-494-2545 ======================================================= Brought to you by Super Global Mega Corp .com