EXP NO – Implementation of multi threading

9(a)

DATE –

Aim:
In this task, you are required to implement a multi-threaded function that
calculates the Fibonacci series up to the nth term. The calculation should be
distributed across multiple threads, with each thread calculating a portion of the
Fibonacci series. Each thread will compute specific terms, and the results should
be merged to form the complete series.

Background Theory:
The Fibonacci sequence is a series of numbers where each number is the sum of
the two preceding ones.

 The Fibonacci series up to the 11th term is: 0, 1, 1, 2, 3, 5, 8, 13,

21, 34, 55
 The Fibonacci series up to the 20th term is: 0, 1, 1, 2, 3, 5, 8, 13,
21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181

Running multiple threads in parallel helps speed up calculations by using

multiple CPU cores.
Algorithm:
Step 1: Read Input

1. Take an integer input n from the user.

2. If n < 1, print "Invalid input" and exit.

Step 2: Initialize Fibonacci Array

3. Create an array fib of size n to store Fibonacci numbers.

4. Set fib[0] = 0.
5. If n > 1, set fib[1] = 1.

Step 3: Determine Multi-Threading Parameters

6. Get the number of available CPU cores.

7. Set the number of threads as the minimum of CPU cores and n/2.
8. Compute chunkSize = max(2, n / numThreads), which determines how many
terms each thread will compute.

Step 4: Create and Start Threads

9. Iterate from index i = 2 to n, with increments of chunkSize:

o Set end = min(i + chunkSize, n).
o Create a new thread to compute Fibonacci numbers from index i to
end.
o Start the thread and add it to a list.

Step 5: Wait for Threads to Finish

[Link] join() to ensure all threads complete execution.

[Link] the executor service.
Step 6: Print Fibonacci Series

[Link] through the fib array and print each Fibonacci number.
 Coding:

import [Link].*;

import [Link].*;

class FibonacciThread implements Runnable {

private int start, end;

private long[] fib;

public FibonacciThread(int start, int end, long[] fib) {

[Link] = start;

[Link] = end;

[Link] = fib; }

public void run() {

for (int i = start; i < end; i++) {

synchronized (fib) {

fib[i] = fib[i - 1] + fib[i - 2]; } } } }

public class MultiThreadedFibonacci {

public static void main(String[] args) throws InterruptedException {

Scanner sc = new Scanner([Link]);

int n = [Link]();

if (n < 1) {

[Link]("Invalid input");

return; }

long[] fib = new long[n];

fib[0] = 0;

if (n > 1) fib[1] = 1;

int cores = [Link]().availableProcessors();

int numThreads = [Link](cores, n / 2);

ExecutorService executor = [Link](numThreads);

int chunkSize = [Link](2, n / numThreads);

List<Thread> threads = new ArrayList<>();

for (int i = 2; i < n; i += chunkSize) {

int end = [Link](i + chunkSize, n);

Thread t = new Thread(new FibonacciThread(i, end, fib));

[Link](t);

[Link]();

}
for (Thread t : threads) {

[Link]();

}
[Link]();

for (long num : fib) {

[Link](num);
}
}
}
Output:
 Result:

Thus, the program correctly computes the Fibonacci sequence up to the

given number and displays the Fibonacci series.
EXP NO – Implementation of multi threading
9(b)

DATE –

Aim:

Implement a multi-threaded program to compute the sum of the first

N prime numbers and the first N Fibonacci numbers concurrently. Each
calculation runs in a separate thread for efficiency. The program then
outputs both sums after computation.

Background Theory:

This program demonstrates multi-threading in Java by calculating:

1. The sum of the first N Fibonacci numbers (using the fibo thread).
2. The sum of the first N prime numbers (using the prime thread).

Concepts Used:

 Threads in Java: The program creates two separate threads (fibo and
prime) to perform calculations concurrently.
 Fibonacci Sequence: Each number is the sum of the two preceding
numbers. The sum is calculated iteratively.
 Prime Numbers: A number is prime if it has only two divisors: 1 and
itself. The program finds and sums the first N prime numbers.
 Concurrency: Both calculations run in parallel, improving efficiency.

Algorithm:
Step 1: Take Input

1. Read an integer N from the user.

Step 2: Initialize and Start Threads

2. Create a fibo thread to compute the sum of the first N Fibonacci numbers.
3. Create a prime thread to compute the sum of the first N prime numbers.
4. Start both threads using start(), allowing them to run concurrently.

Step 3: Fibonacci Calculation (fibo Thread)

5. Initialize first = 0, second = 1, and res = 1.

6. Iterate from 2 to N, updating Fibonacci values iteratively:
o Compute the next Fibonacci number: temp = first + second.
o Update first = second, second = temp, and add temp to res.
7. Print the sum of the Fibonacci series.

Step 4: Prime Number Calculation (prime Thread)

8. Initialize res = 0 and primesFound = 0.

9. Start checking numbers from 2, counting prime numbers found.
[Link] an optimized prime check:
o Count the number of divisors up to the square root of num.
o If exactly 2 divisors are found, it's a prime number.
 [Link] the prime number to res and increment primesFound.
[Link] until N prime numbers are found.
[Link] the sum of the first N prime numbers.

Step 5: End Program

[Link] threads complete execution independently, printing their results

 Coding:

package workout;

import [Link].*;

class fibo extends Thread{

public int n,first,second,res;

fibo(int n){

this.n=n;
[Link]=0;
[Link]=1;
[Link]=1;

}
public void run() {

try {
[Link](1000);

for(int i=2;i<n;i++) {

int temp=first+second;
first=second;
second=temp;
res+=temp;
}
[Link]("The sum of fibonacci series is "+ res); }

catch(Exception e) { } } }

class prime extends Thread {

int n, res, count, num, primesFound;

prime(int n) {
this.n = n;
res = 0;
count = 0;
num = 2; // Start checking from 2
primesFound = 0;
}

public void run() {

try {

while (primesFound < n) {

int divisorCount = 0;

for (int i = 1; i * i <= num; i++) { // Optimized prime check

if (num % i == 0) {
if (i * i == num) divisorCount++; // Perfect square case
else divisorCount += 2; // Two divisors: i and num/i
}
}
 if (divisorCount == 2) { // Prime number found
res += num;
primesFound++;
}
num++;
}
[Link]("The sum of the first " + n + " prime numbers is " +
res);
} catch (Exception e) {
[Link]();
}
}
}

public class multi {

public static void main(String[] args) {

Scanner ob=new Scanner([Link]);
int n=[Link]();
fibo thread1=new fibo(n);

prime thread2=new prime(n);

[Link]();
[Link]();

}
Output:
 Result:

Thus, the program correctly computes the sum of the first N prime numbers
and the sum of the first N Fibonacci numbers concurrently,
EXP NO – Implementation of multi threading
9(c)

DATE –

Aim:
To implement a multi-threaded program in C++ that efficiently finds and
displays all prime numbers within a given range [n, m] by dividing the workload
between multiple threads, optimizing execution time.

Background Theory:

This program demonstrates multi-threading in C++ by dividing a given range

[n, m] into multiple subranges, where each thread processes a subrange to find
prime numbers.

Concepts Used:

 Threads in C++ (std::thread): Each thread handles a portion of the

range.
 Prime Number Check (without built-in functions): A number is prime if
it has exactly two divisors: 1 and itself.
 Concurrency: By using multiple threads, the workload is distributed
efficiently across CPU cores.
 Synchronization: A mutex (std::mutex) ensures safe access to the
shared list of prime numbers.

Algorithm:

Step 1: Input the Range

1. Read two integers n and m (start and end of the range).

2. If n > m, print "Invalid range" and terminate the program.

Step 2: Multi-Threading Setup

3. Create two threads:

o First thread checks primes in the range [n, (n + m) / 2].
o Second thread checks primes in the range [(n + m) / 2 + 1, m].
4. Start both threads to execute prime number checking concurrently.

Step 3: Prime Number Calculation

5. Each thread checks numbers in its assigned range:

o A number is prime if it is greater than 1 and has no divisors other than 1
and itself.
o If a number is prime, store it in the global primes[] array.

Step 4: Merge Results and Display Output

6. Wait for both threads to complete execution using join().

7. Print all stored prime numbers.
 Coding:

#include <iostream>
#include <thread>

using namespace std;

const int MAX = 100000;

int primes[MAX], prime_count = 0;
int n, m;

bool isPrime(int num) {

if (num < 2) return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) return false;
}
return true;
}

void findPrimes(int start, int end) {

for (int i = start; i <= end; i++) {
if (isPrime(i)) {
primes[prime_count++] = i;
}
}
}

int main() {
cin >> n >> m;

if (n > m) {
cout << "Invalid range" << endl;
return 0;
}

thread t1(findPrimes, n, (n + m) / 2);

thread t2(findPrimes, (n + m) / 2 + 1, m);

[Link]();
[Link]();

for (int i = 0; i < prime_count; i++) {

cout << primes[i] << endl;
}

return 0;
}
Output:
Result:
Thus, the program correctly finds and displays all prime numbers within the
given range using optimized multi-threading.