1
$\begingroup$

Computing regular continued fractions by iteratively inverting the remainder is easiest, but runs into problems with fixed precision arithmetics. Its possible to work with arbitrary precision libraries, but that is really slow.

Due to other posts on this page I came along the algorithm described here. It is very intuitive, but it requires a repeated computation of square roots (or rather the integer part of the square root), which still seems unnecessary:

I also found the algorithm hidden on this page, which reads implemented in Python:

def cf_sqrt(D):
    a0 = int(sqrt(D))
    result = [a0]

    an, Pn, Qn = a0, 0, 1
    while an != 2*a0:
        Pn = an*Qn - Pn
        Qn = (D - Pn**2)/Qn
        an = int((a0 + Pn)/Qn)
        result.append(an)
    return result

It only needs a single square root evaluation and other than that only basic arithmetic operations. However, I can not figure out, why this actually works. I can verify the result for individual numbers, but I'd like to have a prove, that this functions indeed computes the continued fraction of $\sqrt{D}$.

$\endgroup$
3
  • $\begingroup$ I think if you do a computation of $\sqrt n$ for a particular $n$ (say $n=13$ or $n=7$, not with a calculator but in precise arithmetic, derationalizing the denominator when necessary, you’ll see that it’s a description of what you’re doing at each step. (I haven’t checked that this is precisely my algorithm, but it certainly looks like.) $\endgroup$
    – Lubin
    Commented Jan 13, 2020 at 18:04
  • $\begingroup$ How do I compute $\sqrt{n}$ in precise arithmetic? Can you give a reference for "your" algorithm? Btw., I messed up the first link. It should point to maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/… $\endgroup$
    – staxyz
    Commented Jan 13, 2020 at 18:49
  • $\begingroup$ Please look at MSE question 213683 "Calculate the continuedd fraction of square root". $\endgroup$
    – Somos
    Commented Jan 13, 2020 at 22:51

1 Answer 1

0
$\begingroup$

This is not really an answer, but let me illustrate a fairly standard procedure for getting the expansion of $\sqrt n$ where $n>0$, nonsquare. I’ll do it for $\sqrt7$.

Preliminary step, find $m=\lfloor\sqrt7\rfloor$, i.e. the largest integer for which $m^2<7$, so $m=2$.

Then compute: \begin{align} \sqrt7-2=\frac{\sqrt7-2}1&=\frac3{\sqrt7+2}&=\frac1{(\sqrt7+2)/3}&=\frac1{1+(\sqrt7-1)/3}\\ \frac{\sqrt7-1}3&=\frac2{\sqrt7+1} &=\frac1{(\sqrt7+1)/2}&=\frac1{1+(\sqrt7-1)/2}\\ \frac{\sqrt7-1}2&=\frac3{\sqrt7+1}&=\frac1{(\sqrt7+1)/3}&=\frac1{1+(\sqrt7-2)/3}\\ \frac{\sqrt7-2}3&=\frac1{\sqrt7+2}&=\frac1{4+\sqrt7-2}\\ \sqrt7-2=\text{( it repeats )} \end{align} Thus the expansion of $\sqrt7$ is $2+\frac1{1+}\frac1{1+}\frac1{1+}\frac1{4+\cdots}$ . When I said, “precise arithmetic, derationalizing the denominator when necessary”, I meant exactly the step that takes, for instance, $(\sqrt7-1)/3$ to $(7-1)/\bigl(3(\sqrt7+1)\bigr)=2/(\sqrt7+1)$. It’s just the process you learned in high-school to “rationalize the denominator”, except going backwards.

I’m pretty sure that if you analyse the process step by step, you’ll see that it’s performed exactly by the Python routine that you’ve quoted.

$\endgroup$
4
  • $\begingroup$ Yes, you're right. What you are describing here was in fact not my problem. I was just looking at three examples at once and overlooked, that I need to calculate the square root of $n$ only once. $\endgroup$
    – staxyz
    Commented Jan 14, 2020 at 16:55
  • $\begingroup$ Actually, @xwst, you don’t need to calculate the square root (as a real number) at all: just find the number $m$ such that $m^2<n<(m+1)^2$. $\endgroup$
    – Lubin
    Commented Jan 14, 2020 at 18:01
  • $\begingroup$ Yes, you're right. But how to do that efficiently for large numbers is not obvious. From what I understand, it is the time consuming part to get the integer component, while the decimal digits are obtained easily from that using Heron. $\endgroup$
    – staxyz
    Commented Jan 14, 2020 at 18:25
  • $\begingroup$ Huge numbers $n$ ? I can’t see the difficulty if you have the decimal expansion. Nor do I see much point in getting the continued-fraction expansion of $\sqrt n$ for gigantic $n$, but that’s your business… $\endgroup$
    – Lubin
    Commented Jan 14, 2020 at 22:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .