# What is the length of a continued fraction expansion of a rational number?

I was reviewing quantum factorization and am slightly unclear on a classical detail of order-finding.

Given a (suitably nice) periodic function $f$ with unknown period $r$ and a power of two $N > r^2$, the quantum subroutine yields (with bounded probability) a result of the form $\lfloor jr/N \rceil$ for $1 \le j \le r-1$.

Moreover, $\left \lvert \lfloor jr/N \rceil/N - j/r \right \rvert \le 1/2N$, so since $N > r^2$ a theorem assures us that $j/r$ is a convergent in the continued fraction expansion of $\lfloor jr/N \rceil/N$. Now I see lots of hand-waving at this point in most discussions of the algorithm. If the length of the CFE is $poly(\log(N))$, then this hand-waving can be trivially dispensed with (perhaps at the cost of a slight inefficiency).

So, does the CFE of $M/N$ have length $poly(\log(N))$?

-
It looks like this is the case, and I saw this before I posted, but I don't see an explanation: books.google.com/… –  S Huntsman Nov 15 '10 at 19:43

The length of the CF of a rational number $\displaystyle \dfrac{a}{b}$ is closely related to the number of steps it takes in the Euclidean algorithm for finding gcd of $\displaystyle a,b$, which can, in the worst case, be shown to be proportional to the number of digits in $\displaystyle b$.