algorithm - tiene - Rápido algoritmo para calcular Pi en paralelo.

historia del pi

Question

Estoy empezando a aprender CUDA y creo que calcular dígitos largos de pi sería un proyecto agradable e introductorio.

Ya he implementado el método simple de Monte Carlo que se puede paralelizar fácilmente. Simplemente hago que cada hilo genere puntos al azar en el cuadrado de la unidad, averigüe cuántos se encuentran dentro del círculo de la unidad y cuente los resultados mediante una operación de reducción.

Pero ciertamente este no es el algoritmo más rápido para calcular la constante. Antes, cuando hice este ejercicio en una CPU de un solo hilo, usé fórmulas similares a las de Machin para hacer el cálculo para una convergencia mucho más rápida. Para aquellos interesados, esto implica expresar pi como la suma de los elementos y usar series de Taylor para evaluar la expresión.

Un ejemplo de tal fórmula:

Desafortunadamente, encontré que paralelizar esta técnica con miles de subprocesos de GPU no es fácil. El problema es que la mayoría de las operaciones simplemente hacen cálculos matemáticos de alta precisión en lugar de realizar operaciones de punto flotante en largos vectores de datos.

Así que me pregunto, ¿cuál es la forma más eficiente de calcular dígitos de pi arbitrariamente largos en una GPU?

Answer 1

Debes usar la fórmula Bailey – Borwein – Plouffe

¿Por qué? En primer lugar, necesita un algoritmo que se pueda desglosar. Entonces, lo primero que me vino a la mente es tener una representación de pi como una suma infinita. Luego, cada procesador solo calcula un término, y los sumas todos al final.

Entonces, es preferible que cada procesador manipule valores de precisión pequeña, en lugar de valores de muy alta precisión. Por ejemplo, si desea mil millones de decimales y usa algunas de las expresiones que se usan here , como el algoritmo de Chudnovsky , cada uno de sus procesadores necesitará manipular un número de mil millones de dólares. Eso simplemente no es el método apropiado para una GPU.

Así que, en general, la fórmula BBP le permitirá calcular los dígitos de pi por separado (el algoritmo es muy bueno), y con procesadores de "baja precisión". Lea el "algoritmo de extracción de dígitos BBP para π"

Ventajas del algoritmo BBP para calcular π Este algoritmo calcula π sin requerir tipos de datos personalizados con miles o incluso millones de dígitos . El método calcula el enésimo dígito sin calcular los primeros n - 1 dígitos, y puede usar tipos de datos pequeños y eficientes . El algoritmo es la forma más rápida de calcular el enésimo dígito (o unos pocos dígitos en una vecindad del enésimo), pero los algoritmos de computación π que usan tipos de datos grandes siguen siendo más rápidos cuando el objetivo es calcular todos los dígitos del 1 al n.