Re: Fast parallel integer multiply?

Thread View: comp.hypercube

1 messages

[T] Back to Threads [V] Tree View [G] Group Articles

1 total messages Started by fpst Fri, 18 Sep 1987 12:12

#65

Author: fpst
Date: Fri, 18 Sep 1987 12:12

15 lines
1192 bytes

[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

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads