5
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.