На самом деле есть целая книга, посвященная (среди прочего) быстрым методам вычисления \ pi: 'Pi и AGM' Джонатаном и Питером Боровейном (доступно на Amazon).
Я немного изучил AGM и связанные с ним алгоритмы: это довольно интересно (хотя иногда нетривиально).
Обратите внимание, что для реализации большинства современных алгоритмов для вычисления \ pi вам понадобится библиотека точной арифметики (GMP - неплохой выбор, хотя с тех пор, как я последний раз его использовал, прошло довольно много времени).
Сложность по времени лучших алгоритмов находится в O (M (n) log (n)), где M (n) - сложность по времени для умножения двух n-битных целых чисел (M (n) = O (n log (n) log (log (n))) с использованием алгоритмов на основе FFT, которые обычно необходимы при вычислении цифр \ pi, и такой алгоритм реализован в GMP).
Обратите внимание, что хотя математика, лежащая в основе алгоритмов, может и не быть тривиальной, сами алгоритмы обычно представляют собой несколько строк псевдокода, и их реализация обычно очень проста (если вы решили не писать свою собственную арифметику мультиточности: - )).