User:Marc Schroeder/sandbox3

Deze sandbox hoort bij Methods of computing square roots

Continued fraction expansion

See also: Solving quadratic equations with continued fractions

Square roots

The identity

${\begin{array}{lcl}{\sqrt {x}}&=&1+{\sqrt {x}}-1\\&=&1+{\frac {({\sqrt {x}}-1)({\sqrt {x}}+1)}{({\sqrt {x}}+1)}}\\&=&1+{\frac {x-1}{1+{\sqrt {x}}}}\end{array}}$

leads via recursion to the generalized continued fraction for any square root:

${\begin{array}{lcl}{\sqrt {x}}&=&1+{\frac {x-1}{1+\left(1+{\frac {x-1}{1+{\sqrt {x}}}}\right)}}=1+{\frac {x-1}{2+{\frac {x-1}{1+{\sqrt {x}}}}}}\\&=&1+{\cfrac {x-1}{2+{\cfrac {x-1}{2+{\cfrac {x-1}{2+{\ddots }}}}}}}\\&\\&=&1+{\cfrac {(x-1)}{2+}}{\cfrac {(x-1)}{2+}}{\cfrac {(x-1)}{2+}}\cdots \\&=&1+{\underset {i=1}{\overset {\infty }{\operatorname {K} }}}{\cfrac {x-1}{2}}\end{array}}$

Computation of the convergents

A general continued fraction is an expression of the form

$c=a_{0}+b_{1}/(a_{1}+b_{2}/(a_{2}+b_{3}/(a_{3}+b_{4}/(a_{4}+b_{5}/(a_{5}+b_{6}/(a_{6}+\dots ))))))$

whish is in prefix notation:

$c=\mathop {+} a_{0}\mathop {/} b_{1}\mathop {+} a_{1}\mathop {/} b_{2}\mathop {+} a_{2}\mathop {/} b_{3}\mathop {+} a_{3}\mathop {/} b_{4}\mathop {+} a_{4}\mathop {/} b_{5}\mathop {+} a_{5}\mathop {/} b_{6}\mathop {+} a_{6}\dots$

Here:

$c=\mathop {+} 1\mathop {/} \mathop {-} x\ 1\mathop {+} 2\mathop {/} \mathop {-} x\ 1\mathop {+} 2\mathop {/} \mathop {-} x\ 1\mathop {+} 2\mathop {/} \mathop {-} x\ 1\mathop {+} 2\mathop {/} \mathop {-} x\ 1\mathop {+} 2\mathop {/} \mathop {-} x\ 1\mathop {+} 2\dots$

typedef struct
{
	double p;	// numerator
	double q;	// denominator
} Frac;

or

typedef struct
{
	unsigned long long int p;	// numerator
	unsigned long long int q;	// denominator
} Frac;

Frac sqrt_continued_fraction( Frac x, int k )
{
	Frac current_tail, next_tail;

	for( int i = k ; i > 0 ; i-- )
	{
		// set current_tail to x-1
		current_tail.p = x.p - x.q;
		current_tail.q = x.q;

		if( i == k )
		{
			// last tail: divide (x-1) by 2
			current_tail.q = current_tail.q * 2;
		}
		else
		{
			// 0 < i <= k
			current_tail.p = current_tail.p * next_tail.q;
			current_tail.q = current_tail.q * ((2 * next_tail.q) + next_tail.p);
		} // i > 1

		next_tail = current_tail;
	} // for

	// add first term (= 1) to current_tail
	current_tail.p = current_tail.p + current_tail.q;
	return current_tail;
}

Quadratic irrationals (numbers of the form ${\frac {a+{\sqrt {b}}}{c}}$, where a, b and c are integers), and in particular, square roots of integers, have periodic continued fractions. Sometimes what is desired is finding not the numerical value of a square root, but rather its continued fraction expansion, and hence its rational approximation. Let S be the positive number for which we are required to find the square root. Then assuming a to be a number that serves as an initial guess and r to be the remainder term, we can write $S=a^{2}+r.$ Since we have $S-a^{2}=({\sqrt {S}}+a)({\sqrt {S}}-a)=r$, we can express the square root of S as

${\sqrt {S}}=a+{\frac {r}{a+{\sqrt {S}}}}.$

By applying this expression for ${\sqrt {S}}$ to the denominator term of the fraction, we have

${\sqrt {S}}=a+{\frac {r}{a+(a+{\frac {r}{a+{\sqrt {S}}}})}}=a+{\frac {r}{2a+{\frac {r}{a+{\sqrt {S}}}}}}.$

Compact notation

The numerator/denominator expansion for continued fractions (see left) is cumbersome to write as well as to embed in text formatting systems. So mathematicians have devised several alternative notations, like

${\sqrt {S}}=a+{\frac {r}{2a+}}\,{\frac {r}{2a+}}\,{\frac {r}{2a+}}\cdots$

When $r=1$ throughout, an even more compact notation is:

$[a;2a,2a,2a,\cdots ]$

For repeating continued fractions (which all square roots of non-perfect squares do), the repetend is represented only once, with an overline to signify a non-terminating repetition of the overlined part:

$[a;{\overline {2a}}]$

For √2, the value of $a$ is 1, so its representation is:

$[1;{\overline {2}}]$

Proceeding this way, we get a generalized continued fraction for the square root as ${\sqrt {S}}=a+{\cfrac {r}{2a+{\cfrac {r}{2a+{\cfrac {r}{2a+\ddots }}}}}}$

The first step to evaluating such a fraction to obtain a root is to do numerical substitutions for the root of the number desired, and number of denominators selected. For example, in canonical form, $r$ is 1 and for √2, $a$ is 1, so the numerical continued fraction for 3 denominators is:

${\sqrt {2}}\approx 1+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2}}}}}}$

Step 2 is to reduce the continued fraction from the bottom up, one denominator at a time, to yield a rational fraction whose numerator and denominator are integers. The reduction proceeds thus (taking the first three denominators):

$1+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2}}}}}}=1+{\cfrac {1}{2+{\cfrac {1}{\frac {5}{2}}}}}$

$=1+{\cfrac {1}{2+{\cfrac {2}{5}}}}=1+{\cfrac {1}{\frac {12}{5}}}$

$=1+{\cfrac {5}{12}}={\frac {17}{12}}$

Finally (step 3), divide the numerator by the denominator of the rational fraction to obtain the approximate value of the root:

$17\div 12=1.42$ rounded to three digits of precision.

The actual value of √2 is 1.41 to three significant digits. The relative error is 0.17%, so the rational fraction is good to almost three digits of precision. Taking more denominators gives successively better approximations: four denominators yields the fraction ${\frac {41}{29}}=1.4137$, good to almost 4 digits of precision, etc.

The following are examples of square roots, their simple continued fractions, and their first terms — called convergents — up to and including denominator 99:

√S	~decimal	continued fraction	convergents
√2	1.41421	$[1;{\overline {2}}]$	${\frac {3}{2}},{\frac {7}{5}},{\frac {17}{12}},{\frac {41}{29}},{\frac {99}{70}}$
√3	1.73205	$[1;{\overline {1,2}}]$	${\frac {2}{1}},{\frac {5}{3}},{\frac {7}{4}},{\frac {19}{11}},{\frac {26}{15}},{\frac {71}{41}},{\frac {97}{56}}$
√5	2.23607	$[2;{\overline {4}}]$	${\frac {9}{4}},{\frac {38}{17}},{\frac {161}{72}}$
√6	2.44949	$[2;{\overline {2,4}}]$	${\frac {5}{2}},{\frac {22}{9}},{\frac {49}{20}},{\frac {218}{89}}$
√10	3.16228	$[3;{\overline {6}}]$	${\frac {19}{6}},{\frac {117}{37}}$
${\sqrt {\pi }}$	1.77245	$[1;1,3,2,1,1,6...]$	${\frac {2}{1}},{\frac {7}{4}},{\frac {16}{9}},{\frac {23}{13}},{\frac {39}{22}}$
${\sqrt {e}}$	1.64872	$[1;1,1,1,5,1,1...]$	${\frac {2}{1}},{\frac {3}{2}},{\frac {5}{3}},{\frac {28}{17}},{\frac {33}{20}},{\frac {61}{37}}$
${\sqrt {\phi }}$	1.27202	$[1;3,1,2,11,3,7...]$	${\frac {4}{3}},{\frac {5}{4}},{\frac {14}{11}}$

In general, the larger the denominator of a rational fraction, the better the approximation. It can also be shown that truncating a continued fraction yields a rational fraction that is the best approximation to the root of any fraction with denominator less than or equal to the denominator of that fraction — e.g., no fraction with a denominator less than or equal to 70 is as good an approximation to √2 as 99/70.

Continued fraction expansion OLD

See also: Solving quadratic equations with continued fractions

Quadratic irrationals (numbers of the form ${\frac {a+{\sqrt {b}}}{c}}$, where a, b and c are integers), and in particular, square roots of integers, have periodic continued fractions. Sometimes what is desired is finding not the numerical value of a square root, but rather its continued fraction expansion, and hence its rational approximation. Let S be the positive number for which we are required to find the square root. Then assuming a to be a number that serves as an initial guess and r to be the remainder term, we can write $S=a^{2}+r.$ Since we have $S-a^{2}=({\sqrt {S}}+a)({\sqrt {S}}-a)=r$, we can express the square root of S as

${\sqrt {S}}=a+{\frac {r}{a+{\sqrt {S}}}}.$

By applying this expression for ${\sqrt {S}}$ to the denominator term of the fraction, we have

${\sqrt {S}}=a+{\frac {r}{a+(a+{\frac {r}{a+{\sqrt {S}}}})}}=a+{\frac {r}{2a+{\frac {r}{a+{\sqrt {S}}}}}}.$

Compact notation

The numerator/denominator expansion for continued fractions (see left) is cumbersome to write as well as to embed in text formatting systems. So mathematicians have devised several alternative notations, like

${\sqrt {S}}=a+{\frac {r}{2a+}}\,{\frac {r}{2a+}}\,{\frac {r}{2a+}}\cdots$

When $r=1$ throughout, an even more compact notation is:

$[a;2a,2a,2a,\cdots ]$

For repeating continued fractions (which all square roots of non-perfect squares do), the repetend is represented only once, with an overline to signify a non-terminating repetition of the overlined part:

$[a;{\overline {2a}}]$

For √2, the value of $a$ is 1, so its representation is:

$[1;{\overline {2}}]$

Proceeding this way, we get a generalized continued fraction for the square root as ${\sqrt {S}}=a+{\cfrac {r}{2a+{\cfrac {r}{2a+{\cfrac {r}{2a+\ddots }}}}}}$

The first step to evaluating such a fraction to obtain a root is to do numerical substitutions for the root of the number desired, and number of denominators selected. For example, in canonical form, $r$ is 1 and for √2, $a$ is 1, so the numerical continued fraction for 3 denominators is:

${\sqrt {2}}\approx 1+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2}}}}}}$

Step 2 is to reduce the continued fraction from the bottom up, one denominator at a time, to yield a rational fraction whose numerator and denominator are integers. The reduction proceeds thus (taking the first three denominators):

$1+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2}}}}}}=1+{\cfrac {1}{2+{\cfrac {1}{\frac {5}{2}}}}}$

$=1+{\cfrac {1}{2+{\cfrac {2}{5}}}}=1+{\cfrac {1}{\frac {12}{5}}}$

$=1+{\cfrac {5}{12}}={\frac {17}{12}}$

Finally (step 3), divide the numerator by the denominator of the rational fraction to obtain the approximate value of the root:

$17\div 12=1.42$ rounded to three digits of precision.

The actual value of √2 is 1.41 to three significant digits. The relative error is 0.17%, so the rational fraction is good to almost three digits of precision. Taking more denominators gives successively better approximations: four denominators yields the fraction ${\frac {41}{29}}=1.4137$, good to almost 4 digits of precision, etc.

The following are examples of square roots, their simple continued fractions, and their first terms — called convergents — up to and including denominator 99:

√S	~decimal	continued fraction	convergents
√2	1.41421	$[1;{\overline {2}}]$	${\frac {3}{2}},{\frac {7}{5}},{\frac {17}{12}},{\frac {41}{29}},{\frac {99}{70}}$
√3	1.73205	$[1;{\overline {1,2}}]$	${\frac {2}{1}},{\frac {5}{3}},{\frac {7}{4}},{\frac {19}{11}},{\frac {26}{15}},{\frac {71}{41}},{\frac {97}{56}}$
√5	2.23607	$[2;{\overline {4}}]$	${\frac {9}{4}},{\frac {38}{17}},{\frac {161}{72}}$
√6	2.44949	$[2;{\overline {2,4}}]$	${\frac {5}{2}},{\frac {22}{9}},{\frac {49}{20}},{\frac {218}{89}}$
√10	3.16228	$[3;{\overline {6}}]$	${\frac {19}{6}},{\frac {117}{37}}$
${\sqrt {\pi }}$	1.77245	$[1;1,3,2,1,1,6...]$	${\frac {2}{1}},{\frac {7}{4}},{\frac {16}{9}},{\frac {23}{13}},{\frac {39}{22}}$
${\sqrt {e}}$	1.64872	$[1;1,1,1,5,1,1...]$	${\frac {2}{1}},{\frac {3}{2}},{\frac {5}{3}},{\frac {28}{17}},{\frac {33}{20}},{\frac {61}{37}}$
${\sqrt {\phi }}$	1.27202	$[1;3,1,2,11,3,7...]$	${\frac {4}{3}},{\frac {5}{4}},{\frac {14}{11}}$

In general, the larger the denominator of a rational fraction, the better the approximation. It can also be shown that truncating a continued fraction yields a rational fraction that is the best approximation to the root of any fraction with denominator less than or equal to the denominator of that fraction — e.g., no fraction with a denominator less than or equal to 70 is as good an approximation to √2 as 99/70.