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

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

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

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

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

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

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

Ответ 1

Вы должны использовать формулу Формула Бейли-Борвейн-Плуффе

Почему? Прежде всего, вам нужен алгоритм, который можно разбить. Итак, первое, что пришло мне в голову, - это представление pi как бесконечной суммы. Затем каждый процессор просто вычисляет один член, и вы суммируете их все в конце.

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

Итак, в целом формула BBP позволит вам вычислять цифры pi отдельно (алгоритм очень крут) и с процессорами с низкой точностью! Прочитайте "BB-разрядный алгоритм извлечения для π"

Преимущества алгоритма BBP для вычисления π Этот алгоритм вычисляет π , не требуя специальных типов данных, имеющих тысячи или даже миллионы цифр. Метод вычисляет n-ю цифру без вычисления первых n-1 цифр и может использовать небольшие эффективные типы данных. Алгоритм является самым быстрым способом вычисления n-й цифры (или нескольких цифр в окрестности n-го), но π-вычислительные алгоритмы с использованием больших типов данных остаются более быстрыми, когда целью является вычисление всех цифр от 1 до n.