Module binary_splitting 

Binary-splitting engine for hypergeometric-like series.

This module implements the standard “binary splitting” divide-and-conquer algorithm for evaluating series of the form

S = Σ_{k=lo}^{hi-1} a(k) · P(lo) · P(lo+1) · … · P(k)
                         / (Q(lo) · Q(lo+1) · … · Q(k)
                            · B(lo) · B(lo+1) · … · B(k))

where P(k), Q(k), B(k), a(k) are integer-valued functions of k.

Algorithm

Each recursive call returns a BSSplit { p, q, b, t } struct where t / (q · b) equals the partial sum over [lo, hi). The combine step is:

p  = p_L · p_R
q  = q_L · q_R
b  = b_L · b_R
t  = t_L · q_R · b_R + t_R · p_L

This is O(M(n) log n) where M(n) is the cost of multiplying two n-digit integers (Karatsuba in this implementation).

Usage

Implement BSSeries for your series, then call binary_split:

struct MySeries;
impl BSSeries for MySeries {
    fn term(&self, k: u64) -> (BigInt, BigInt, BigInt, BigInt) {
        (BigInt::one(), BigInt::one(), BigInt::one(), BigInt::one())
    }
}
let split = binary_split(&MySeries, 0, 10);

Structs

BSSplit

Result of binary-splitting over a range [lo, hi).

Traits

BSSeries

Trait that defines the per-term factors of a binary-splittable series.

Functions

binary_split

Evaluate Σ_{k=lo}^{hi-1} using binary splitting.