Folding the Plouffe-Bellard Digit-Extraction Scheme for $\pi$: A Legendre-Symbol Block Identity and an $O(n^{3/2})$ Variant

The algorithm of Plouffe and Bellard computes the digits of Pi at positions n+1,...,n+g in any base from the series Pi = 2 * Sum_{k>=0} k!/(2k+1)!! in O(n^2) operations on machine words and O(1) words of memory: for each of the pi(2N) primes q < 2N with N approx. n*log2(10) it runs a loop of length N. We prove that for every prime q with q^2 > 2N + q the sum of the contributions of all complete blocks k = j (mod q) collapses to the Legendre symbol (-1/q), by the identity Sum_{i=0}^{(q-1)/2} binomial(2i, i) * 2^(-i) = (-1)^((q-1)/2) (mod q). The loop of length N is replaced by a partial sum of at most min(L, h - L + 1) terms, where h = (q - 1)/2, and the total number of loop iterations drops from (2 + o(1)) * N^2 / ln N to at most (7/24 + o(1)) * N^2 / ln N, a reduction factor of at least 6.8. Each remaining partial sum is a prefix or suffix sum of a hypergeometric sequence modulo q; computing it with the baby-step giant-step method of Bostan, Gaudry and Schost takes O(sqrt(L) * log L) operations and gives a total complexity of O(n^3/2) operations. The proposed framework returns the correct digits in all verification cases; on benchmarks with n = 2000,...,32000 it is 4.2 to 18.7 times faster than the standard loop of the Plouffe-Bellard scheme on the same series, and the measured execution time of a single tail sum scales strictly like sqrt(L) up to L = 4.1 * 10^7. The complete source code, verification test suites, and benchmarks are made available.