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;
        x.add(a);
        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;
            x.add(e);
            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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: