Maths Problems 3C: Estimating pi by sampling

In response to my first post about pi, my friend Chris Timbey pointed out that he's previously written a computer program which will estimate pi by determining if a random point in a square is also in a quadrant drawn within that square.  The diagram below shows how this would work.

Not only is pi the ratio of a circle's circumference to its diameter (C = pi x d), but the area of a circle is pi r², so we have another way of approximating the value of pi.

The cartesian equation (using x and y) for a circle is x² + y² = 1. By taking random values of x and y and determining if the value of x² + y² is greater than or less than 1, we can calculate the ratio of the area of the quadrant to the area of the square.

This is where a computer comes in very handy.  The basic program works thus:
1.  Obtain random values of x and y between 0 and 1.
2.  Square x and y, and sum the two values.
3.  If the sum of x² + y² is less than 1, then count this as 'within the quadrant', otherwise count it as outside the quadrant.
4.  Repeat the first three steps a large number of times.
5.  Calculate the proportion of counts 'within the quadrant' to the total number of counts (both inside and outside the quadrant).
6.  Multiply this proportion by 4, since there are four quadrants in a circle.

For example:
Random value of x = 0.252
Random value of y=0.881
x² + y² = 0.840 so this is within the quadrant.

This takes a large number of iterations to produce an accurate result.

Here are my results; iterations on the left, value of pi on the right:
100  -  3.08
200  -  3.12
1000 - 3.212
5500 - 3.167272 (recurring)
10,000 - 3.13040, also 3.1736, 3.1312  (repeating the experiment with 10,000 new random pairs).
15,000 - 3.13040 (11739/15000)
Beyond this, my spreadsheet starts grinding to a slow and painful halt, but at least by 10,000 iterations it's mostly hitting pi to one decimal place.  This will always be an approximation, since it's based on a fraction (no matter how precise), and pi, being an irrational number, doesn't much like being expressed as a fraction!

Next time - approximation of pi based on a regular polygon with thousands of sides.

My Series on Determining The Value Of Pi

1. An upper limit on the value of pi
2. A lower limit on the value of pi
3. Approximating pi by sampling
4. Approximating pi using an infinite polygon

Mathematical Problems 4: Close packed circles

While I was at university, I remember studying close-packed spheres and how they form in crystalline structures.  We were given the figure that close-packed spheres occupy the largest proportion of space available - more than they'd fill if they were arranged in squares, for example.

To explain what close-packed circles look like, here's a diagram.

Sometimes, they're described as hexagonally close-packed; as you can see from the diagram, the circles form hexagonal arrangements.  This makes it easier to calculate how much of the area the circles are filling... especially if we break the hexagon down into equilateral triangles...

Now, the triangle marked in bold contains three sixths of a circle - half the circle, in other words, which has an area of A = 0.5 x pi r²

The triangle is an equilateral triangle (all sides are equal, all angles are equal at 60 degrees).  I don't know any shortcuts for working out the area of an equilateral triangle, so I'll do it long hand:

Area = base x height x 0.5

The base = the diameter of a circle = 2 r
The height is found through trigonometry:  tan 60 = h / r   therefore h = r tan 60

Area = 2 r x r tan 60 x 0.5

Area of triangle = r² x tan 60

Area of half a circle (contained within the triangle) = 0.5 x pi x r²

The proportion of the triangle's area which is covered by the semi circle = area semicircle / area triangle

Proportion = 0.5 x pi x r²  / r² x tan 60  and the r² cancel, so proportion = 0.5 pi / tan 60

pi / 2 =1.5707

tan 60 = 1.732

Proportion = 1.5707 / 1.732 = 0.9069 which is 91%.

Now I accept I haven't worked it out for packing by spheres in space, but I thought I'd start simple and work from there...  maybe next time!

Mathematical Problems, 3B - A lower value of Pi

Returning to pi, and this time using geometry to calculate a minimum value.  Instead of using a square around the outside of a circle, this method will use a square within a circle.  Last time we looked at square ABCD, this time, it's WXYZ.

Now the circumference of the circle is greater than the perimeter of WXYZ.  We know this for sure because the shortest distance between two corners of a square is the straight line that connects them, and the circle is a curved line and therefore must be longer.

If we call the centre of the circle O, then we can see that WOX is a right-angled triangle, and WO = OX = radius of the circle.

Using Pythagoras, we can determine the length WX:

WX ² = WO² + OX²

And since WO = OX = radius of the circle, r, then WX² = 2 r²
And WX = sqrt (2 r²)  = sqrt 2 x r

Now, the full perimeter of the square is four times WX (since the square has four sides),
4 WX = 4 sqrt (2 r²)  = 4 x sqrt 2 x r

We want to describe pi in terms of the diameter of the circle, not the radius, so substitute d = 2r and this gives

Perimeter of square (4 WX) = 4 x sqrt 2 x d/2
Perimeter of square = 2 x sqrt 2 x d

We know the circumference of the circle is pi x d
The perimeter of the square is 2 x sqrt 2 x d
Therefore, pi is greater than 2 x sqrt 2  (approximately 2.82)

Combining this with the result from the previous post gives us the approximation

2 sqrt 2< pi < 4

In my next post, I'll work out how to use superscripts and square root signs in HTML (I hope) and I'll show a way of approximating pi using statistics rather than geometry.  In a future post, I'll also look at close-packed circles, and calculate how much of the available area they can fill, then extend this to close-packed spheres.

My Series on Determining The Value Of Pi

1. An upper limit on the value of pi
2. A lower limit on the value of pi
3. Approximating pi by sampling
4. Approximating pi using an infinite polygon

Mathematical Problems, 3A - The Value of Pi

Back when I was doing my A-levels, I remember learning about how it's possible to evaluate pi in various ways, one of which was through calculus.  I can only remember the basics, and I'm sure I can't recall how to do it now - at least not without some help!

The value of pi is the ratio of the circumference of a circle (the distance all the way around the outside of the circle) divided by the diameter (the straight-line distance from one side to the other, through the centre).  It's been known historically to be about 3, but I'm going to make some approximations from first principles.

Firstly, drawing a square around a circle, so that the square touches the circle.  See the diagram above, with the square ABCD around the circle.

If the diameter of the circle is d, then the perimeter of the square is 4d.  We can see by inspection that the square's perimeter is longer than the circle's circumference, and we've called the circumference pi d.  Therefore, we know that pi is less than 4.

It's not a dramatic result, I know, but it's a start!

Next, we need to look at setting a minimum value for pi, and we'll look at this next time.

My Series on Determining The Value Of Pi

1. An upper limit on the value of pi
2. A lower limit on the value of pi
3. Approximating pi by sampling
4. Approximating pi using an infinite polygon

Mathematical Problems, 2 - The Tetrahedron Path

In this article, I want to provide another puzzle, and the solution to it (you'll need to look closely at the diagram below to understand the solution).  This follows on from my previous post, which was a puzzle about a spider and a cube.  The spider was a mathematical spider, and she wanted to walk around all 12 edges of a cube, in both directions (i.e. from left to right and then right to left) in a single continuous path, without getting stuck or having to turn around completely.  In the original puzzle (devised in a BBC Micro maths adventure game), you had to tell the spider to turn either left or right at each corner.  Now I'm a little older, I use a pen and paper and a diagram...

Following on from the cube, I set myself the challenge of doing the same for a tetrahedron.  I can't say if it was significantly harder or easier, perhaps a little easier with fewer edges to follow, but here's the solution.  The path through the letters goes along each edge twice, once in one direction and then later in the opposite direction, starting and finishing at the same point.

My next post will be a brief discussion on how to calculate a very approximate value of pi from first principles (by which I mean a few diagrams and some basic geometry).  After that, I'll use a different method to get the value of pi, and we'll see how that goes.  If you're looking for more information about tetrahedra, I can recommend this post where I calculate the tetrahedral bond angle.

Here's my solution to the tetrahedron path puzzle: follow the letters in sequence.  

Mathematical Problems, 1 - The Cube Path

Now that the X-Factory has finished its on-screen cash-making routine, I'm returning to more interesting and productive matters - in this case, a mathematical problem that I first came across nearly 20 years ago.  Yes, I'm that old.

This puzzle was posed as part of a text-based adventure game (remember them?) with a strong mathematical bias - you had to solve certain problems in order to progress through the game.  If I remember rightly, for each part you solved, you were given an item or a shape that would come in useful later in the game.  The game was on the school's Maths Club's BBC Micro, and although I can't remember what it was called, there was one puzzle which I didn't solve at the time (although a friend of mine, James Leeson,did, after we started working on it together).  The puzzle recently resurfaced in my mind earlier this week, and I sat down to apply myself to solving it.

Anyways, enough preamble.  In the game, you met a spider, who had a challenge.  She wanted to walk along each of the 12 edges of a cube in a single continuous path that would take her along each edge twice - once in each direction.  You weren't allowed to go directly back on yourself (i.e. reverse) but at the end of each edge, you had to type in if you wanted to turn left or right.  Although the problem didn't specify that you had to start and finish at the same point, this becomes evident through the symmetry of the problem.  And you have to walk along each edge twice (once in one direction, and once in the reverse) otherwise you're guaranteed to hit a dead end.

I can't say much about the theory behind the solution - or if there's more than one solution - but here's mine (and I'm quite proud of it, nearly two decades later).  Start with A and follow each letter sequentially.  If you label each edge with an arrow as you go along, you'll see that it's a valid solution.

Next time... the same puzzle for a tetrahedron!

Cheryl vs Wagner, 21 November 2010

Well, it's good to see the X Factory machine in full swing.  Last Saturday's X Factory Pantomime was filled with all the usual comments, criticisms and crowing that we've come to expect, and in addition, they even managed to get Jeremy Kyle's audience in too.

Big news was of course Cheryl Cole's desperate attempt to undermine Wagner's fanbase.  Realising that her acts are rapidly losing ground, popularity and votes, she's had to change her tactics in order to try and get him voted out of the show.  I'm pleased to see that it completely failed.  So, she, "doesn't normally have any constructive criticism," for him?  Why should this week be any different, eh, Cheryl?  That wasn't constructive criticism, that was a failed character assassination.  So Wagner pointed out that she used to live in a council estate and she's very lucky.  Her transparent, "You should think about how lucky you are," was a thinly veiled threat, and I'm happy that it didn't work.  Instead, with good grace, Wagner managed to completely turn the tables on her, and came up smelling of roses.

Of course, I'm biased.  Yes, The Sun reports it differently, but the fact remains that Wagner is still in, and this little escapade by CC has not done enough to dent his increasingly loyal fanbase.  I'd have liked to have seen Louis take the sing-off to deadlock, instead of eliminating Paije - if only because it increased the chance of Cheryl losing *another* act, the uninspiring rapper, Cher.

Still, Wagner remains, the votes count must be climbing, and we saw an inspired use of the, "No particular order," line.  More on that next time.