Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:

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):

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,

share|cite|improve this question
up vote 3 down vote accepted

I gave a complete answer at

share|cite|improve this answer
Thank you, I'll read it! – rubik Dec 10 '11 at 11:52
Thank you!! It works perfectly! If someone wants to see the Python code, it's here: – rubik Dec 10 '11 at 12:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.