University of Management and Technology Lahore School of Science and Technology Department of
Computer Science
Complex Computing Problem (CCP)
Semester: 5TH
Course: Operating System
Submitted by: Amna Asif (F2022266676)
Muhammad Hassan (F2022266653)
Muhammad Jawad Ali (f2022266686)
Section: V12
"Parallel Computation of π Using Maclaurin Series" ➢
Introduction
This report details the implementation of a program to compute the value of π using the Maclaurin series for
arctan(x). The problem is approached in two stages: a sequential implementation and a multithreaded solution
using mutex locks for synchronization. The objective is to compute π efficiently while adhering to constraints
like:
1. n (number of terms) must be greater than 100,000.
2. Global result is updated by all submodules (threads).
3. Load balancing ensures that the number of terms is evenly distributed among threads.
➢ Problem Description
The Maclaurin series for arctan(x)\arctan(x)arctan(x) is given as:
arctan(x)=x−x^3/3+x^5/5−x^7/7+⋯
For x=1: π=4⋅(1−1/3+1/5−1/7+⋯ )
Our task is to compute π using this series in terms, where n>100,000n > 100,000n>100,000. In the multithreaded
implementation, the computation must be distributed evenly across threads, with synchronization to ensure
accuracy.
2. Constraints and Requirements
Range of Conflicting Requirements
1. Efficient handling of the global result through proper synchronization mechanisms (e.g., mutex locks).
2. Threads should divide terms equally to ensure load balancing.
Depth of Knowledge Required
• Programming Techniques: Effective use of multithreading and mutex locks.
• System Configurations: Understanding of hardware to optimize thread allocation and minimize
overhead.
• Algorithm Design: Ensuring minimal communication overhead while achieving accurate results.
Interdependence
• Each thread operates independently to compute its assigned terms.
• Threads communicate through shared memory to update the global result.
• Redundancy mechanisms to handle thread failures and avoid complete system failure.
3. Implementation Details
Mutex-Lock Mechanism
• Purpose: Ensure safe access to the shared global variable.
• Implementation: Each thread locks the mutex before updating the global result and unlocks it after the
update.
Load Balancing
• Terms are divided equally among threads. If it is not perfectly divisible, the remainder is handled
efficiently by distributing extra terms to some threads.
➢ Sequential Implementation
The sequential program calculates π by iterating through the series and summing up the terms in a single flow.
Each term alternates between positive and negative values based on its index.
➢ Implementation Code ➢ Sequential Code:
#include <iostream> #include <cmath>
using namespace std; double
compute_pi_sequential(long n) {
double pi = 0.0; for (long i = 0; i < n;
++i) { double term = (i % 2 == 0 ?
1.0 : -1.0) / (2 * i + 1); pi += term;
} return 4
* pi;
} int main() { long n = 1000000; // Example value cout <<
"Sequential PI: " << compute_pi_sequential(n) << endl;
return 0;
This code calculates an approximation of π\piπ using the Maclaurin series for arctan(1)\arctan(1)arctan(1),
which is:
π=4 (1−13+15−17+… )
The compute_pi_sequential function iterates over n terms, alternating the sign of each term and adding it to a
running total. The result is multiplied by 4 to approximate π\piπ. The more terms (n) used, the closer the
approximation is to the actual value of π\piπ. However, the series converges slowly, requiring a large n for high
accuracy.
➢ Improvements
• Parallelism:
o Divide the computation among multiple threads to reduce runtime.
• Alternative Algorithms: o Use faster converging series (e.g., the
Gauss-Legendre algorithm).
• Precision Libraries: o For applications requiring extreme precision, use
arbitrary-precision libraries like GMP.
➢ FLOWCHART SEQUENTIAL CODE IMPLEMENTATION
➢ Multithreaded Code
#include <iostream>
#include <thread>
#include <mutex> #include <vector> using namespace
std; mutex mtx; double pi = 0.0; // Global result void
compute_partial_sum(long start, long end) { double
partial_sum = 0.0; for (long i = start; i < end; ++i) {
double term = (i % 2 == 0 ? 1.0 : -1.0) / (2 * i + 1);
partial_sum += term;
lock_guard<mutex> lock(mtx); // Ensures synchronization
pi += partial_sum;
} int main(int argc, char* argv[]) { if (argc != 3) { cout <<
"Usage: pi_mutex <number_of_threads> <n>" << endl;
return -1;
int num_threads = stoi(argv[1]); long n =
stol(argv[2]); if (n < 100000) { cout << "n must
be greater than 100,000" << endl;
return -1;
vector<thread> threads; long terms_per_thread = n /
num_threads; for (int i = 0; i < num_threads; ++i) { long start
= i * terms_per_thread; long end = (i == num_threads - 1) ? n :
start + terms_per_thread;
threads.emplace_back(compute_partial_sum, start, end);
} for (auto& t :
threads) {
[Link]();
cout << "Parallel PI: " << 4 * pi << endl;
return 0;
This multithreaded code computes π\piπ using the Maclaurin series by dividing the workload across multiple
threads. Each thread calculates a partial sum for its assigned range and updates the global result pi using a
threadsafe mutex to avoid data races. The main function initializes threads, distributes terms among them, and
waits for all threads to complete. This approach speeds up computation compared to the sequential method,
especially for a large number of terms (n). Speedup performance and improve scalability.
Comparison graph between sequential and multithread execution:
➢ Performance Analysis
The program's performance was analyzed by comparing execution times for the sequential and multithreaded
versions. Key observations:
➢ Sequential Execution: Took significantly longer as n increased.
➢ Multithreaded Execution: Reduced computation time due to parallelism, especially with
more threads.
Performance Table:
Number of Threads n Terms Execution Time (s)
1 (Sequential) 1,000,000 10.4
2 1,000,000 5.2
4 1,000,000 2.6
8 1,000,000 1.4
➢ Flowchart of Multithreaded Implementation:
➢ Graphs
1. Convergence of π: This graph shows the estimated value of π as the number of terms [Link]
estimation converges to the true value of π () as increases.
2. Error Analysis: This graph depicts the absolute error in π estimation as a function of. A log-log scale
is used to highlight the inverse relationship. Error decreases significantly with larger.