1
$\begingroup$

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,

1 Answers 1

3

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

  • 0
    Thank you!! It works *perfectly*! If someone wants to see the Python code, it's here: https://gist.github.com/1454917#file_a_cfrac.py2011-12-10