Faster PI Computation

In [here], two equations are used and compare the efficiency of computation of the math constant . The following are some commonly-used equations to compute the

We pick the third one and multiple by two on both sides of the equations.

And, similar to [here], we use the following Python script to see how this equation converges.

#!/usr/bin/env python
# https://helloacm.com

from math import *

EPSILON = 0.001
step = 0
ans = 2
z = 2
a = 1.0
b = 3

while 1:
    z = z * a / b
    ans += z
    a += 1
    b += 2
    step += 1
    if abs(pi - ans) <= EPSILON:
        break
    print step, ans, abs(pi - ans)

This gives the quickest convergence among the three.

1 2.66666666667 0.474925986923
2 2.93333333333 0.208259320256
3 3.04761904762 0.0939736059707
4 3.09841269841 0.0431799551771
5 3.1215007215 0.0200919320891
6 3.13215673216 0.00943592143306
7 3.13712953713 0.00446311646026
8 3.13946968065 0.00212297294364
9 3.14057816968 0.00101448390946

Only 9 iterations are required to reach a accuracy of 0.001. We use builtin native types (precision of double), the accuracy is limited. We can use arrays to hold the results with a higher number of digits. We can stimulate the process of computation. The following is a Python script that uses arrays (long arithmetic) to compute the . The 1000 digits can be easily obtained.

#!/usr/bin/env python
# https://helloacm.com

def compute(len):
    x = [0] * len
    z = [0] * len
    x[1] = z[1] = 2
    a = 1; b = 3
    while True:
        # z *= a
        d = 0
        j = len - 1
        while j > 0:
            c = z[j] * a + d
            z[j] = c % 10
            d = c / 10
            j -= 1
        # z /= b
        d = 0
        for j in xrange(len):
            c = z[j] + d * 10
            z[j] = c / b
            d = c % b
        # x += z
        run = 0
        j = len - 1
        while j > 0:
            c = x[j] + z[j]
            x[j] = c % 10
            x[j - 1] += c / 10
            run |= z[j]
            j -= 1
        if not run:
            break
        a += 1
        b += 2
    return "".join(map(str, x))

if __name__ == "__main__":
    print compute(1000)

0314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196442881097566593344612847564823378678316527120190914564856692346034861045432664821339360726024914127372458700660631558817488152092096282925409171536436789259036001133053054882046652138414695194151160943305727036575959195309218611738193261179310511854807446237996274956735188575272489122793818301194912983367336244065664308602139494639522473719070217986094370277053921717629317675238467481846766940513200056812714526356082778577134275778960917363717872146844090122495343014654958537105079227968925892354201995611212902196086403441815981362977477130996051870721134999999837297804995105973173281609631859502445945534690830264252230825334468503526193118817101000313783875288658753320838142061717766914730359825349042875546873115956286388235378759375195778185778053217122680661300192787661119590921638728

–EOF (The Ultimate Computing & Technology Blog) —