Binary Splitting

Recursive algorithm:

S_{[n_{1},n_{2})} = ∑_{n=n_{1}}^{n_{2}−1} \frac{a(n)}{b(n)} \frac{p(n_{1}) ⋯ p(n)}{q(n_{1}) ⋯ q(n)}

Compute P = p(n_{1}) ⋯ p(n_{2} − 1), Q = q(n_{1}) ⋯ q(n_{2} − 1), B = b(n_{1}) ⋯ b(n_{2} − 1) and T with

S_{[n_{1},n_{2})} = \frac{T}{B · Q}

n_{2} − n_{1} < 4 → directly n_{2} − n_{1} ≥ 4 → split

P = P_{L} · P_{R}
Q = Q_{L} · Q_{R}
B = B_{L} · B_{R}

T = B_{R} · Q_{R} · T_{L} + B_{L} · P_{L} · T_{R}