1# Source: https://github.com/python/pyperformance
2# License: MIT
3
4# Calculating some of the digits of π.
5# This benchmark stresses big integer arithmetic.
6# Adapted from code on: http://benchmarksgame.alioth.debian.org/
7
8
9def compose(a, b):
10    aq, ar, as_, at = a
11    bq, br, bs, bt = b
12    return (aq * bq, aq * br + ar * bt, as_ * bq + at * bs, as_ * br + at * bt)
13
14
15def extract(z, j):
16    q, r, s, t = z
17    return (q * j + r) // (s * j + t)
18
19
20def gen_pi_digits(n):
21    z = (1, 0, 0, 1)
22    k = 1
23    digs = []
24    for _ in range(n):
25        y = extract(z, 3)
26        while y != extract(z, 4):
27            z = compose(z, (k, 4 * k + 2, 0, 2 * k + 1))
28            k += 1
29            y = extract(z, 3)
30        z = compose((10, -10 * y, 0, 1), z)
31        digs.append(y)
32    return digs
33
34
35###########################################################################
36# Benchmark interface
37
38bm_params = {
39    (50, 25): (1, 35),
40    (100, 100): (1, 65),
41    (1000, 1000): (2, 250),
42    (5000, 1000): (3, 350),
43}
44
45
46def bm_setup(params):
47    state = None
48
49    def run():
50        nonlocal state
51        nloop, ndig = params
52        ndig = params[1]
53        for _ in range(nloop):
54            state = None  # free previous result
55            state = gen_pi_digits(ndig)
56
57    def result():
58        return params[0] * params[1], "".join(str(d) for d in state)
59
60    return run, result
61