The fast self-correcting algorithm conjecture for computing π

Let M(n)M(n) denote the time complexity of multiplying two nn-bit integers. The self-correcting algorithm described in the paper computes pipi with error O(2n)O(2^{-n}).

Fast self-correcting pipi algorithm conjecture. Algorithm~ runs in O(M(n)logn)O(M(n)\log n) bit operations.

The algorithm is already proved to run in O(M(n)log2n)O(M(n)\log^2 n) bit operations and is self-correcting, producing a more accurate approximation from an approximate input with cubic convergence. The conjecture asserts the sharper complexity matching the known asymptotically fastest algorithms for computing pipi; no resolution is supplied in the source.

Sources & referencesView supporting material

Primary source

Tsz-Wo Sze, “A Fast Self-correcting π Algorithm”, arXiv:1912.05319 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.