Hacker News Reader

Does parallelization work on this problem? I vaguely remember you can compute nth digit of Pi (not sure in what bases though) without computing the previous ones but this doesn't mean that an efficient parallel algorithm exists.

View on HN

I wondered the same, according to the site its not possible to parallelize:

http://www.numberworld.org/y-cruncher/faq.html#distributed

The nth digit type computations are too slow.

“There exist algorithms like BBP to directly compute arbitrary binary digits without the memory cost of computing all the digits before it. These are called "digit-extraction" algorithms. However, these algorithms require roughly O(N*log(N)) time to compute a small number of digits at offset N. Using this approach to compute all the digits from 1 to N will result in a quadratic run-time algorithm. This alone makes it unsuitable for large N.”

Reply on news.ycombinator.com