Description
Introduction
[… A] simulation is a fictitious representation of reality, a Monte Carlo method is a technique that can be
used to solve a mathematical or statistical problem, and a Monte Carlo simulation uses repeated sampling
to determine the properties of some phenomenon (or behavior). Examples:
Simulation: Drawing one pseudo-random uniform variable from the interval [0, 1] can be used to
simulate the tossing of a coin: If the value is less than or equal to 0.50 designate the outcome as
heads, but if the value is greater than 0.50 designate the outcome as tails. This is a simulation, but not
a Monte Carlo simulation.
Monte Carlo method: Pouring out a box of coins on a table, and then computing the ratio of coins that
land heads versus tails is a Monte Carlo method of determining the behavior of repeated coin tosses,
but it is not a simulation.
Monte Carlo simulation: Drawing a large number of pseudo-random uniform variables from the
interval [0, 1], and assigning values less than or equal to 0.50 as heads and greater than 0.50 as tails,
is a Monte Carlo simulation of the behavior of repeatedly tossing a coin.
[http://en.wikipedia.org/wiki/Monte_Carlo_method]
A Monte Carlo simulation can be used as an interesting way of evaluating integrals, especially when
obtaining a closed-form solution is infeasible.
The algorithm to estimate the value of the integral ∫ 𝑓(𝑥)
𝑏
𝑎
𝑑𝑥 using a Monte Carlo simulation works as
follows:
1) Given the interval [a, b], determine the maximum value fmax that f(x) assumes within this
interval. In Figure 1, fmax = f(b).
2) Generate a series of random points (x, y)
that fall within the rectangle. In other
words, x must be within the interval
[a, b], and y must be within the interval
[0,fmax]. Some of these random points
will fall below the f(x) curve (green dots
in Figure 1), and some will fall above the
f(x) curve (red dots).
3) The value of the integral is approximated by
the total area of the rectangle multiplied by
the fraction of the number of points that fall
under the f(x) curve.
4) The greater the number of random points used in this Monte Carlo simulation the more accurate is
the estimated integral value.
Problem Specification
Implement a program using Monte Carlo simulation for estimating the following integral:
∫
12
5
x2 dx
Figure 1: The basic idea of Monte Carlo integration.
– 2 –
The program must use ten (10) threads, where each thread generates 10,000 random points.
Show the estimates of the value of the integral as calculated individually by each thread, as well as the
estimate obtained by the parent process using information it gets from all threads. Make sure the above
results are displayed in a nice, clear form.
Extra Credit (10%)
We stated above the claim that the greater the number of points the more accurate is the estimated
integral value.
Run experiments to support or reject the claim. Do not exceed 1 million points per thread.
Use one or more appropriate tables to store individual and “collective” estimates. Draw one or more
diagrams showing accuracy of the estimate as a function of the total number of points. (You can calculate
the exact value of the integral; then accuracy is simply the deviation of the estimate from this exact
value.)
Provide a brief discussion with your arguments supporting or rejecting the claim.
SLC Report Requirements
For each program write a full SOFTWARE LIFE CYCLE (SLC) report (analogous to the SLC report
presented in class).
Please note that your reporting job is easier due to the following simplifications:
1) If appropriate, the PROBLEM SPECIFICATION section (Step 1) might include just a copy of the
given problem(s).
2) The PROGRAM STRUCTURE DESIGN section (Step 2) will have a few modules to name
(Substep 2.1. Modules and Their Basic Structure), and few modules to provide pseudocode for
(Substep 2.2.Pseudocode for the Modules).
3) The sections for RISK ANALYSIS (Step 3), VERIFICATION (Step 4), REFINING THE
PROGRAM (Step 7), PRODUCTION (Step 8) and MAINTENANCE (Step 9) can include just 1-
2 sentences (analogous in the SLC report presented in class).
4) The CODING section (Step 5) should have the appropriate number of code refinement levels.
5) Due to the simple structures of the programs, the TESTING section (Step 6) should be rather
easy.
6) Using a mono-spaced fonts like (Courier New) for source code adds a significant value for
code readability and quality. Please use this type of font only for the source code in your report.
Coding, Running and Submission Requirements
1) Follow C Code Style Guide and the proper programming style it requires, including comments,
blank lines, indentations, spaces, etc.
2) All programs must be compiled and executed on Ubuntu running within the Oracle VirtualBox.
3) Remember about Assignment Submission Instructions (guidelines), to be followed for each
program of this assignment.
4) In addition to what Assignment Submission Instructions require, provide a makefile, and, if
– 3 –
needed a README file explaining how to compile and run your program.
Submission Checklist
For each program, you need to submit:
1) the SLC report (including 9 SLC steps, with as many pseudocode and code refinements as
needed);
2) makefile, and, if needed a README file explaining how to compile and run the program;
3) the files created by the script command (including program output to the terminal, if any);
4) the output files (if any in addition to the output to the terminal);
5) if you have worked on the extra-credit portion of this assignment, provide a separate file with
these extra results.
Submit your complete assignment package (all files) via Elearning as a zip file. Use
hw
hw1_Smith.zip)
——– Good luck! —–