Help understanding continuing fractions

[John3509]

They are mysterious to me, they do not make any intuitive sense. What is the context for them? I found this website. http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/cfINTRO.html

It tries to show the history of how they were discovered geometrically. So you start off with a rectangle with sides 16, 45 and you take a ratio. My first problem, why would you take a ratio of their sides? Then you flip it, 45/16, my second problem, why flip it? Then you turn it into a mixed number. Then you rewrite 13/16 as 1/(16/13), My third issue with this, why?

It seems to me that you get this "thing" when you follow an algorithm specifically designed to give you that thing, as opposed to it arising naturally, or authentically, stemming from some deeper interpretation.

Its like if I said the number 3 is special because if you start at 4 and 2 on the number line and go inward at the same speed you will hit this number, yes that is factually true, but why would you set up this scenario? Things like squaring and quadratics have a deeper interpretation, it tells you how much your squares area has increased if you increase the length of a side. Is there some other meaning for this?

 

[fresh_42]

Continued fractions are old, very old. They have been found in ancient chinese, greek and indian culture. The basic idea is an approximation algorithm for a certain number $x$. We begin with $a_0:=\lfloor x \rfloor$ as first approximation. Now we have $x=a_0+\xi_0$ with a number $\xi_0 \in [0,1)$. So either we are done if $\xi=0$ or we have a problem. In order to continue with our approach, we must turn $\xi_0$ into a number which we again can subtract the integer part of. Hence we must turn to $\xi_0$ into a number greater than one, i.e. we move on with $\xi_0^{-1}$. This allows us to carry on. Say $\xi_1^{-1}=\lfloor \xi_0 \rfloor + \xi_1=a_1+\xi_1$. And so on. Going back to $x$ this results in
$$
x=a_0+ \dfrac{1}{a_1+\xi_1}=a_0+ \dfrac{1}{a_1+\dfrac{1}{a_2+\xi_2}}= \ldots
$$

So that's the basic idea. I don't know about the geometric interpretation of your book, only the arithmetic approximation I described. Don't forget that Fermat, Huygens, Lagrange, Legendre and Euler couldn't just hit a key labeled $\pi$ on a calculator! They had to find ways to handle irrational numbers and work with them. Periodic continued fractions are one way to achieve this. Even numerically they provide approximations to every desired degree. And the approximation is good!

 

[Stephen Tashi]

It seems to me that you get this "thing" when you follow an algorithm specifically designed to give you that thing, as opposed to it arising naturally, or authentically, stemming from some deeper interpretation.

I don't know the history of continued fractions. Nowadays, algorithms and computers are well known, so people interpret the "..." notation as specifying an algorithm. Many people enjoy thinking about expressions that implicitly involve an infinite number of symbols. They don't require any physical motivation for the expressions. They just enjoy thinking about patterns of symbols.

It's worth noting that the "..." notation doesn't necessarily specify a unique infinite sequence. Defining the meaning of that notation requires saying explicitly how we will form the sequence. See the Youtube video , especially at 8:15.

 

[John3509]

Continued fractions are old, very old. They have been found in ancient chinese, greek and indian culture. The basic idea is an approximation algorithm for a certain number $x$. We begin with $a_0:=\lfloor x \rfloor$ as first approximation. Now we have $x=a_0+\xi_0$ with a number $\xi_0 \in [0,1)$. So either we are done if $\xi=0$ or we have a problem. In order to continue with our approach, we must turn $\xi_0$ into a number which we again can subtract the integer part of. Hence we must turn to $\xi_0$ into a number greater than one, i.e. we move on with $\xi_0^{-1}$. This allows us to carry on. Say $\xi_1^{-1}=\lfloor \xi_0 \rfloor + \xi_1=a_1+\xi_1$. And so on. Going back to $x$ this results in
$$
x=a_0+ \dfrac{1}{a_1+\xi_1}=a_0+ \dfrac{1}{a_1+\dfrac{1}{a_2+\xi_2}}= \ldots
$$

That sounds vaguely similar to a certain method for computing logs,
https://www.quora.com/How-can-we-calculate-the-logarithms-by-hand-without-using-any-calculator
The first reply.

But I do not understand your response. What context would you compute that certain number? Trying to find a decimal representation of a fraction?

And the x = a + E , is "x" an integer with a decimal? The "E" is supposed to be the decimal part? And if you further try to find out what E is, if you replace it with E^-1 aren't we changing the value we are looking for? Fir instance if you try to find 743/500 = 1.486 if you do 1/.486 you change it to 2.057613169.

 

[fresh_42]

What context would you compute that certain number?

In any context you want to calculate with that number, e.g. $\pi, \pi^2, \sqrt{2}$. What are the first 200 digits of $\pi$?

Trying to find a decimal representation of a fraction?

Trying to find a representation at all, a calculation instruction.

And the x = a + E , is "x" an integer with a decimal?

$x$ is any real number, "integer with a decimal" makes no sense.

The "E" is supposed to be the decimal part?

Yes, the digits less than one.

And if you further try to find out what E is, if you replace it with E^-1 aren't we changing the value we are looking for?

No. We have $x=a_0+\xi_0=a_0+ \dfrac{1}{\xi_0^{-1}}$, i.e. we divided twice: once to get a number greater than one again, and twice by writing this number as $1/ \ldots$

Fir instance if you try to find 743/500 = 1.486 if you do 1/.486 you change it to 2.057613169.

That's why we get continued fractions in the representation. We have to reverse the reciprocal again. Try it with $\dfrac{157}{68}\,.$

 

[Stephen Tashi]

It seems to me that you get this "thing" when you follow an algorithm specifically designed to give you that thing, as opposed to it arising naturally, or authentically, stemming from some deeper interpretation.

A frequent application is when you know the "thing" $x$ and you want to find the value of a function evaluated at $x$, such as $e^x$ or $sin(x)$. This can often be done by evaluating a power series in $x$. A power series can often be expressed as continued fraction. The continued fraction may or may not be more useful for computing the numerical value of $f(x)$, but expressions using continued fractions look more mysterious and impressive than power series - at least to me and typical math students because we were introduced to Taylor series in introductory calculus classes.

If you are familiar with Taylor-McLaurin series, you know that it's often the case that a function $f(x)$ can be written as a power series. This allows functions (like $e^x$) to be written in the form $f(x) = c_0 + c_1 x + c_2 x^2 + ...$.

For many "famous" functions like $e^x$, $arctan(x)$ etc. it is the case that the coefficients $c_i$ can be written as infinite products in the form:

$c_0 = a_0$
$c_1 = (a_0)(a_1)$
$c_2 = (a_0)(a_1)(a_2)$
...
where the $a_i$ are factors involving only constants and powers of $x$.

(I don't have any insight about why this happens. Perhaps some other forum member can explain if this is a rare property of functions or whether most infinitely differentiable functions can be expressed this way.)

In such a case, the function $f(x)$ can then be expressed as a continued fraction using a discovery of Euler.
The current Wikipedia artice on that topic is: https://en.wikipedia.org/wiki/Euler's_continued_fraction_formula
I haven't read the article in detail. If you want to discuss the article, I'm sure members of the forum can help.

 

[John3509]

In any context you want to calculate with that number, e.g. $\pi, \pi^2, \sqrt{2}$. What are the first 200 digits of $\pi$?

It makes a bit more sense to me now as just a weird way of representing a mixed number,
I can imagine it being useful in calculating numbers if you can get the whole numbers in the denominator nest you can write out the repeated fraction and simplify it to get the number.
But, how then do you get a1,a2,a3,... to write out the fraction? And what do you do if it is not finite?

Also what about on the website where they split up the rectangle?

 

[fresh_42]

But, how then do you get a1,a2,a3,... to write out the fraction?

By the algorithm I described in post #2. Test it with $\frac{157}{68}$.

And what do you do if it is not finite?

It is finite if and only if the number is rational, a quotient of integers. If it's not finite? Well, $\pi$ isn't finite but you work with it anyway. We just have a representation that doesn't stop. Same with $\sqrt{2}$.

Also what about on the website where they split up the rectangle?

I haven't looked at it. Every quotient can generally be considered as the ratio of two lengths. The example above is not very long. You can draw the rectangles given by this example and the instructions in the video. See what it will tell you. E.g. we need the function greatest number less than , i.e. $x \longmapsto \lfloor x \rfloor$. This is geometrically a rectangle of length $x$ and height $1$, where we take the height and measure how often it fits onto the length. The small rest then is the reciprocal of our new length. Not quite sure how to proceed $x \longmapsto \dfrac{1}{x}$ geometrically.

 

[John3509]

By the algorithm I described in post #2. Test it with $\frac{157}{68}$.

I know how to turn the mixed number into the continued fraction. I am talking about going the other way. This is the only way I can see a continued fraction be useful for computing something. Let's say you don't know the value is $\frac{157}{68}$ and that is what you are trying to find. Some how you figure out a1, a2, a3... , you write out the continued fraction, collapse it by simplifying it, and you see the result you are looking for is $\frac{157}{68}$

But where do you get a1, a2, a3... first from?
Unless the only way is to first know the original fraction $\frac{157}{68}$ , if that is the case then I see no advantage of reweighting $\frac{157}{68}$ as a continued fraction.

See what it will tell you. E.g. we need the function greatest number less than , i.e. x⟼⌊x⌋x⟼⌊x⌋. This is geometrically a rectangle of length xx and height 11, where we take the height and measure how often it fits onto the length. The small rest then is the reciprocal of our new length. Not quite sure how to proceed x⟼1xx⟼1x geometrically.

Im not sure what you mean here. let's say your value is 2.3, the greatest integer less than is 2. So the rectangles Hight will fit into its length 2 times with .3 left over. What is .3 the reciprocal of? 10/3? what new length? what do you mean by x -> (1/x) ?

 

[fresh_42]

But where do you get a1, a2, a3... first from?
Unless the only way is to first know the original fraction $\frac{157}{68}$ , if that is the case then I see no advantage of reweighting $\frac{157}{68}$ as a continued fraction.

If we do not have $\frac{157}{68}$ and do not know the $a_i$ then what do we have to start in the first place? The decimal representation with a long period? In this case we would first calculate $\frac{157}{68}$. But what for? The continued fraction is just one possible representation of numbers. It has some interesting properties, which is why people investigated it, and it's useful in some cases for irrational numbers.

Im not sure what you mean here. let's say your value is 2.3, the greatest integer less than is 2. So the rectangles Hight will fit into its length 2 times with .3 left over. What is .3 the reciprocal of? 10/3? what new length? what do you mean by x -> (1/x) ?

I meant the geometric translation of the step $.3 \longmapsto \frac{10}{3}$. If we started with $2.3$ then we have $2+\frac{1}{\frac{10}{3}}=2+\frac{1}{3+\frac{1}{3}}$. The "new length" after the first step is $\frac{10}{3}$, yes. But as I said, I haven't watched the video.

 

[Stephen Tashi]

But where do you get a1, a2, a3... first from?

Look at the link given in post #6. Look at the example in that article that uses $arctan(1) = \frac{\pi}{4}$. We begin by knowing the representation for $x = 1$ and are able to find the continued fraction representation for $\frac{\pi}{4}$.

In the link that you yourself gave in post #`1, look at section 6 Continued fractions for square-roots. In that section the article finds the repesentation for $\sqrt{5}$ without knowing a1, a2, a3 first.

 

[John3509]

Look at the link given in post #6. Look at the example in that article that uses $arctan(1) = \frac{\pi}{4}$. We begin by knowing the representation for $x = 1$ and are able to find the continued fraction representation for $\frac{\pi}{4}$.

In the link that you yourself gave in post #`1, look at section 6 Continued fractions for square-roots. In that section the article finds the repesentation for $\sqrt{5}$ without knowing a1, a2, a3 first.

I overlooked your original post because my knowledge of sequences and series is poor. Am I going to have to put my investigation of continued fractions on hold till I learn that?

But from the looks of it, it can be done. I stopped the fraction at 5 iterations and computed it and got a very close representation of sqrt5. I am guessing we can get an as close we want by doing more iterations?

And this is possible with any equation where you have variables on both sides? Instead of trying to isolate the variable on one side we can just get it x = f(x) and rewrite it as a continuous fraction, cut it off after a certain amount, and get a good estimation? This seems like a very powerful method for engineering where only a decimal to few significant figures is of practical importance, that i have never been thought in school, wow.

Does this have anything to do with the Newton raphson method? Since the algorithm requires you to plug in your previous result, into the equation we can just plug in the same equation with n-1 into the x value and again with n-2 and have a long nest.

 

[Stephen Tashi]

I overlooked your original post because my knowledge of sequences and series is poor. Am I going to have to put my investigation of continued fractions on hold till I learn that?

Students needing to learn mathematics in an orderly fashion must study all the prerequisites for a course before taking the course. Some people are driven to thoroughly understand technical topics. Hence they must master all relevant prerequisites when studying something. If you find yourself in either of those situations then, yes, you should study the standard topics in sequences and series - before or along with your study of continued fractions.

I myself am not so fastidious. I'm not a student now and it doesn't bother me to study things in a haphazard fashion.

But from the looks of it, it can be done. I stopped the fraction at 5 iterations and computed it and got a very close representation of sqrt5. I am guessing we can get an as close we want by doing more iterations?

I think so, but I haven't tried to prove it.

And this is possible with any equation where you have variables on both sides? Instead of trying to isolate the variable on one side we can just get it x = f(x) and rewrite it as a continuous fraction, cut it off after a certain amount, and get a good estimation?

The case of $\sqrt{5}$ is special. In that example, $x = f(x)$ has an expression for $f(x)$ where $x$ appears in the denominator of a fraction. You can't count on $x = f(x)$ implying a continued fraction representation unless $f(x)$ is given by an expression that involves fractions.

Does this have anything to do with the Newton raphson method?

Declaring that one part of mathematics has nothing to do with another is risky. People discover surprising connections!
Offhand, I don't know a direct connection between continued fractions and solving the general equation $f(x) = 0$ by the Newton-Raphson method.

There may be some connection for particular $f(x)$. How would you solve $x^2 - 5 = 0$ by the Newton-Raphson method? Can the sequence of estimated roots be written as a continued fraction? I don't know. It's something to think about.

 

[John3509]

I think I get it, although the Newton Raphson method may not be able to be written as a continued fraction what I am thinking of nesting in general, since in the place of x_0 you can plug in the formula with x0-1 and repeat. You can't solve (x^2)-5=0 as a continued fraction tho, i tried (x*x)=5 , x=(5/x) , x=(5/(5/x)) , (5/(5/(5/x))) , 5/5/5/5/5/5/5/... and it yields nothing, but it have tried it on other quadratic functions and it did work on those so I guess it works for some not all.

Regarding section (1.1 A jigsaw puzzle: splitting rectangles into squares), do you have any interpretation of this?

 

[Stephen Tashi]

Regarding section (1.1 A jigsaw puzzle: splitting rectangles into squares), do you have any interpretation of this?

I only see it as a procedure - perhaps a game: Divide a rectangular area into a whole number of identical squares plus a rectangular remainder area. Then express the remainder area as a whole number of identical squares (of a smaller size than previously used) plus another rectangular remainder area and keep continuing this process.

However, one might consider representing an area as a decimal number as a procedure or game, except we are expressing it as a sum of squares whose areas are ...001, .01, .1, 1, 10, 100, ...etc. This procedure produces a representation that is useful in calculations.

Section 1.3 points out that a continued fraction can be written as list of numbers. Section 2.2 says that given the list that represents x, it is easy to find the list that represents 1/x.

If you have a lively mathematical imagination, you can daydream this way: Various functions f(x) can be defined by algorithms that operate on the digits of numbers. For example f(x) = x + 5 can be implemented by the algorithm we learn for adding the digital representation of numbers. Suppose we invent some algorithms that transform two lists of numbers to a third list numbers. If we interpret these lists as continued fractions, what kind of binary operations would these algorithms represent? What kind of mathematical functions could we define using the binary operations?

 

[Stephen Tashi]

Regarding section (1.1 A jigsaw puzzle: splitting rectangles into squares), do you have any interpretation of this?

The article eventually presents the jigsaw puzzle as a graphical way to visualize Euclid's algorithm for find the greatest common divisor of two integers. To me, this connection isn't obvious just by looking a the figures. I have to convince myself by text based examples.

For example, consider 990 and 84

From the viewpoint of the Euclidean Algorithm:

Divide 990 by 84: 990 = (11)(84) + 66
Divide 84 by 66: 84 = (1)(66) + 18
Divide 66 by 18: 66 = (3)(18) + 12
Divide 18 by 12: 18 = (1)(12) + 6
Divide 12 by 6: 12 = (2)(6) + 0
The GCD of 990 and 84 is 6.


For a continued fraction , we use the equivalent equations:

990/84 = 11 + 66/84 = 11 + 1/(84/66)
84/66 = 1 + 18/66 = 1 + 1/(66/18)
66/18 = 3 + 12/18 = 3 + 1/(18/12)
18/12 = 1 + 6/12
12/6 = 2 + 0/6

The continued fraction comes from starting with
990/84 = 11 + 1/(84/66)
and then replacing (84/66) by 1 + 1/(66/18)
and then replacing (66/18) by 3 + 1/(12/18)
and then replacing (18/12) by 1 + 1/(12/6)
and then replacing 12/6 by 2Solving the jigsaw puzzle begins by dividing a 990 by 84 rectangle into squares of size 84 by 84. We don't see (84)(84) = 7056 in the above arithmetic, but it appears if we write the product (990)(84) as:

(990)(84) = ( 11(84) + 66) (84) = 11 (84)(84) + (66)(84)
giving 11 whole squares of 84 by 84

The area 66 by 84 is divided into squares 66 by 66 as (66)(84) = (66)( (1)(66) + 12)
giving 1 whole square of size 66 by 66

and so forth.

You can see the sequence 11, 1, 3, 1, 2 appearing in the successive steps of all three approaches.

 

[John3509]

Thanks!