# Continued Fraction Algorithm in Shor's Algorithm

I am just trying to make the final link of Shor's algorithm clear. Here $r$ is the order of $x$ modulo $N$.

We have a number $\psi$, which for a rational number $\dfrac{s}{r}$ satisfies $$\Big| \dfrac{s}{r} - \psi \Big| \leq \dfrac{1}{2r^{2}}$$ which means that if $\psi$ has continued fraction algorithm $[a_0,\dots,a_N]$ then $\dfrac{s}{r}$ has continued fraction $[a_0,\dots,a_k]$ for $k \leq N$.

The book just says that then applying the continued fractions algorithm to $\psi$ we obtain $r'$ which is our estimate for $r$. I'm not too sure how exactly we arrive at this value of $r'$. Is it just that once we obtain our expansion $\psi = [a_0,\dots,a_N]$, we obtain a value $r'_{m}$ for each of the $m^{th}$ convergent expansions and see which one is correct?

Theorem. Let $\psi$ be an irrational number, and suppose $|\psi - s/r| \le 1/2r^2$. Then $s/r$ is one of the convergents of the continued fraction expansion of $\psi$.
In other words, every "very good" approximation to $\psi$ can be obtained by computing the continued fraction representation of $\psi$ and looking at one of its convergents.
In the specific situation you mentioned, we know $\psi$, and we don't know $s$ or $r$. However, we know that there exist $s,r$ such that $|\psi - s/r| \le 1/2r^2$. It follows from the theorem that $s/r$ must be one of the convergents of the continued fraction of $\psi$.
Therefore, if we iterate through the convergents of the continued fraction for $\psi$, this is guaranteed to find $s,r$. Moreover, this procedure is efficient: you'll only have to look at $O(\lg r)$ convergents, so the running time will be polynomial in $\lg N$.