DONE: Scalar product of 2 vectors of the same length

Use a binary tree for computing the sum. The program shall use a number of threads specified as input.

#include <iostream>
#include <fstream>
#include <vector>
#include <thread>
#include <mutex>

using namespace std;

int t, n;
vector<int> a, b;
int prod = 0;
mutex mtx;

void scalar_product(int s, int e, int &res) {
    int partial_prod = 0;
    for (int i = s; i < e; ++i) {
        partial_prod += a[i] * b[i];
    }
    lock_guard<mutex> lock(mtx);
    res = partial_prod;
}

void parallel_scalar_product(int s, int e, int &res, int t) {
    if (t <= 1) {
        scalar_product(s, e, res);
    } else {
        int mid = (s + e) / 2;
        int l_res = 0;
        int r_res = 0;
        thread l_th(parallel_scalar_product, s, mid, ref(l_res), t / 2 + t % 2);
        thread r_th(parallel_scalar_product, mid, e, ref(r_res), t / 2);
        l_th.join();
        r_th.join();
        
        lock_guard<mutex> lock(mtx);
        res = l_res + r_res;
    }
}

int main() {
    ifstream fin("input.in");
    fin >> t;
    fin >> n;
    a.resize(n);
    b.resize(n);
    for (int i = 0; i < n; i++) {
        fin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        fin >> b[i];
    }
		fin.close();

    if (t == 0) {
        scalar_product(0, n, prod);
    } else {
        parallel_scalar_product(0, n, prod, t);
    }
    cout << prod << endl;
}

DONE: Sum of all elements in a matrix

Use a binary tree for computing the sum. The program shall use a number of threads specified as input.

#include <iostream>
#include <fstream>
#include <vector>
#include <thread>
#include <mutex>

using namespace std;

int t, n, m;
vector<vector<int>> mat;
int sum = 0;
mutex mtx;

void partial_sum(int r, int c, int s) {
    if (s == 1) {
        unique_lock<mutex> lck(mtx);
        sum += mat[r][c];
        return;
    }

    int l_s = s / 2 + s % 2;
    int l_r = r;
    int l_c = c;

    int r_s = s / 2;
    int r_r = r + (l_s / m);
    int r_c = c + (l_s % m);
    if (r_c >= m) r_r++, r_c = r_c % m;

    partial_sum(l_r, l_c, l_s);
    partial_sum(r_r, r_c, r_s);
}

void parallel_sum(int r, int c, int s, int t) {
    if (s == 1) {
        unique_lock<mutex> lck(mtx);
        sum += mat[r][c];
        return;
    }
    int l_s = s / 2 + s % 2;
    int l_r = r;
    int l_c = c;

    int r_s = s / 2;
    int r_r = r + (l_s / m);
    int r_c = c + (l_s % m);
    if (r_c >= m) r_r++, r_c = r_c % m;

    if (t == 1) {
        partial_sum(r_r, r_c, r_s);
    } else {
        thread l_th(parallel_sum, l_r, l_c, l_s, t / 2 + t % 2);
        thread r_th(parallel_sum, r_r, r_c, r_s, t / 2);
        l_th.join();
        r_th.join();
    }
}

int main() {
    ifstream fin("input.in");
    fin >> t;
    fin >> n >> m;
    mat.resize(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            fin >> mat[i][j];
        }
    }
	fin.close();
    if (t == 0){
		partial_sum(0, 0, n * m);
    } else {
        parallel_sum(0, 0, n * m, t - 1);
    }
    cout << sum;
}

DONE: Product of two big numbers

The program shall use a number of threads specified as input.

#include <iostream>
#include <fstream>
#include <vector>
#include <thread>
#include <mutex>
#include <algorithm> 

using namespace std;

int t, n;
vector<int> a, b;
vector<int> res;
mutex mtx;

void solve(int t) {
    int n = a.size();
    int m = 2 * n - 1;
    
    res.resize(m, 0);

    if (t <= 1) {
        unique_lock<mutex> lock(mtx);
        for (int x = 0; x < m; x++) {
            for (int i = 0; i < n; ++i) {
                if (x - i >= n || x - i < 0) {
                    continue;
                }
                res[x] += a[i] * b[x - i];
            }
        }
    } else {
        vector<thread> thr;
        for (int idx = 0; idx < t; ++idx) {
            thr.push_back(thread([&, idx]() {
                for (int x = idx; x < m; x += t) {
                    for (int i = 0; i < n; ++i) {
                        if (x - i >= n || x - i < 0) {
                            continue;
                        }
                        unique_lock<mutex> lock(mtx);
                        res[x] += a[i] * b[x - i];
                    }
                }
            }));
        }

        for (int i = 0; i < thr.size(); ++i) {
            thr[i].join();
        }
    }
    vector<int> result;
    int carry = 0;
	for (int i = res.size() - 1; i >= 0; i--){
		res[i] += carry;
		result.push_back(res[i] % 10);
		if (res[i] > 9)
			carry = res[i] / 10;
		else
			carry = 0;
	}
	while (carry > 0){
		result.push_back(carry % 10);
		carry /= 10;
	}
	reverse(result.begin(), result.end());
	res = result;
}

int main() {
    ifstream fin("input.in");
    fin >> t >> n;
	a.resize(n);
	b.resize(n);
    for (int i = 0; i < n; ++i) {
        fin >> a[i];
    }
	  for (int i = 0; i < n; ++i) {
        fin >> b[i];
    }
    fin.close();

    solve(t);

    for (auto it : res) {
        cout << it;
    }

    return 0;
}

DONE: Product of 2 matrices

The program shall use a number of threads specified as input.

#include <iostream>
#include <fstream>
#include <vector>
#include <thread>
#include <mutex>

using namespace std;

int t, n, m;
vector<vector<int>> a, b, res; 
mutex mtx;

void mult(int p, int t, int id) {
    for (int i = id; i < n; i += t) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < p; k++) {
                unique_lock<mutex> lck(mtx);
                res[i][j] += a[i][k] * b[k][j];
            }
        }
    }
}

void mult_parallel(int t) {
    vector<thread> th;

	if(t <= 1){
        mult(n, 1, 0);
    } else {
	    for (int i = 0; i < t; i++) {
	        th.push_back(thread(mult, n, t, i));
	    }
	
	    for (int i = 0; i < t; i++) {
	        th[i].join();
	    }
	}
}

int main() {
    ifstream fin("input.in");
    fin >> t;
    fin >> n >> m;

    a.resize(n, vector<int>(m));
    b.resize(m, vector<int>(n));
    res.resize(n, vector<int>(n, 0));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            fin >> a[i][j];
        }
    }

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            fin >> b[i][j];
        }
    }

    fin.close();

    mult_parallel(t);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

DONE: n-th power of a square matrix

Use a binary tree for computing the result. The program shall use a number of threads specified as input.

#include <iostream>
#include <fstream>
#include <vector>
#include <thread>
#include <mutex>

using namespace std; 

int t, n, p;
vector<vector<int>> a;
mutex mtx;

int compute_point(const vector<vector<int>> a, const vector<vector<int>> b, int i, int j) {
	int sum = 0; 
	for (int k = 0; k < n; k++) {
		sum += a[i][k] * b[k][j]; 
	}
	return sum; 
}

vector<pair<int, int>> split_workload(int n, int t) {
	vector< pair<int, int> > intervals;

	int index = 0;
	int step = n / t;
	int mod = n % t;

	while (index < n) {
		intervals.push_back(pair<int, int>(index, index + step + (mod > 0)));
		index += step + (mod > 0);
		mod--;
	}

	return intervals;
}

vector<vector<int>> mult(const vector<vector<int>> &a, const vector<vector<int>> &b, int t) {
    vector<vector<int>> result(n, vector<int>(n, 0));
    vector<thread> threads;
    vector<pair<int, int>> intervals = split_workload(n, t);
    for (int idx = 0; idx < t; idx++) {
        threads.push_back(
            thread([intervals, a, b, idx, &result]() {
                for (int i = intervals[idx].first; i < intervals[idx].second; i++) {
                    for (int j = 0; j < n; j++) {
                        result[i][j] = compute_point(a, b, i, j);
                    }
                }
            })
        );
    }

    for (int i = 0; i < t; i++) {
        threads[i].join();
    }

    return result;
}

vector<vector<int>> power(const vector<vector<int>> a, int p, int t) {
	if (p == 1) {
		return a; 
	}

	vector<vector<int>> temp = power(a, p / 2, t);
	if (p % 2 == 0) {
		return mult(temp, temp, t);
	}
	else {
		return mult(a, mult(temp, temp, t), t);
	}
}

int main() {
    ifstream fin("input.in");
    fin >> t >> n >> p;
    a.resize(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            fin >> a[i][j];
        }
    }
    fin.close();

    vector<vector<int>> res = power(a, p, t);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }
}

DONE: Polynomial multiplication

Use a binary tree for computing the result. The program shall use a number of threads specified as input.

#include <iostream>
#include <fstream>
#include <thread>
#include <string>
#include <vector>
#include <cmath>
#include <mutex>

using namespace std;

int t, n;
vector<int> a, b, r;
mutex mtx;

void multiply(int start, int end) {
    for (int i = start; i < end; ++i) {
        for (int j = 0; j < n; ++j) {
            unique_lock<mutex> lck(mtx);
            r[i + j] += a[i] * b[j];
        }
    }
}

void mult(int t, int start, int end) {
    if (t <= 1) {
        multiply(start, end);
    } else {
        int mid = (start + end) / 2;
        thread l_th([=] { mult(t / 2 + t % 2, start, mid); });
        thread r_th([=] { mult(t / 2, mid, end); });

        l_th.join();
        r_th.join();
    }
}

int main() {
    ifstream fin("input.in");
    fin >> t >> n;
    a.resize(n);
    b.resize(n);
    r.resize(2 * n - 1, 0);
    for (int i = 0; i < n; ++i) {
        fin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        fin >> b[i];
    }

    mult(t, 0, n);

    for (auto it : r)
        cout << it << " ";

    return 0;
}

DONE: Prime numbers up to N