import sys
from time import time
from itertools import *
__all__ = ('main', 'pi_digits', 'extract', 'compose', 'gen_x')

try:
    imap
    xrange
except NameError:
    imap = map
    xrange = range

def gen_x():
    return imap(lambda k: (k, 4*k + 2, 0, 2*k + 1), count(1))

def compose(a, b):
    aq, ar, as_, at = a
    bq, br, bs, bt = b
    return (aq * bq,
            aq * br + ar * bt,
            as_ * bq + at * bs,
            as_ * br + at * bt)

def extract(z, j):
    q, r, s, t = z
    return (q*j + r) // (s*j + t)

def pi_digits(nb_digit):
    z = (1, 0, 0, 1)
    x = gen_x()
    for count in xrange(nb_digit):
        y = extract(z, 3)
        while y != extract(z, 4):
            z = compose(z, next(x))
            y = extract(z, 3)
        z = compose((10, -10*y, 0, 1), z)

def main():
    n = int(sys.argv[1])
    print('performing a warm up run...')
    pi_digits(n)
    print('running')
    print('sys.int_info=', getattr(sys, 'int_info', None))
    best = None
    for _ in range(5):
      start = time()
      pi_digits(n)
      bench = time() - start
      if best is None or bench < best:
          best = bench
      print("Time; %.1f ms" % (bench*1000))
    print("Best Time; %.1f ms" % (best*1000))

if __name__ == '__main__':
    main()