Там на самом деле целая книга, посвященная (среди прочего) для быстрых методов для вычисления \ пи: «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).
Обратите внимание, что хотя математика, лежащая в основе алгоритмов, не может быть тривиальной, сами алгоритмы обычно представляют собой несколько строк псевдокода, и их реализация обычно очень проста (если вы решили не писать свою собственную арифметику multiprecision: -)).
Что это касается моего вопроса ??????? – Jack 2014-10-17 05:26:49