[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:	Mathematics at DEC

Moderator:	RUSURE::EDP

Created:	Mon Feb 03 1986
Last Modified:	Fri Jun 06 1997
Last Successful Update:	Fri Jun 06 1997
Number of topics:	2083
Total number of notes:	14613

1338.0. "how can we get continued fractions for square roots ?" by HANNAH::OSMAN (see HANNAH::IGLOO$:[OSMAN]ERIC.VT240) Wed Nov 14 1990 14:02

Goal:   Pick any integer n and represent its sqrt like this:

sqrt(n) = a+1
	    ----
	    b+1
	      ----
	      c+1 ...

where a,b,c are the (largest possible) positive integers.

In short form, let's write this as

sqrt(n) = <a b c ...>

Let's try sqrt(2):

sqrt(2) = a+1/rest

With minimal numerical analysis, we find a=1, so

[1]   sqrt(2) = 1+1/r

Now we want to find integer b in

r = b+1/rest

Well, solving [1] for r, we get

r=1/(sqrt(2)-1)

rationalizing denominator by multiplying top and bottom by sqrt(2)+1, we get

r=1+sqrt(2)

Substituting that r back into [1], we get

sqrt(2) = 1+1/(1+sqrt(2))

Substituting this last into itself ad nauseum, we get

sqrt(2) = 1+1/(1+1+1/(1+1+1/(1+1+1/(1+...

which is

sqrt(2) = 1+1/(2+1/(2+1/...

which we can write in short form as

sqrt(2) = <1 2 2 2 ...>

It's important to note the slight numerical analysis that was used to
get a=1.

Now let's try sqrt(3):

sqrt(3) = a+1/r

With some numerical analysis, we get a=1.  So

[1]   sqrt(3) = 1+1/r

Solving for r,

r=1/(sqrt(3)-1)

Rationalizing,

[2]   r=(1+sqrt(3))/2

We'd like to represent this r again as

[3]   r=b+1/rest

with b as largest possible positive integer.

What is b ?  Well, we're looking for largest integer b such that

2b < 1+sqrt(3) < 2(b+1)

By original numerical analysis, we know sqrt(3) is between 1 and 2, hence
1+sqrt(3) is between 2 and 3, hence

2b < 2.something < 2(b+1)

Since b is an integer, b=1.

Substituting back into [3], we get

[4]   r=1+1/rest

Recall [2] which said r=(1+sqrt(3))/2.  Equate these last two and we have

(1+sqrt(3))/2 = 1+1/rest

Solve for "rest", which we start by subtracting 1 from both sides and
taking reciprocal:

rest = 1/((1+sqrt(3))/2 - 1)

Multiply top and bottom by 2:

rest = 2/(1+sqrt(3)-2).  Simplify that to      rest = 2/(sqrt(3)-1).

Rationalize, which nicely gives a 2 on bottom which we cancel with top, so

rest = 1 + sqrt(3).

The fact that we have sqrt(3) standing alone is our signal that we are
done and can substitute back.  Recall [4]   r=1+1/rest.  Substitute:

r=1+1/(1+sqrt(3)).

Recall [1]   sqrt(3) = 1+1/r.  Substitute ad nauseum:

sqrt(3) = 1+1/1+1/(1+1+1/1+1/(1+1+1/1+1/(1+1+1/...

Simplifying, we have

sqrt(3) = 1+1/1+1/2+1/1+1/2+1/1+1/2+1/...

or in short form,

sqrt(3) = <1 1 2 1 2 1 2 1 2 ...>

The question is, can we simplify this procedure for sqrt(n) for any
integer n ?

T.R	Title	User	Personal Name	Date	Lines
1338.1	Article answers question.	CADSYS::COOPER	Topher Cooper	`Sun Nov 25 1990 19:59`	28
	You will find the answer to your question in: Vuillemin, Jean E.; Exact Real Computer Arithmetic with Continued Fractions; IEEE Transactions on Computers, vol 39, #8; Aug. 1990 pp1087-1105 This discusses using a representation of continued fractions as an implementation for the exact representation of real numbers. The continued fraction is represented (in its most basic form) as a list of numbers (possibly with a loop) with a continuation which specifies how to extend the list, if needed for computation. There are some oddities from most perspectives -- i.e., you may be unable to specify in finite time whether two numbers with a finite representation are equal; but overall, a very general, not extraordinarily inefficient, representation is given for "computable" reals. Two basic algorithms are given. The "algebraic algorithm" allows algebraic reals to be specified, while the "transcendental algorithm" allows a broad class of transcendental reals to be specified (logs, exponentials, trig, and inverse trig; the abstract says "as well as a wide class of special functions", but these special functions are left, essentially as an exercise for the reader). Anyway, on page 1100 is an algorithm (specialized from the algebraic algorithm) for finding the representation of the square root of an arbitrary rational number. You will have to read the preceding material since the description does not stand on its own. Topher
1338.2	x=p+1/(a+1/(a+1/(a+...	HANNAH::OSMAN	see HANNAH::IGLOO$:[OSMAN]ERIC.VT240	`Thu Nov 29 1990 13:33`	65
1338.3		GUESS::DERAMO	Dan D'Eramo	`Thu Nov 29 1990 15:01`	29
1338.4		GUESS::DERAMO	Dan D'Eramo	`Thu Nov 29 1990 15:05`	12
1338.5	avoiding quadratic formula, and interesting questions for readers	HANNAH::OSMAN	see HANNAH::IGLOO$:[OSMAN]ERIC.VT240	`Tue Dec 04 1990 12:47`	223
1338.6	How to compute continued fractions for sqrt(n)	HANNAH::OSMAN	see HANNAH::IGLOO$:[OSMAN]ERIC.VT240	`Wed Dec 12 1990 14:37`	239
	I have finally figured out how to compute the continued fraction for square roots. Contained in this paper: 1) An example of computing sqrt(19) 2) A generalized example with reference to an unprovem theorem (see another note for discussion of the theorem) Suppose we wish to express sqrt(19) = a + 1/b where a is an integer. Well, 44 is 16, and 55 is 25, too much, so a = 4. So we have sqrt(19) = 4 + 1/b To make the equation still hold, then necessarily the 1/b is sqrt(19)-4, and we want to leave the "1/" there, so we write as: sqrt(19) = 4 + 1/(1/(sqrt(19)-4)) Rationalize the denominator by multiplying top and bottom by sqrt(19)+4, giving us sqrt(19) = 4 + 1/((sqrt(19)+4)/3) We remind ourselves the form we're trying to follow, namely sqrt(19) = 4 + 1/(a + 1/b) (This is a form, so the "a" and "b" are different than before. So, we have (sqrt(19)+4)/3 = a + 1/b This "a" is easily seen be 2, since 4 < sqrt(19) < 5, hence 8 < sqrt(19)+4 < 9. So, (sqrt(19)+4)/3 = 2 + 1/b As before, we represent b as the reciprocal of the lefthand side with a subtracted, so (sqrt(19)+4)/3 = 2 + 1/(1/((sqrt(19)+4/3) - 2) Combining the -2 with the fraction by cross-multiplying, we have (sqrt(19)+4)/3 = 2 + 1/(1/((sqrt(19)-2)/3)) Remove the inner reciprocal by flipping, so (sqrt(19)+4)/3 = 2 + 1/(3/(sqrt(19)-2)) Rationalize denominator again, giving (sqrt(19)+4)/3 = 2 + 1/(3(sqrt(19)+2)/15) THIS IS WHERE AN UNPROVEN BUT HOPEFULLY EASY-TO-PROVE THEOREM APPEARS. Namely, the 15 is divisible by 3 and I believe the denominator at this step always will be. See another note where I address the theorem directly. So, (sqrt(19)+4)/3 = 2 + 1/((sqrt(19)+2)/5) In process, we've come full circle, because now we want to solve (sqrt(19)+2)/5 = a + 1/b which can be done exactly as we did with (sqrt(19)+4)/3. Eventually, we come back to (sqrt(19)+4)/3, so we know the pattern repeats. The particular string of a's that emerge for this example shows that sqrt(19) = 4+1/(2+1/(1+1/(3+1/(1+1/(2+1/... Written in short form sqrt(19) = 4 2 1 3 1 2 8 2 1 3 1 2 8 2 1 3 1 2 8 ... To generalize all of this, suppose we start with (sqrt(r)+s)/t and we wish to generate the continued fraction. So, we the form (sqrt(r)+s)/t = a + 1/b We can find a, given only the \|sqrt(r)\|. The vertical bar means "floor" of what's inside, or the largest integer less than the value inside. So, a = \|(\|sqrt(r)\|+s)/t\| Represent b as the reciprocal of the difference of "a" and (sqrt(r)+s)/t: b = 1/((sqrt(r)+s)/t) - a) Cross-multiply to make single fraction on bottom: b = 1/(((sqrt(r)+s-at)/(at)) Since it's a single fraction, we can flip and simplify: b = at/((sqrt(r)+s-at) We want to rationalize the bottom, so let w=s-at and rationalize: b = at(sqrt(r)-w)/(r-ww) HERE'S WHERE THE UNPROVED THEOREM COMES IN. THE THEOREM SAYS: "at" divides evenly into r-ww or as mathematicians like to say it: at \| r-ww So, assuming that theorem is true, we let x=(r-ww)/at, so we have b = (sqrt(r)-w)/x This is an identical problem as before. If w and x match the original s and t, we can stop since we know the values will repeat the same forever. If w and x don't match, we just set up the form (sqrt(r)-w)/x = a +1/b and repeat the process. I formalized the above in a program, and ran it for all the numbers from 1 to 100. Here they are: sqrt(1) = 1. sqrt(2) = 1 2 2 2 ... sqrt(3) = 1 1 2 1 2 1 2 ... sqrt(4) = 2. sqrt(5) = 2 4 4 4 ... sqrt(6) = 2 2 4 2 4 2 4 ... sqrt(7) = 2 1 1 1 4 1 1 1 4 1 1 1 4 ... sqrt(8) = 2 1 4 1 4 1 4 ... sqrt(9) = 3. sqrt(10) = 3 6 6 6 ... sqrt(11) = 3 3 6 3 6 3 6 ... sqrt(12) = 3 2 6 2 6 2 6 ... sqrt(13) = 3 1 1 1 1 6 1 1 1 1 6 1 1 1 1 6 ... sqrt(14) = 3 1 2 1 6 1 2 1 6 1 2 1 6 ... sqrt(15) = 3 1 6 1 6 1 6 ... sqrt(16) = 4. sqrt(17) = 4 8 8 8 ... sqrt(18) = 4 4 8 4 8 4 8 ... sqrt(19) = 4 2 1 3 1 2 8 2 1 3 1 2 8 2 1 3 1 2 8 ... sqrt(20) = 4 2 8 2 8 2 8 ... sqrt(21) = 4 1 1 2 1 1 8 1 1 2 1 1 8 1 1 2 1 1 8 ... sqrt(22) = 4 1 2 4 2 1 8 1 2 4 2 1 8 1 2 4 2 1 8 ... sqrt(23) = 4 1 3 1 8 1 3 1 8 1 3 1 8 ... sqrt(24) = 4 1 8 1 8 1 8 ... sqrt(25) = 5. sqrt(26) = 5 10 10 10 ... sqrt(27) = 5 5 10 5 10 5 10 ... sqrt(28) = 5 3 2 3 10 3 2 3 10 3 2 3 10 ... sqrt(29) = 5 2 1 1 2 10 2 1 1 2 10 2 1 1 2 10 ... sqrt(30) = 5 2 10 2 10 2 10 ... sqrt(31) = 5 1 1 3 5 3 1 1 10 1 1 3 5 3 1 1 10 1 1 3 5 3 1 1 10 ... sqrt(32) = 5 1 1 1 10 1 1 1 10 1 1 1 10 ... sqrt(33) = 5 1 2 1 10 1 2 1 10 1 2 1 10 ... sqrt(34) = 5 1 4 1 10 1 4 1 10 1 4 1 10 ... sqrt(35) = 5 1 10 1 10 1 10 ... sqrt(36) = 6. sqrt(37) = 6 12 12 12 ... sqrt(38) = 6 6 12 6 12 6 12 ... sqrt(39) = 6 4 12 4 12 4 12 ... sqrt(40) = 6 3 12 3 12 3 12 ... sqrt(41) = 6 2 2 12 2 2 12 2 2 12 ... sqrt(42) = 6 2 12 2 12 2 12 ... sqrt(43) = 6 1 1 3 1 5 1 3 1 1 12 1 1 3 1 5 1 3 1 1 12 1 1 3 1 5 1 3 1 1 12 ... sqrt(44) = 6 1 1 1 2 1 1 1 12 1 1 1 2 1 1 1 12 1 1 1 2 1 1 1 12 ... sqrt(45) = 6 1 2 2 2 1 12 1 2 2 2 1 12 1 2 2 2 1 12 ... sqrt(46) = 6 1 3 1 1 2 6 2 1 1 3 1 12 1 3 1 1 2 6 2 1 1 3 1 12 1 3 1 1 2 6 2 1 1 3 1 12 ... sqrt(47) = 6 1 5 1 12 1 5 1 12 1 5 1 12 ... sqrt(48) = 6 1 12 1 12 1 12 ... sqrt(49) = 7. sqrt(50) = 7 14 14 14 ... sqrt(51) = 7 7 14 7 14 7 14 ... sqrt(52) = 7 4 1 2 1 4 14 4 1 2 1 4 14 4 1 2 1 4 14 ... sqrt(53) = 7 3 1 1 3 14 3 1 1 3 14 3 1 1 3 14 ... sqrt(54) = 7 2 1 6 1 2 14 2 1 6 1 2 14 2 1 6 1 2 14 ... sqrt(55) = 7 2 2 2 14 2 2 2 14 2 2 2 14 ... sqrt(56) = 7 2 14 2 14 2 14 ... sqrt(57) = 7 1 1 4 1 1 14 1 1 4 1 1 14 1 1 4 1 1 14 ... sqrt(58) = 7 1 1 1 1 1 1 14 1 1 1 1 1 1 14 1 1 1 1 1 1 14 ... sqrt(59) = 7 1 2 7 2 1 14 1 2 7 2 1 14 1 2 7 2 1 14 ... sqrt(60) = 7 1 2 1 14 1 2 1 14 1 2 1 14 ... sqrt(61) = 7 1 4 3 1 2 2 1 3 4 1 14 1 4 3 1 2 2 1 3 4 1 14 1 4 3 1 2 2 1 3 4 1 14 ... sqrt(62) = 7 1 6 1 14 1 6 1 14 1 6 1 14 ... sqrt(63) = 7 1 14 1 14 1 14 ... sqrt(64) = 8. sqrt(65) = 8 16 16 16 ... sqrt(66) = 8 8 16 8 16 8 16 ... sqrt(67) = 8 5 2 1 1 7 1 1 2 5 16 5 2 1 1 7 1 1 2 5 16 5 2 1 1 7 1 1 2 5 16 ... sqrt(68) = 8 4 16 4 16 4 16 ... sqrt(69) = 8 3 3 1 4 1 3 3 16 3 3 1 4 1 3 3 16 3 3 1 4 1 3 3 16 ... sqrt(70) = 8 2 1 2 1 2 16 2 1 2 1 2 16 2 1 2 1 2 16 ... sqrt(71) = 8 2 2 1 7 1 2 2 16 2 2 1 7 1 2 2 16 2 2 1 7 1 2 2 16 ... sqrt(72) = 8 2 16 2 16 2 16 ... sqrt(73) = 8 1 1 5 5 1 1 16 1 1 5 5 1 1 16 1 1 5 5 1 1 16 ... sqrt(74) = 8 1 1 1 1 16 1 1 1 1 16 1 1 1 1 16 ... sqrt(75) = 8 1 1 1 16 1 1 1 16 1 1 1 16 ... sqrt(76) = 8 1 2 1 1 5 4 5 1 1 2 1 16 1 2 1 1 5 4 5 1 1 2 1 16 1 2 1 1 5 4 5 1 1 2 1 16 ... sqrt(77) = 8 1 3 2 3 1 16 1 3 2 3 1 16 1 3 2 3 1 16 ... sqrt(78) = 8 1 4 1 16 1 4 1 16 1 4 1 16 ... sqrt(79) = 8 1 7 1 16 1 7 1 16 1 7 1 16 ... sqrt(80) = 8 1 16 1 16 1 16 ... sqrt(81) = 9. sqrt(82) = 9 18 18 18 ... sqrt(83) = 9 9 18 9 18 9 18 ... sqrt(84) = 9 6 18 6 18 6 18 ... sqrt(85) = 9 4 1 1 4 18 4 1 1 4 18 4 1 1 4 18 ... sqrt(86) = 9 3 1 1 1 8 1 1 1 3 18 3 1 1 1 8 1 1 1 3 18 3 1 1 1 8 1 1 1 3 18 ... sqrt(87) = 9 3 18 3 18 3 18 ... sqrt(88) = 9 2 1 1 1 2 18 2 1 1 1 2 18 2 1 1 1 2 18 ... sqrt(89) = 9 2 3 3 2 18 2 3 3 2 18 2 3 3 2 18 ... sqrt(90) = 9 2 18 2 18 2 18 ... sqrt(91) = 9 1 1 5 1 5 1 1 18 1 1 5 1 5 1 1 18 1 1 5 1 5 1 1 18 ... sqrt(92) = 9 1 1 2 4 2 1 1 18 1 1 2 4 2 1 1 18 1 1 2 4 2 1 1 18 ... sqrt(93) = 9 1 1 1 4 6 4 1 1 1 18 1 1 1 4 6 4 1 1 1 18 1 1 1 4 6 4 1 1 1 18 ... sqrt(94) = 9 1 2 3 1 1 5 1 8 1 5 1 1 3 2 1 18 1 2 3 1 1 5 1 8 1 5 1 1 3 2 1 18 1 2 3 1 1 5 1 8 1 5 1 1 3 2 1 18 ... sqrt(95) = 9 1 2 1 18 1 2 1 18 1 2 1 18 ... sqrt(96) = 9 1 3 1 18 1 3 1 18 1 3 1 18 ... sqrt(97) = 9 1 5 1 1 1 1 1 1 5 1 18 1 5 1 1 1 1 1 1 5 1 18 1 5 1 1 1 1 1 1 5 1 18 ... sqrt(98) = 9 1 8 1 18 1 8 1 18 1 8 1 18 ... sqrt(99) = 9 1 18 1 18 1 18 ... Anyone that wants a copy of the program, send a SASE to Eric Osman Digital Equipment Corp. USA
1338.7	Continued fractions is non-unique.	CADSYS::COOPER	Topher Cooper	`Wed Dec 12 1990 15:45`	10
	Very good, Eric. Note that you do not have to use "floor". Equally valid fractions will result if you use "ceiling" or sometimes use one and sometimes the other (e.g., alternating, rounding or randomly). You might have started your example with a = 25. The initial 1/b would then have had to be negative, but there is nothing wrong with that, it just means that the next a would have been negative rather than positive. Topher
1338.8		GUESS::DERAMO	Sometimes they leave skid marks.	`Wed Dec 12 1990 16:05`	12
	re .7 Continued fractions is non-unique. However, there is a bijective correspondence between the irrationals in (0,1) and \omega-sequences of positive integers, x <--> 1/(n0 + 1/(n1 + 1/(n2 + ...))). If you topologize the irrationals in (0,1) as a subspace of the order topology on the real line, and topologize the set of such sequences as a product of discrete spaces, then continued fraction evaluation is a homeomorhpism (a bijection and both it and its inverse are continuous). Dan
1338.9	translating into English...	HANNAH::OSMAN	see HANNAH::IGLOO$:[OSMAN]ERIC.VT240	`Wed Dec 12 1990 16:39`	7
	Gee, if I were as good a go player as Dan is a mathematician... By limiting the values to POSITIVE ones, then every positive real has a UNIQUE mapping to a simple continued fraction. (I think my number theory book uses the term "simple" continued fraction to mean positive integers as the "a's".)
1338.10		GUESS::DERAMO	Sometimes they leave skid marks.	`Wed Dec 12 1990 17:40`	40
	Thanks. >> By limiting the values to POSITIVE ones, then every positive real has >> a UNIQUE mapping to a simple continued fraction. (I think my number >> theory book uses the term "simple" continued fraction to mean positive >> integers as the "a's".) Be careful with that word "UNIQUE". If you define [n0,n1,n2,...] = 1/(n1 + 1/(n2 + 1/(n3 + ...))) then the bijective correspondence is between the irrationals in (0,1) and the nonterminating continued fractions of positive integers [n0,n1,n2,...]. If you define <a0,a1,a2,...> = a0 + 1/(a1 + 1/(a2 + ...))) = a0 + [a1,a2,a3,...] = 1/[a0,a1,a2,...] then there is a bijective correspondence between the irrationals GREATER THAN ONE and the nonterminating continued fractions of positive integers <a0,a1,a2,...>. Or, there is a bijective correspondence between the positive irrationals and the nonterminating continued fractions <a0,a1,a2,...> where a0 is a nonnegative integer and a1,a2,a3,... are positive integers. The rationals/terminating continued fractions cause even more problems if you desire uniqueness, as for example 2 = <2> = <1,1>. If you "outlaw" terminating with a 1 then how do you represent 1 = <1>? You have to be very careful if you want to specify a unique canonical form for expressing rationals. Dan
1338.11	not to mention...	HANNAH::OSMAN	see HANNAH::IGLOO$:[OSMAN]ERIC.VT240	`Wed Dec 12 1990 17:53`	8
	Not to mention that [a0,a1,a2] = a0+1/(a1+1/a2) = a0+1/(a1+1/(a2-1 + 1/1)) = [a0,a1,a2-1,1] but my book number theory book defines uniqueness and acknowledges this specific-but-uninteresting counterexample. /Eric