Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
Suppose to calculate the continued fraction expansion of $\pi$, the common-sense algorithm would be to take the decimal part, perform inversion, which will give the next term as integer part, and the process is repeated for the decimal part.
However, this algorithm has the complexity of order $\mathcal O(n^2\log(n))$ assuming $\mathcal O(n \log n)$ multiplication. What would be an asymptotically faster algorithm?
I have not solved this exact problem, but a nearby problem is finding rational approximations to decimals (eg 0.333 => 1/3), for which I have used an algorithm called "mediant search". Under the hood, this search traverses an (implicit/infinite) data structure called the "Stern-Brocot tree", which is a novel way to enumerate every possible rational number in sorted order. If you look for those terms on Wikipedia, there appear to be similar Stern-Brocot based algorithms for finding continued fractions.
