Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!bloom-beacon!gatech!hubcap!howard
From: howard@cpocd2.UUCP (Howard A. Landman)
Newsgroups: comp.hypercube
Subject: Re: Fast parallel integer multiply?
Message-ID: <503@hubcap.UUCP>
Date: Thu, 24-Sep-87 13:09:11 EDT
Article-I.D.: hubcap.503
Posted: Thu Sep 24 13:09:11 1987
Date-Received: Sat, 26-Sep-87 17:00:47 EDT
Sender: fpst@hubcap.UUCP
Lines: 36
Approved: hypercube@hubcap.clemson.edu
Summary: Sure

[ This one was on sci.math.
  Steve
]

In article <67@rpicsb8] abbottj@csv.rpi.edu (John Abbott) writes:
>Are there any articles about how to multiply large integers quickly on
>parallel machines?

In article <13410@linus.UUCP>, bs@linus.UUCP (Robert D. Silverman) writes:
> If the numbers are say several THOUSAND computer words long (e.g. say 20000+
> decimal digits) then FFT techniques can be used and these parallelize well.
> Under that I'm afraid that the old-fashioned algorithms in Knuth which run
> in O(N^2) time (N = # bits) are inherently serial. Ditto for the recursive
> partitioning algorithms that say run in O(N^lg(3)) time.

In article <579@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes:
>If we have M^2 processors and M^2 memory available (M = # words, where
>multiplying 2 words to produce a double word is available) then the
>usual algorithm can be implemented in log M time.

Also, with only 2N bit-serial processors, linked in a linear arrary where
each processor can only communicate with its 2 nearest neighbors on each side,
we can multiply 2 N-bit numbers in O(N) time.  I forget who first observed
this, but Dick Lyon built such hardware while at Xerox PARC and described
it in his notes on digital signal processing, published internally by Xerox.
This has a better space-time product than Herman's "usual algorithm": O(N^2)
versus O(N^2*logN).

It would be fairly easy to implement this on a Connection machine for numbers
up to at least 32K bits, and possibly as high as 8M bits or more with clever
programming.  It doesn't do too much good to get faster than linear, because
input and output are still linear.
-- 
	Howard A. Landman
	...!{oliveb,...}!intelca!mipos3!cpocd2!howard
	howard%cpocd2%sc.intel.com@RELAY.CS.NET