During this I stumbled on an article about How to calculate Pi by Throwing Frozen Hotdogs.
http://m.wikihow.com/Calculate-Pi-by-Throwing-Frozen-Hot-Dogs
This is more correctly known as the Buffon's Needle.
Buffon's Needle is a technique that uses the probability of throwing a needle onto a grid where the grid is spaced at the length of the needle. From this an estimate of Pi can be made.
There is mathematics behind this and I am not even going and try and explain why this works, but for those interested, you can read about it here.
http://en.wikipedia.org/wiki/Buffon%27s_needle
Obviously this was crying out for an Excel implementation.
I mean, "Who doesn't want to throw hotdogs with Excel!"
The Setup
The technique of estimating Pi by throwing hotdogs onto a grid involves marking out a grid on the floor with grid lines spaced equivalent to the length of the hotdog.
You then randomly throw hotdogs onto the grid and tally up the number of hotdogs that cross a grid line.
Pi is then estimated as the Total number of Hotdogs /Number of Hotdogs that cross a grid line/2.
In Excel, I originally thought of using a chart, but adding new series to a chart requires VBA.
I also wanted to be able to throw many thousands of hotdogs and most chart types have a limit of 255 series, although the number of points can be much greater than 255. I also needed the ability to rotate each hotdog individually.
I considered doing it all in VBA and drawing hotdogs on a UserForm, but that just seems too non-Excel.
I finally settled on using a Worksheet Range as the Grid, where I could obviously set the Row Spacing as the Hotdog's length.
I decided on a hotdog length of 50. This allowed for 10 Rows in the Grid and left room for user controls and result monitoring charts on a worksheet that would fit on most displays.
Excel doesn't have a Hotdog Drawing tool, but it does have a basic Drawing facility and so a straight line will suffice as a hotdog.
By using a Line I can use VBA to calculate its starting position and rotation as well as the color and line thickness, and then draw the hotdog.
It is a shame that although I can manually select a HotDog and change the Line Ends to be round, this functionality hasn't been included into the VBA Object Model and so we are left with straight lines with flat ends as hotdogs.
Maybe they have just been trimmed by the VBA Hotdog vendor?
Once a hotdog is thrown we need to accumulate some statistics.
Simplistically I only need to know the number of hotdogs that cross/touch a grid line and that could be simply accumulated as each throw occurred.
But once I started I couldn't help myself and added the history and cumulative Pi value and variance from Pi as charts. I also colored the hotdogs according to there location Red for Hotdogs that Crossed a grid line and Green Hotdogs for those that missed a gridline.
The remainder of this post will examine the techniques used for each section.
Simulation
The basic of the simulation are as follows
- Setup Grid
- Throw a random Hotdog
a. Choose a random centroid X, Y and Rotation for a Hotdog3. Repeat step 2
b. Calculate X & Y position of each end
c. Check if the Hotdog intercepts a line
d. Draw the HotDog
e. Record the throws status
f. Tally results
4. Calculate Pi
Of course this could all be done in memory. There is no need to display the hotdogs. Displaying them will definitely slow down the process. But wouldn't that be boring !
Setup a Grid
Excel uses an orthogonal grid starting at 0,0 at the Top Left corner of the A1 Cell. X values increase to the right and Y values increase down the worksheet.
I originally decided to have grid of 10 rows of size 50pts, which is 500pts. This allows for space above/below for inputs, controls and stats. I was going to use a Hotdog length of 50.
But in Excel 2010 using a standard Calibri Font, I could only get an odd 49.5 pts Row Spacing (66 pixels). Close enough and I can use that as a variable in VBA when I check the hotdogs location, more on this later.
Setup Code
To ensure the grid is correctly calibrated a small piece of VBA is used to setup the Row sizes
It only need to be used once on a PC or after people change the view zoom or row /column sizes etc, just to make sure everything is setup correctly.
Sub Setup()The Column sizes aren't important but from an aesthetic point of view it looks better if the hotdogs are within a defined area.
Const HotDogLength As Double = 49.5
Worksheets("Throw").Select
Range("A1").Select
Application.ScreenUpdating = False
'Cleanup old hotdogs
CleanUp
'Setup the Throw Sheet
Columns("A:A").ColumnWidth = 1.43
Columns("B:K").ColumnWidth = 10
Rows("1:5").RowHeight = 19.5
Rows("6:17").RowHeight = HotDogLength
Rows("18:1048576").EntireRow.Hidden = True
With Range("B6:K15")
.Borders(xlDiagonalDown).LineStyle = xlNone
.Borders(xlDiagonalUp).LineStyle = xlNone
With .Borders(xlEdgeLeft)
.LineStyle = xlContinuous
.ThemeColor = 2
.TintAndShade = 0
.Weight = xlMedium
End With
With .Borders(xlEdgeTop)
.LineStyle = xlContinuous
.ThemeColor = 2
.TintAndShade = 0
.Weight = xlMedium
End With
With .Borders(xlEdgeBottom)
.LineStyle = xlContinuous
.ThemeColor = 2
.TintAndShade = 0
.Weight = xlMedium
End With
With .Borders(xlEdgeRight)
.LineStyle = xlContinuous
.ThemeColor = 2
.TintAndShade = 0
.Weight = xlMedium
End With
With .Borders(xlInsideVertical)
.LineStyle = xlContinuous
.ThemeColor = 1
.TintAndShade = 0
.Weight = xlMedium
End With
End With
Range("Runs") = 200
Range("Runs").Select
Application.ScreenUpdating = True
End Sub
Only the Hotdogs Y value is required or used for checking the hotdogs location, This will be discussed later.
The Main Simulation
The Main VBA code runs through the steps of the simulation as described above
2. Throw a random Hotdog
a. Choose a random centroid X, Y and Rotation for a Hotdog
b. Calculate X & Y position of each end
c. Check if the Hotdog intercepts a line
d. Draw the HotDog
e. Record the throws status
f. Tally results
a. Choose a random centroid X & Y position and Rotation for a Hotdog
For each throw of a hotdog we need to calculate a random X, Y coordinate of the centroid of the hotdog and a random rotation of the hotdog between 0 and 2 x Pi Radians
'Calc start pos
Randomize
xc = XOffset + Rnd() * 10 * HotDogLength
yc = YOffset + 10 * HotDogLength * Rnd()
Rot = Rnd() * 2 * Pi
b. Calculate X & Y position of each end
From the Centroid, Rotation and Hotdog length we can calculate the end position of each hotdog using simple trigonometry.
'Calc end positions
x1 = xc + Cos(Rot + Pi) * HotDogLength / 2
y1 = yc + Sin(Rot + Pi) * HotDogLength / 2
x2 = xc + Cos(Rot) * HotDogLength / 2
y2 = yc + Sin(Rot) * HotDogLength / 2
c. Check if the Hotdog crosses a gridline
To check if a Hotdog crosses a grid line it is simply a matter of determining which section of the grid each end is in. If they are in different sections the hotdog crosses a line.
This is easily achieved by calculating the Integer value of the hotdogs two end Y values divided by the Grid Spacing. The YOffset is first subtracted to normalise the data .
If Int((y1 - YOffset) / HotDogLength) = Int((y2 - YOffset) / HotDogLength) Then
Worksheets("Results").Cells(same, 1) = i
HotdogColor = RGB(0, 255, 0) 'Green
Worksheets("Results").Cells(i + 1, 6) = -10
same = same + 1
Else
Worksheets("Results").Cells(cross, 2) = i
HotdogColor = RGB(255, 0, 0) 'Red
Worksheets("Results").Cells(i + 1, 6) = 10
cross = cross + 1
End If
d. Draw the Hotdog
Once the code has determined if the Hotdog is a Red(Crosses a gridline) or Green (Is between the gridlines) we can draw the hotdog. The drawing is outsourced to a small subroutine to simplify the code flow.
Sub DrawDogs(x1, y1, x2, y2, HotdogColor)
'Draw Hotdog
ActiveSheet.Shapes.AddConnector(msoConnectorStraight, x1, y1, x2, y2).Select
With Selection.ShapeRange.Line
.Visible = msoTrue
.Weight = 6
'.capType = msoRound ??? come on MS Guys complete the Object Model
.ForeColor.RGB = HotdogColor
End With
Application.ScreenUpdating = True
End Sub
The function is called by simply calling the DrawDogs subroutine which requires the X & Y values for each end of the dog as well as the Hotdogs color
Call DrawDogs(x1, y1, x2, y2, HotdogColor)
e. Tally results
To calculate Pi using this technique we simply need the tally of the Number of Hotdogs that cross a Gridline and the Total thrown
I decided early on in the design of the workbook that keeping records of which throw was a Cross or Miss may be useful and so 2 columns are setup to store these.
All results are stored on the Results sheet
Columns A & B keep a record of which throw is which type of throw
Column E stores the running Pi and Column F is used for the display of the individual
Display Results
6 measures are monitored on a throw by throw basis
1. The individual hotdog status as Red (touches a gridline) or Green (sits between gridlines)
2. The Throw No.
3. The Current estimate of Pi
4. The Historical Estimate of Pi vs Pi
5. The Variance from Pi as a percentage of Pi
6. The historical throw Status of each throw as either Cross or Not-Crossed
A number of Named Formula are used to convert the data to a suitable format for charting.
The Named Formula are then used directly in the various charts.
These include:
Worksheet Storage Names | |
Runs | =Throw!$D$2 |
Iteration | =Throw!$H$2 |
Summary Names | |
Cross | =COUNT(OFFSET(Results!$B$2,,,COUNTA(Results!$B:$B)-1,1)) |
Same | =COUNT(OFFSET(Results!$A$2,,,COUNTA(Results!$A:$A)-1,1)) |
Calculated Names | |
i | =OFFSET(Results!$D$1,1,,COUNTA(Results!$D:$D)-1,1) |
PiEst | =OFFSET(i,,1) |
Ind | =OFFSET(i,,2) |
PiAct | =PiEst*0+PI() |
PiVar | =(PiEst-PI())/PI() |
The above Named Formula are used to transfer the results into the charts on the Throw Worksheet.
Remove Hotdogs
Prior to a simulation run it is good practice to remove the existing hotdogs from the floor and so it is in the Excel implementation.
This is achieved by using a small piece of VBA code.
Sub CleanUp()The code loops through the shapes in the Shapes collection and if not named "Chart" or "Button" deletes it
Dim Shp As Shape
Worksheets("Throw").Select
For Each Shp In ActiveSheet.Shapes
If Left(Shp.Name, 6) <> "Button" And Left(Shp.Name, 6) <> "Chart " Then
Shp.Delete
End If
Next Shp
Worksheets("Results").Range("A2:B10000").ClearContents
Worksheets("Results").Range("D3:F10000").ClearContents
Worksheets("Results").Range("F2").ClearContents
[Iteration] = 0
[Iteration].Select
End Sub
It also resets the Results sheet.
Download
You can download a copy of this file which has only been tested in excel 2010 and 2013 from Download File
Closing
I hope you enjoy this implementation in Excel of the Buffon's Needle provided by Hui, proving that indeed Excel can throw Frozen Hotdogs with the best of them.
I have ran this many times with up to 10,000 hotdogs without issue, however from time to time I have experienced an issue where Chart 3 becomes invisible. If this happens simply close the file without saving and re-open it.
If you work out why please let me know.
About Hui
Hui is a Consulting Mining Engineer by profession and guest author at ExcelHero Blog and Chandoo.org.
Hui received a Microsoft MVP award (Excel) in 2013 and 2014.
Hui has published over 100 posts about all things Excel at:
@ ExcelHero Blog
Counter-Intuitive Illusory Contours
@ Chandoo.orgAbout Hui
Recent Comments