🚀 go-pugleaf

[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