import sys
from time import time
from itertools import count
import struct

# Python 2.x compatibility
if sys.hexversion < 0x3000000:
    def next(x):
        return x.next()
    from itertools import imap
else:
    imap = map
    xrange = range

__all__ = ('main', 'pi_digits', 'extract', 'compose', 'gen_x')

def info():
    print("Python " + sys.version)
    longbits = struct.calcsize('l') * 8
    print('CPU: %s bits, %s endian' % (longbits, sys.byteorder))

    int_info = getattr(sys, 'int_info', None)
    if int_info is None:
        base = 15
        sizeof_digit = struct.calcsize('h')
    else:
        base = int_info.bits_per_digit
        sizeof_digit = int_info.sizeof_digit
    info = "base=2^%s" % base
    if sizeof_digit:
        info += ', sizeof(digit)=%s bits' % (sizeof_digit * 8)
    print('PyLong: %s' % info)
    print('')

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():
    if len(sys.argv) != 2:
        print("usage: %s ndigits" % sys.argv[0])
        sys.exit(1)
    n = int(sys.argv[1])
    info()
    print('performing a warm up run...')
    pi_digits(n)
    print('running')
    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()