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
\begin{equation}
\Big| \dfrac{s}{r} - \psi \Big| \leq \dfrac{1}{2r^{2}}
\end{equation}
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?
Yes, that's exactly the idea.  It is inspired by the following fact:

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$.



See also https://math.stackexchange.com/q/1139381/14578.