# Continued fractions with Shor's algorithm: which convergent?

Suppose I am using Shor's order finding algorithm to calculate the order $$r$$ of $$x\leq N$$ with respect to $$N$$. After some run of the QPE subroutine, I obtain a good, $$L$$-bit approximation to $$s/r$$ for some $$s\leq r$$. According to, say, Nielsen and Chuang, because my estimation $$\phi$$ is sufficiently close, when I do the continued-fractions algorithm (CFA) on $$\phi$$, one of the convergents will be exactly $$s/r$$.

My question is, how will we know which convergent? It certainly isn't necessarily the last convergent, since this will be equal to the binary approximation $$\phi$$ and not $$s/r$$. Is there a guess-and-check stage that goes on here and if so, does efficiently of the algorithm depend on the number of convergents being small relative to $$N$$?

Edit: I should mention that I am also curious why the answer is what it is. Namely, if we are able to make a specific choice of convergent, what mathematical argument allows us to do so?

You use the last one whose denominator is less than $$N$$, the number you're trying to factor. The value returned by fraction.limit_denominator(N) in python.