快速算法并行计算Pi
我开始学习CUDA，我认为计算pi的长数字将是一个不错的介绍性项目。
我已经实现了易于并行化的简单蒙特卡洛方法。 我简单地让每个线程在单位正方形上随机生成点，找出单位圆内有多少个谎言，并使用简化操作来计算结果。
但这当然不是计算常数的最快算法。 之前，当我在一个单线程的CPU上完成这个练习时，我使用类Machin公式来计算更快的收敛。 对于那些感兴趣的人来说，这包括将pi表示为总和，并使用泰勒级数来评估表达式。
这样一个公式的例子：
不幸的是，我发现将这种技术并行化到数千个GPU线程并不容易。 问题是大多数操作只是在做高精度的数学运算，而不是在长向量数据上进行浮点运算。
所以我想知道， 在GPU上计算pi的任意长数字的最有效方法是什么？
你应该使用Bailey-Borwein-Plouffe公式
为什么？ 首先，你需要一个可以分解的算法。 所以，我想到的第一件事就是将pi的表示形式表示为无限的总和。 然后，每个处理器只计算一个术语，并且最后总结它们。
然后，每个处理器最好操纵小精度值，而不是非常高精度的值。 例如，如果你想要十亿小数，并且你使用了这里使用的一些表达式，比如Chudnovsky算法，那么你的每个处理器都需要操纵十亿长的数字。 这根本不是GPU的适当方法。
因此，总而言之，BBP公式将允许您分别计算pi的数字（算法非常酷），并使用“低精度”处理器！ 阅读“用于π的BBP数字提取算法”
用于计算π的BBP算法的优点该算法计算π 而不需要具有数千甚至数百万位的自定义数据类型 。 该方法计算第n位而不计算前n-1位，并且可以使用小而有效的数据类型 。 该算法是计算第n位数字（或第n位邻域中的几位数字）的最快方法，但是当目标是计算从1到n的所有数字时，使用大数据类型的π计算算法仍然更快。
链接地址: http://www.djcxy.com/p/12239.html