Difference between revisions of "Kernal Blas"
(→Calculation of Pi) |
(→Calculation of Pi) |
||
| Line 10: | Line 10: | ||
=== Assignment 1 === | === Assignment 1 === | ||
==== Calculation of Pi ==== | ==== Calculation of Pi ==== | ||
| − | For this assessment, | + | For this assessment, we used code found at [https://helloacm.com/cc-coding-exercise-finding-approximation-of-pi-using-monto-carlo-algorithm/ helloacm.com] |
In this version, the value of PI is calculated using the Monte Carlo method. | In this version, the value of PI is calculated using the Monte Carlo method. | ||
| Line 37: | Line 37: | ||
10000000 3.1417368 - took - 998 millisecs | 10000000 3.1417368 - took - 998 millisecs | ||
100000000 3.1419176 - took - 10035 millisecs | 100000000 3.1419176 - took - 10035 millisecs | ||
| − | + | ||
''The first column represents the "stride" or the number of digits of pi we are calculating to. | ''The first column represents the "stride" or the number of digits of pi we are calculating to. | ||
Revision as of 15:39, 21 February 2018
GPU610/DPS915 | Student List | Group and Project Index | Student Resources | Glossary
Contents
Kernal Blas
Team Members
Progress
Assignment 1
Calculation of Pi
For this assessment, we used code found at helloacm.com
In this version, the value of PI is calculated using the Monte Carlo method. This method states:
- A circle with radius r in a squre with side length 2r
- The area of the circle is Πr2 and the area of the square is 4r2
- The ratio of the area of the circle to the area of the square is: Πr2 / 4r2 = Π / 4
- If you randomly generate N points inside the square, approximately N * Π / 4 of those points (M) should fall inside the circle.
- Π is then approximated as:
- N * Π / 4 = M
- Π / 4 = M / N
- Π = 4 * M / N
For simplicity the radius of the circle is 1. With this, we randomly generate points within the area and count the number of times each point falls within the circle, between 0 and 1. We then calculate the ratio and multiply by 4 which will give us the approximation of Π.
When we run the program we see:
1st Run
1000 3.152 - took - 0 millisecs 10000 3.1328 - took - 0 millisecs 100000 3.14744 - took - 9 millisecs 1000000 3.141028 - took - 96 millisecs 10000000 3.1417368 - took - 998 millisecs 100000000 3.1419176 - took - 10035 millisecs The first column represents the "stride" or the number of digits of pi we are calculating to.
With this method, we can see that the accuracy of the calculation is slightly off. This is due to the randomization of points within the circle. Running the program again will give us slightly different results.
2nd Run
1000 3.12 - took - 0 millisecs 10000 3.1428 - took - 0 millisecs 100000 3.13528 - took - 9 millisecs 1000000 3.143348 - took - 106 millisecs 10000000 3.1414228 - took - 1061 millisecs 100000000 3.14140056 - took - 8281 millisecs
The hotspot within the code lies in the loops. There iteration for the loops is O(n2)
Potential Speedup:
Using Gustafson's Law:
P = 50% of the code P = 0.50 n = ? S(n)= n - ( 1 - P ) ∙ ( n - 1 ) Sn = n - ( 1 - .5 ) ∙ ( n - 1 ) Sn =
