240
edits
Changes
→Pi
=== Pi ===
This is a comparison between two programs that calculate Pi.
* '''How to execute the programs on Linux'''
1. Here is the Makefile:
# Change this to "monte-carlo" if needed
VER = leibniz
# Uncomment and modify the following lines to specify a specific version of GCC
#GCC_VERSION = 5.2.0
#PREFIX = /usr/local/gcc/${GCC_VERSION}/bin/
CC = ${PREFIX}gcc
CPP = ${PREFIX}g++
$(VER): $(VER).o ; \
$(CPP) -g -pg -o$(VER) $(VER).o
$(VER).o: $(VER).cpp ; \
$(CPP) -c -O2 -g -pg -std=c++14 $(VER).cpp
# Remember to ">make clean" after ">make" to cleanup if the cleaning does not happen automatically
clean: ; \
rm *\.o
2. Download leibniz.cpp and monte-carlo.cpp and put them into the same directory as the Makefile.
3. Execute the following:
>make
'''Leibniz formula implementation:'''
13 // Arctangent of 1; execute for ~n iterations to refine the result
14 long double arctan1( unsigned long long int it ) {
15 long double r = 0.0;// 1 op. (=) runs 1 time
16
17 // v0.25; due to performing the operations in a different order, there are rounding issues...
18 for ( long double d = 0.0; d < it; d++ ) { // 1 op. (=) runs 1 time; 2 op.s (<, ++) run ''n'' times 19 long double de = d * 4.0 + 1.0;// 3 op.s (=, *, +) run ''n'' times 20 r += (1.0 / de) - (1.0 / (de + 2.0));// 6 op.s (+ & =, /, -, /, +) run ''n'' times
21 }
22
23 return r;// 1 op. (return) runs 1 time
24 }
25
40 }
* '''Stage 1 - Big-O:'''There is only one for loop in this program (on line 18); it executes ''d'' times, where ''d'' is the first argument provided to the program on the command line. Summing up the operations in the (predicted) hotspot, T(n) = 11n + 3; therefore O(n) runtime. * '''Stage 2 - Potential Speedup