Быстрый алгоритм для вычисления Pi параллельно

Я начинаю изучать CUDA и думаю, что вычисление длинных цифр числа пи было бы хорошим вводным проектом.

Я уже реализовал простой метод Монте-Карло, который легко распараллелить. Я просто заставляю каждый поток случайным образом генерировать точки на единичном квадрате, выяснять, сколько из них лежит в пределах единичного круга, и подсчитывать результаты с помощью операции редукции.

Но это определенно не самый быстрый алгоритм вычисления константы. Раньше, когда я выполнял это упражнение на однопоточном процессоре, я использовал Machin-подобные формулыдля выполнения вычислений для гораздо более быстрой сходимости. Для тех, кто заинтересован, это включает в себя выражение пи в виде суммы арктангенсов и использование ряда Тейлора для вычисления выражения.

Пример такой формулы:

enter image description here

К сожалению, я обнаружил, что распараллелить эту технику для тысяч потоков графического процессора непросто. Проблема в том, что большинство операций просто выполняют высокоточные математические операции, а не выполняют операции с плавающей запятой над длинными векторами данных.

Итак, мне интересно, какой самый эффективный способ вычисления сколь угодно длинных цифр числа пи на графическом процессоре?

20
задан tskuzzy 5 June 2012 в 02:11
поделиться