On 11/28/2016 10:56 AM, Marc Feeley wrote:
Yes parallelizing Karatsuba multiplication should be very easy. That will make an interesting experiment when the multiple threaded VM configuration is stable. I expect very close to linear speedup given the independent sub-multiplications.
The Chudnovsky algorithm for $\pi$ is implemented using binary splitting of a series, and the independent sub-series can also be computed in parallel and then combined. This parallelism can be exploited even for not-so-large numbers of digits.
You get about 14 digits accuracy per term in the series, so for a billion digits you'd need about 70 million terms.
It'd be interesting to see how much overhead one incurs in distributing this computation to several processes. I imagine that processing 10,000 to 100,000 terms in a single process might be a good cutoff point, but we'd have to see.
Brad