That will be a perfect use case for the multiple-threaded VM. Can you write a parallel version of the algorithm, using thread-start! and thread-join! to manage the parallelism? You can test it on a single-threaded VM and then I can give it a try here on a 64 processor machine.
Marc
On Dec 9, 2016, at 11:21 AM, Bradley Lucier lucier@math.purdue.edu wrote:
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