I am new to the threads concepts and I try to understand them better. After reading the theory about I decided to write a simple program with threads. I found this (maybe simple) task in the internet:
Write a program that calculates prime numbers and numbers of Fibunacci on different threads.
a. The first thread starts searching for prime number from 1, until killing of the program and when a prime number is found the program must present the time for finding this number.
b. The second thread is calculating and printing numbers of Fibunacci from 1 until killing of the program. When a new number of Fibunacci is found the program prints this number and the time for calculating this number.
c. The time is shown in ms (milliseconds)
d. Think about strategies for not having overlapping messages from the console.
e. The program must work with large as possible numbers. When the number is too large to be held in type like unsigned long long the program stops the calculation of that kind of numbers and shows error message.
Example output:
Prime 1, 0.1 ms.
Fibunacci 1, 0.1 ms.
Prime 2, 0.1 ms.
Fibunacci 2, 0.1 ms.
Prime 3, 0.1 ms.
Fibunacci 3, 0.1 ms.
Fibunacci 5, 0.1 ms.
Prime 5, 0.1 ms.
Fibunacci 8, 0.1 ms.
Prime 7, 0.1 ms.
Fibunacci 13, 0.2 ms.
Fibbunaci 21, 0.1 ms.
Prime 11, 0.2 ms.
This is the code I wrote:
#include <iostream> // std::cout
#include <string> // std::cout << std::string
#include <thread> // std::thread
#include <time.h> // clock()
#include <mutex> // std::mutex
std::mutex mtx;
int timePrim, timeFib;
bool isPrime(int testedNumber)
{
if (testedNumber <= 2) return true;
if (testedNumber % 2 == 0) return false;
for (int i = 3; (i*i) <= testedNumber; i += 2)
{
if (testedNumber % i == 0) return false;
}
return true;
}
// the function is realized by a recursive algorithm; credits to stackoverflow ;)
bool isFibonacci(unsigned long long testedNumber, int a = 1, int b = 1)
{
if (testedNumber == 0 || testedNumber == 1)
return true;//returning true for 0 and 1 right away.
int nextFib = a + b;//getting the next number in the sequence
if (nextFib > testedNumber)
return false;//if we have passed the tested number, it's not in the sequence
else if (nextFib == testedNumber)
return true;//if we have a perfect match, the tested number is in the sequence
else
isFibonacci(testedNumber, b, nextFib);//otherwise, get the next fibonacci number and repeat.
}
void CheckNumber(unsigned long long numberToCheck, bool ifPrime)
{
bool result = false;
if (ifPrime == true)
{
result = isPrime(numberToCheck);
}
else
{
result = isFibonacci(numberToCheck);
}
if (result == true)
{
float currentTime = 0;
std::string typeNumber = "";
if (ifPrime == true)
{
typeNumber = "Prime";
currentTime = (float)(clock() - timePrim) / CLOCKS_PER_SEC;
timePrim = clock();
}
else
{
typeNumber = "Fibonacci";
currentTime = (float)(clock() - timeFib) / CLOCKS_PER_SEC;
timeFib = clock();
}
mtx.lock();
std::cout << typeNumber << " number " << numberToCheck << "; time " << currentTime << std::endl;
mtx.unlock();
}
}
int main()
{
timePrim = timeFib = clock();
for (unsigned long long i = 0; true; i++) // endless for loop == while(true) // by requirements
{
std::thread primeThread = std::thread(CheckNumber, i, true);
std::thread fibThread = std::thread(CheckNumber, i, false);
primeThread.join();
fibThread.join();
}
}
As far as I understand, these two threads should go independently one another and to print the results as fast the relevant function find a number. But the results appear straightforward - by the order of the advance of the iterator in the for loop in the main function but not by the time of calculation. This is a snippet from the console:
Prime number 0; time 0.005
Fibonacci number 0; time 0.007
Prime number 1; time 0.03
Fibonacci number 1; time 0.029
Prime number 2; time 0.093
Fibonacci number 2; time 0.092
Prime number 3; time 0.023
Fibonacci number 3; time 0.023
Prime number 5; time 0.05
Fibonacci number 5; time 0.052
Prime number 7; time 0.023
Fibonacci number 8; time 0.045
Prime number 11; time 0.038
Prime number 13; time 0.077
Fibonacci number 13; time 0.091
Prime number 17; time 0.019
Prime number 19; time 0.179
Fibonacci number 21; time 0.208
Prime number 23; time 0.027
What should I correct in this code in order to make independent threads running? Where is/are my mistake/s?
// sorry if the text in English above is bad - this is not my native language so it is possible I have made some mistakes...
Now your program creates threads for every number i, so if you calculate primes and fibonaccis where i is from 0 to gazilion, it will create and destroy 2 gazilions threads. Thread creation requires system calls to be done and it is not particularly fast to do so in a loop.
Also you make both threads wait for each other before submitting more work.
Here is how your program looks in pseudocode (any similarity to real programming languages is purely coincidental):
def prime(i):
calculate one prime
def fibo(i):
calculate one fibo
for i from 0 to gazilion:
prime_thread = create_and_run_thread(prime, i) # expensive, runs gazilion times
fibo_thread = create_and_run_thread(fibo, i) # expensive, runs gazilion times
wait_for(prime_thread) # wait until single number is crunched
wait_for(fibo_thread) # wait until single number is crunched
destroy_thread(prime_thread)
destroy_thread(fibo_thread)
Instead, you could create 2 permanent threads per task and loop separately:
def prime():
for i from 0 to gazilion:
calculate one prime
def fibo():
for i from 0 to gazilion:
calculate one fibo
prime_thread = create_and_run_thread(prime) # expensive, but runs only once
fibo_thread = create_and_run_thread(fibo) # expensive, but runs only once
wait_for(prime_thread) # you only wait until gazilion is reached
wait_for(fibo_thread) # you only wait until gazilion is reached
destroy_thread(prime_thread) # runs oly once
destroy_thread(fibo_thread) # runs oly once