A Fast Self-correcting π Algorithm

2019/12/10 by Sze, Tsz-Wo
#11Y16 (Primary) 68Q25 (Secondary) #11Y60 #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Symbolic Computation (cs.SC)

paper · doi:10.48550/arxiv.1912.05319

Abstract

We have rediscovered a simple algorithm to compute the mathematical constant π=3.14159265⋯. The algorithm had been known for a long time but it might not be recognized as a fast, practical algorithm. The time complexity of it can be proved to be O(M(n)log² n) bit operations for computing π with error O(2^-n), where M(n) is the time complexity to multiply two n-bit integers. We conjecture that the algorithm actually runs in O(M(n)log n). The algorithm is self-correcting in the sense that, given an approximated value of π as an input, it can compute a more accurate approximation of π with cubic convergence.

Related

• The combinatorial algorithm for computing pi(x)
• On the computation of the n^th decimal digit of various transcendental numbers
• Easy Proofs of Some Borwein Algorithms for π
• Another (wrong) construction of π
• Distant decimals of π