5 ms·
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 one
by praptak 8y ago
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.
- bluedonuts 8y agoI wondered the same, according to the site its not possible to parallelize: http://www.numberworld.org/y-cruncher/faq.html#distributed http://www.numberworld.org/y-cruncher/faq.html#distributed The nth digit type computations are too slow.
- FavouriteColour 8y ago“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.”