Let $x \in [0, 1]$ be irrational and let $$x = \cfrac1{a_1 + \cfrac1{a_2 + \cfrac1{a_3 + \frac1\ddots}}}$$ be the regular continued fraction expansion of $x$. If you truncate the continued fraction expansion at $n$ you get the $n$th convergent $A_n/B_n$ to $x$.

Let $R_x(n) = x - A_n/B_n$. I know that $$R_x(n) \leq \frac1{B_n B_{n+1}}$$ For $\phi = \frac{\sqrt{5} - 1}{2}$ we have that $R_\phi(n) = O(\phi^{2n})$ and this holds for any $x$ so it is the worst-case approximation to the $R_x$.

Are there any such approximation for the "average-case"?

EDIT: I don't have a rigorous definition of "average-case". But I would be interested in approximations that work for almost all $x$, for example.


Lochs' Theorem implies, that

$$R(n) = \Theta \left(\exp\left(- \frac{\pi^2 n}{6 \ln 3}\right)\right)$$

for almost all $x \in \mathbb{R}$.

  • $\begingroup$ Should there be an $n$ in there somewhere? $\endgroup$ – Antonio Vargas Nov 2 '16 at 11:32
  • $\begingroup$ @AntonioVargas yup you're quite right $\endgroup$ – 0x539 Nov 2 '16 at 11:34

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.