## Continued Fractions of Square Roots – Steps

July 4, 2010 at 19:31 (algorithm, java, math.NT, tutorial)

Everyone knows what continued fractions are, right? Continued fractions have interesting properties and can be used to obtain best rational approximations for real numbers, among other things. Here is an example of a finite continued fraction:

$8.309 = 8+\cfrac{1}{3+\cfrac{1}{4+\cfrac{1}{4+\cfrac{1}{3+\cfrac{1}{2+\cfrac{1}{2}}}}}}$

And here is an example of an infinite continued fraction:

$\sqrt{5} = 2+\cfrac{1}{4+\cfrac{1}{4+\cfrac{1}{4+\cfrac{1}{4+\ddots}}}}$

.
More compactly, $8.309 = [8; 3,4,4,3,2,2]$ and $\sqrt{5} = [2; 4,4,4,4,\,\dots]=$ $[2; (4)]$.

Below is a program that finds continued fraction expansions of square roots of (non-negative) integers, with the option to show steps in LaTeX. For example, here is the output for $\sqrt{47}$ in verbose mode:

$\sqrt{47}=6+\dfrac{\sqrt{47}-6}{1}$

$\dfrac{1}{\sqrt{47}-6}=1+\dfrac{\sqrt{47}-5}{11}$

$\dfrac{11}{\sqrt{47}-5}=5+\dfrac{\sqrt{47}-5}{2}$

$\dfrac{2}{\sqrt{47}-5}=1+\dfrac{\sqrt{47}-6}{11}$

$\dfrac{11}{\sqrt{47}-6}=12+\dfrac{\sqrt{47}-6}{1}$

.

$[6; (1, 5, 1, 12)]$

.

The code:

.
import java.util.ArrayList;

public class ContFracSqrt {
static boolean v=true; // verbosity

public static void main(String[] args) {
print(cfe(47));
}

static void print(ArrayList<Integer> a) {
int i;
String s=a.toString();
if(a.size()>1)
for(i=2;;i++)
if(s.charAt(i)==',') {
s=s.substring(0,i)+"; ("+s.substring(i+2);
s=s.substring(0,s.length()-1)+")]";
break;
}
System.out.println(s);
}

static ArrayList<Integer> cfe(int n) {
ArrayList<Integer> x=new ArrayList<Integer>();
if(n<0) return x;
int a=(int)Math.sqrt(n),b=a,c=1,d,e,f,g;
if(a*a==n) return x;
if(v) System.out.println("\\sqrt{"+n+"}="+a+"+\\dfrac{\\sqrt{"+n+"}-"+a+"}{1}");
if(v) System.out.print("\\dfrac{1}{\\sqrt{"+n+"}-"+a+"}=");
while(true) {
d=c;
c=n-b*b;
g=gcd(c,d);
c/=g;
d/=g;
b=-b;
f=a-c;
for(e=0;b<=f;e++)
b+=c;
if(v) System.out.println(e+"+\\dfrac{\\sqrt{"+n+"}-"+b+"}{"+c+"}");
if(b==a&&c==1) return x;
if(v) System.out.print("\\dfrac{"+c+"}{\\sqrt{"+n+"}-"+b+"}=");
}
}

static int gcd(int a,int b) {
return (b==0)?a:gcd(b,a%b);
}
}


Note: the for loop in cfe() can be replaced with integer division; I haven’t tested how this would affect efficiency, but it shouldn’t matter unless you need something unusually efficient.