When run in GDB, it has no issues. When not, it runs indefinitely (well... I can't really say that for sure... I can say it runs for a long time).
Also, I realise this is a total hack of a way to do this. I'm open to, and glad for, any suggestions.
main.cpp
Code:
#include "prime.hpp"
#include <iostream>
#include <map>
#include <thread>
#include <utility>
#include <vector>
#define MAX_THREADS 16
using namespace std;
void wrapper(mpz_class n, map<mpz_class, set<mpz_class>> &factor_list, bool &state)
{
auto factors = factor(n);
factor_list.insert(pair<mpz_class, set<mpz_class>>(n, factors));
state = false;
}
int main()
{
map<mpz_class, set<mpz_class>> factors;
vector<pair<thread, bool>> threads;
for(mpz_class n = 2;n <= 10;n++)
{
while(threads.size() >= MAX_THREADS)
for(auto i = threads.begin();i < threads.end();i++)
if(i->second == false)
{
if(i->first.joinable())
i->first.join();
threads.erase(i);
}
threads.push_back(pair<thread, bool>(thread(), true));
threads.back().first = thread(wrapper, n, std::ref(factors), std::ref(threads.back().second));
}
while(threads.size() > 0)
for(auto i = threads.begin();i < threads.end();i++)
if(i->second == false)
{
if(i->first.joinable())
i->first.join();
threads.erase(i);
}
for(auto i = factors.begin();i != factors.end();i++)
{
std::cout << i->first.get_str() << ": ";
for(auto j = i->second.begin();j != i->second.end();j++)
std::cout << j->get_str() << " ";
std::cout << std::endl;
}
return 0;
}
prime.hpp
Code:
#ifndef PRIME_HPP
#define PRIME_HPP
#include "gmpxx.h"
#include <set>
std::set<mpz_class> factor(mpz_class);
bool prime(mpz_class);
#endif // PRIME_HPP
prime.cpp (Included for completeness. I don't believe this code is the problem.)
Code:
#include "prime.hpp"
#include <thread>
#include <vector>
static std::vector<mpz_class> primes{2, 3};
static void extend_primes(mpz_class n)
{
// Unfortunately, primes can't effeciently, if at all, be extended concurrently...
static std::mutex m;
std::lock_guard<std::mutex> lock(m);
for(mpz_class i = primes.back() + 2;i <= n;i += 2)
{
bool prime = true; // Assume i is prime.
for(auto j = primes.begin();prime && *j <= sqrt(i);j++)
if(i % *j == 0)
prime = false;
if(prime)
primes.push_back(i);
}
}
std::set<mpz_class> factor(mpz_class n)
{
std::set<mpz_class> factors;
extend_primes(n);
for(auto i = primes.begin();*i <= n / 2;i++)
if(n % *i == 0)
factors.insert(*i);
return factors;
}
bool prime(mpz_class n)
{
extend_primes(sqrt(n));
for(auto i = primes.begin();*i <= sqrt(n);i++)
{
if(n % *i == 0)
return false;
}
return true;
}
Compiled with:
Code:
gcc -g -pthread -std=c++0x -lstdc++ -lgmp -o prime main.cpp prime.cpp
Desired output:
Code:
2:
3:
4: 2
5:
6: 2 3
7:
8: 2
9: 3
10: 2 5