code optimization (calc PI) / Full Code of PI calc in Python and C.

[casevh at comcast.net]

Michael M. wrote:
> Ok, here is the code. It is a translation of the following code, found
> on the internet.
>
> * The C is very fast, Python not.
> * Target: Do optimization, that Python runs nearly like C.

There is an error in the translated code. It returns 1600 digits
instead of 800 digits.

>
> counter=c
> while 0<=counter+4000:
>    f.append(2000)  #   f.append( int(a/5) )
>    counter=counter-1
>    # b=b+1

This creates a list f with length 9601. It should have a length of
2801.

I found an explanation of the original C program at
http://rooster.stanford.edu/~ben/maths/pi/code.html

Using the variable names from the above explanation and editing the
code posted by bearophile to match the explanation, I have the
following:

from time import clock

def compute_pi():
    pi = []
    a = 10000
    i = k = b = d = c = 0
    k = 2800
    r = [2000] * 2801
    while k:
        d = 0
        i = k
        while True:
            d += r[i] * a
            b = 2 * i - 1
            r[i] = d % b
            d //= b
            i -= 1
            if i == 0: break
            d *= i
        k -= 14
        pi.append("%04d" % int(c + d // a))
        c = d % a
    return "".join(pi)

start_time = clock()
pi = compute_pi()
print pi
print "Total time elapsed:", round(clock() - start_time, 2), "s"
print len(pi)

You're original version takes 2.8 seconds on my computer. The above
version takes .36 seconds. I tried a couple of optimizations but
couldn't make any more improvements.

casevh