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,


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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