A couple years ago, I wrote a post entitled Demystifying pi. Since that time, Google Code decided to shut down hosting, so I decided to take a fresh look at it.
Here's a presentation and the new minimal code.
Showing posts with label Continued Fractions. Show all posts
Showing posts with label Continued Fractions. Show all posts
10 June 2015
15 October 2013
Demystifying pi
One of my pet peeves is that we routinely teach kids that things are impossible, unknowable, too complicated, et cetera. Another is when our equations are dirtied with exceptions to rules...
One example of this was my implementation of pi. That in turn was based on a modification of the continued fraction library to be a bit cleaner in the implementation.
It bugged me that my implementation of pi started with an exception. My numerator at index=0 was 22. Something was not quite right - but what was it?
So I thought, well, the number in that position should be 02... but then the continued fraction starts with 0 + 0/ ... That seemed kinda redundant and pointless.
What if we started with index=1? All the sudden, this started to look a lot cleaner... [NOTE: I use 'cf' instead of 'K' to note the indexes are based on the above mentioned modification, not on Gauss's indexes]:
Ok... this is looking really clean... left side is the odd numbers... right side is the squares (or more specifically, the sum of the odd numbers up to and including the one on the left)... no exceptions to the rule, etc. very clean... but it is no longer pi.
π = 4/y.... or more specifically, in this particular case, y = diameter of the circle (⌀) which is about 1.27323954474 (etc)....
What does this mean? It means that π isn't really the important number... ⌀ is. π = 4/⌀, but ⌀ is a very simple continued fraction. π is just derived from it. Maybe if we were teaching how simple continued fractions were, π would not seem like some mystical self-aware number.
Also, to simplify describing these... instead of using LaTeX and such I think we could just specify them as the relationship between two series... For example, ⌀ = A000290::A005408. Similarly, if we wanted to define some 'constant' that was using even numbers instead of odds and the sum of even numbers instead of the sum of odds, we'd have y = A002378::A005843.
UPDATE:
Ok, I admit, the '4' in the definition also bothered me...
Extrapolating further, it appears that this is slightly more correct:
where S = perimeter of a square (ie: the 4 above is the unit square)
where C = circumference of the circle (to find)
then C = S/⌀
aka, while a 1x1 square will mean C=4/⌀; a 3x3 square will mean C=9/⌀
UPDATE:
Obviously, I have to assume that this number has already been defined. It's used everywhere. A quick Google search found nothing until I started trimming the number down. Eventually, I found a reference in The royal gauger; or, gauging made perfectly easy, as it is actually practised by the officers of His Majesty's revenue of excise. In two parts. by Charles Leadbetter. He appears to have referred to it both as "Square of the Diameter of a Circle, whose Area is Unity" as well as "The Multiplier or Multiplicator for reducing a Square to a Circle". He showed how to use it for calculating how much Ale was in a round cask, for example. For reference:
One example of this was my implementation of pi. That in turn was based on a modification of the continued fraction library to be a bit cleaner in the implementation.
It bugged me that my implementation of pi started with an exception. My numerator at index=0 was 22. Something was not quite right - but what was it?
So I thought, well, the number in that position should be 02... but then the continued fraction starts with 0 + 0/ ... That seemed kinda redundant and pointless.
What if we started with index=1? All the sudden, this started to look a lot cleaner... [NOTE: I use 'cf' instead of 'K' to note the indexes are based on the above mentioned modification, not on Gauss's indexes]:
π = 4/y.... or more specifically, in this particular case, y = diameter of the circle (⌀) which is about 1.27323954474 (etc)....
What does this mean? It means that π isn't really the important number... ⌀ is. π = 4/⌀, but ⌀ is a very simple continued fraction. π is just derived from it. Maybe if we were teaching how simple continued fractions were, π would not seem like some mystical self-aware number.
Also, to simplify describing these... instead of using LaTeX and such I think we could just specify them as the relationship between two series... For example, ⌀ = A000290::A005408. Similarly, if we wanted to define some 'constant' that was using even numbers instead of odds and the sum of even numbers instead of the sum of odds, we'd have y = A002378::A005843.
UPDATE:
Ok, I admit, the '4' in the definition also bothered me...
Extrapolating further, it appears that this is slightly more correct:
where S = perimeter of a square (ie: the 4 above is the unit square)
where C = circumference of the circle (to find)
then C = S/⌀
aka, while a 1x1 square will mean C=4/⌀; a 3x3 square will mean C=9/⌀
UPDATE:
Obviously, I have to assume that this number has already been defined. It's used everywhere. A quick Google search found nothing until I started trimming the number down. Eventually, I found a reference in The royal gauger; or, gauging made perfectly easy, as it is actually practised by the officers of His Majesty's revenue of excise. In two parts. by Charles Leadbetter. He appears to have referred to it both as "Square of the Diameter of a Circle, whose Area is Unity" as well as "The Multiplier or Multiplicator for reducing a Square to a Circle". He showed how to use it for calculating how much Ale was in a round cask, for example. For reference:
13 March 2010
Stern–Brocot tree and Continuous Fractions
This post continues the previous entries on Continuous Fractions. This time, we expand the concept to encompass the Stern-Brocot tree.
The Stern-Brocot tree is a binary search tree where the two legs represent "less than" and "more than" (or Low,High or Left,Right, etc).
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!
R1L4 becomes [1;4].
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
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
27 April 2009
Division by Zero
I've been on this kick lately where I have started question some of the basic assumptions I learned in math... things like "you can't easily define pi" or the concept of an "irrational number". Today's philosophical debate is on the idea of division by zero.
This came up because I was creating a ContinuedFraction interface for integers... The number 3, for instance, is 3 + 0/0 + 0/0 .... etc... instead of zeros I had to replace them with nulls in order to prevent the app from trying to compute the 0/0 bit... That got me thinking... maybe it should be allowed...
Let's take a simple concept. Let's say there are 10 pennies on the table, and it is decided that the pennies will be split evenly amongst everyone at the table. [Yes, pennies - I don't want anyone getting the bright idea to make change].
Now, if there are 5 people, everyone gets 2 pennies. Simple.
If there are 3 people, everyone gets 3 pennies and 1 is left on the table.
If there are no people, then there is still 10 pennies on the table.
What's so difficult about that?
So, in essence:
10/5 = 2r0
10/3 = 3r1
10/0 = 0r10
Seems like Occams Razor would say that the whole concept has been arbitrarily inflated to give us errors, exceptions and NaN.
What about the other way around?
If there are 0 pennies...
0/5 = no pennies for anyone
0/3 = same
0/0 = same
Seems like we really don't have an issue there.
Of course, this would mean that things such as limits get screwed up -- but so what. If we think we have irrational numbers, why not stir the pot a bit? Maybe they were not correctly defined in the first place.
Besides, that will open up the ContinuedFractions to more interesting options... like
This came up because I was creating a ContinuedFraction interface for integers... The number 3, for instance, is 3 + 0/0 + 0/0 .... etc... instead of zeros I had to replace them with nulls in order to prevent the app from trying to compute the 0/0 bit... That got me thinking... maybe it should be allowed...
Let's take a simple concept. Let's say there are 10 pennies on the table, and it is decided that the pennies will be split evenly amongst everyone at the table. [Yes, pennies - I don't want anyone getting the bright idea to make change].
Now, if there are 5 people, everyone gets 2 pennies. Simple.
If there are 3 people, everyone gets 3 pennies and 1 is left on the table.
If there are no people, then there is still 10 pennies on the table.
What's so difficult about that?
So, in essence:
10/5 = 2r0
10/3 = 3r1
10/0 = 0r10
Seems like Occams Razor would say that the whole concept has been arbitrarily inflated to give us errors, exceptions and NaN.
What about the other way around?
If there are 0 pennies...
0/5 = no pennies for anyone
0/3 = same
0/0 = same
Seems like we really don't have an issue there.
Of course, this would mean that things such as limits get screwed up -- but so what. If we think we have irrational numbers, why not stir the pot a bit? Maybe they were not correctly defined in the first place.
Besides, that will open up the ContinuedFractions to more interesting options... like
26 April 2009
SeriesCF
While working on my ContinuedFractions library today, it occured to me that our current representation of pi could be simplified by just specifying the numerators and denominators as series...
I went ahead and changed the implementation to use a new SeriesCF class instead of the default ContinuedFraction class and I think the new approach is much cleaner.
25 April 2009
PresenTeX
While writing this package today, I came across the PresenTeX website. Very nice...
from
from
cf = d_0 + \cfrac{n_0}{d_1 + \cfrac{n_1}{d_2 + \cfrac{n_2}{d_3 + \cfrac{n_3}{\ddots\,}}}}
10 February 2009
Continued Fractions
I was working on some continued fractions, and came across the fundamental recurrence formula above. It worked pretty well for some simple continued fractions (like √2) but seemed to be a bit unfriendly towards calculating π.
I'm using this definition of π:
Now, using that definition with the above equation, it was always completely wrong...
So I tried changing the equation...
I'm using this definition of π:
Now, using that definition with the above equation, it was always completely wrong...
So I tried changing the equation...
So you'll notice a few specific changes... 1) A1 has been redefined in terms of previous results. 2) A1 reduced the index on a1 to a0. 3) An+1 changed the index on an+1 to an. 4) Bn+1 changed the index on bn+1 to bn.This may seem like a lot of changes, but really #1 didn't change the outcome at all and the rest were all about reducing the index of a/b.
Net result? All the previous stuff (√2, golden mean, etc) give the same results as before... but now π works.
Subscribe to:
Posts (Atom)