Post

The square root can be uniformly approximated to error ε by a rational function of degree O(log²(1/ε)). This surprising, since a polynomial approximation (e.g. Taylor series) requires degree Ω(1/ε), so rational functions are exponentially better than polynomials.

The proof uses the Poisson summation formula to show that an integral representation of the square root can be very well approximated by a discrete sum. bsky.app/profile/stei...

This approximation result was originally shown by Newman in 1964 (using a different construction and proof). Approximating the square root function on [0,1] is equivalent to approximating the absolute value function on [-1,1]. doi.org/10.1307/mmj/...

This result has been extended to other exponents (i.e. x^α for any α>0) and we have sharp constants: www.ams.org/journals/bul...

This approximation turns out to be useful for designing algorithms! Rational functions have Taylor series whose coefficients satisfy a linear recurrence. And we used that structure to make efficient streaming algorithms. Here's my paper, which appeared at FOCS 2024: arxiv.org/abs/2404.16706