As you can see from the image, it starts with 1 (or 1/1) at the top. The left side is less than 1 and the right side is more than 1. Once you choose a side; its' children are then less/more than that node.
Ok, that looks cool -- but what can we do with it?
We can use it to make a simple continued fraction for any positive number (decimal, fraction or whole number). We could probably expand it to handle negative numbers by starting at 0 instead of 1, but then we'd have to revisit the division-by-zero post.
The simple continued fraction is simply the continued fraction that has a '1' for all the partial numerators. Let's look at a simple example of how we can convert a decimal number into a continued fraction through use of the Stern-Brocot tree.
For this example, let's start with a simple decimal... Let's say, 1.25.
To convert the decimal to the SB tree, we'll walk down the tree and record our chosen path with 'L' for left and 'R' for right.
We start with the 1/1. Since 1.25 > 1/1, we choose the Right side of the tree.
Next choice: Since 1.25 < 2/1, we choose the Left path.
Next, 1.25 < 3/2, so again we choose the Left path.
Next, we chose Left for 1.25 < 4/3.
Last, we choose Left for 1.25 = 5/4 and we are done.
So, in order, we chose RLLLL.
We could also write that we chose R1L4.
But how do we translate that to a continued fraction? We just use the exponents!
Note: If we were using a number lower than 1 as our target, we'd put a '0' in front of that (like [0;1,4] which is actually the inverse; or 4/5).
The process is easily reversible as well. Let's say we started with that Continued Fraction of [1;4].
First, we need to know whether to start with Left or Right. If the first digit is 0, choose Left; otherwise choose Right. So, for [1;4] we choose Right.
We remember that the number are the exponents; and that it will always alternate. So [1;4] becomes R1L4 .
The exponents represent a count of how many of that letter to choose; so that becomes [R][LLLL] or RLLLL.
Walking down the SB tree, we choose in order: 1/1, 2/1, 3/2, 4/3, 5/4.
Ok, that is all well and good... but that tree only shows a few rows; what do we do when it runs out?
The process for generating the next row isn't so bad when you see it paired with the continued fractions.
Below 5/4 for example:
5/4 = [1;4]
assuming that is in the form [a0;a1,a2,...,ak] the two children are:
[a0;a1,a2,...,ak+1] on the left and [a0;a1,a2,....,ak-1,2] on the right
Or in our particular case:
[1;4+1] = [1;5] = 6/5 = 1.2 on the left
[1;4-1,2] = [1;3,2] = 9/7 = 1.2857142857142858 on the right
and it is easy to verify that 1.2 < 1.25 < 1.2857...
or that 6/5 < 5/4 < 9/7
One more simple example in honor of 1:59 tomorrow....:
RRRLLLLLLLRRRRRRRRRRRRRRRLRRRRRRRRRRRRRRRRRRRRRRRRRLRRRRRRRLLLL
[3;7,15,1,25,1,7,4]
314159/100000 = 3.14159
2 comments:
What's more... assuming a particular parent is x/y; the children a/b and c/d will result in (a+c)=3x and (b+d)=3y.
I am surfing and I found this impressive blog,I like your way to describe about equation without solution.t want to discuss a simple definition regarding this as-Rational numbers can be whole numbers, fractions, and decimals. They can be written as a ratio of two integers in the form a/b where a and b are integers and b nonzero.
Post a Comment