# Converting a square root into a simple continued fraction

One can convert a square root $\sqrt{n}$ into a continued fraction $[a_0; \overline{a_1, a_2, \dots , a_k}]$ following the algebraic algorithm explained here: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/cfINTRO.html#sqrtalgsalg.

I have to do this programmatically (using Python). The problem is I cannot use algebra, so I modified the method above:

we describe the fraction obtained in Step 3 like this: $\dfrac{c(\sqrt{n} + m)}{d}$; when $\gcd(c, d) = d$ the algorithm terminates.

For the interested ones, here is the code (24 lines of code): https://gist.github.com/1454917.

The problem is that with numbers with order of magnitude $n=10^{10}$ this method becomes slow. Are there any other methods and/or some optimization I could do?

Thank you,

-