Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!hao!gatech!hubcap!fpst
From: fpst@hubcap.clemson.edu
Newsgroups: comp.hypercube
Subject: Re: Fast parallel integer multiply?
Message-ID: <472@hubcap.UUCP>
Date: Fri, 18-Sep-87 08:12:43 EDT
Article-I.D.: hubcap.472
Posted: Fri Sep 18 08:12:43 1987
Date-Received: Sun, 20-Sep-87 01:59:20 EDT
Sender: fpst@hubcap.UUCP
Lines: 15
Approved: hypercube@hubcap.clemson.edu
Summary: FFT ok for BIG numbers

[This response to the question of integer multiply was on sci.math]

From: bs@linus.UUCP (Robert D. Silverman)
]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?

The basic question is: How Large? 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.

Bob Silverman