Take the 2-minute tour ×
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.

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,

share|improve this question

1 Answer 1

up vote 3 down vote accepted

I gave a complete answer at http://mathoverflow.net/questions/22811/upper-bound-of-period-length-of-continued-fraction-representation-of-very-composi/23014#23014

share|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: gist.github.com/1454917#file_a_cfrac.py –  rubik Dec 10 '11 at 12:53

Your Answer

 
discard

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.