c++ - 计算素数频率的多线程程序会给出不准确的结果。

Question

我正在做一项作业，我需要计算从 1 到 1000 万的素数出现的频率。我们要通过获取变量 U(即 1000 万)并将其分成 N 个部分并让多个线程计算质数的频率来做到这一点，我们必须用不同的 N 值来尝试这个并观察我们的处理器滴答声和花费的时间计算。该程序的工作方式是将 1000 万分为 N 部分，将上限和下限放入一个线程 vector 中，每个线程调用一个计算素数的函数。现在从一百万开始的素数频率应该是 664579。我在做多线程时得到的结果稍微不准确。例如，如果我使用 N=1 运行程序，这意味着只有一个线程可以解决我得到的频率为 6645780，它相差 1。N=2 我得到正确的结果 664579，N=3 freq=664578，并且很快。下面是代码，非常感谢任何帮助。

#include <iostream>
#include <thread>
#include <vector>
#include<algorithm>
#define MILLION 1000000
using namespace std;
using std::for_each;
void frequencyOfPrimes(long long upper, long long lower, long long* freq)
{
    long long i, j;
    if (lower == 2) { *freq = upper; }
    else { *freq = upper - lower; }
    for (i = lower; i <= upper; ++i)
        for (j = (long long)sqrt(i); j>1; --j)
            if (i%j == 0) { --(*freq); break; }
    return;
}

int main(int argc, char* argv[])
{

    clock_t ticks = clock();
    long long N = 10; //declare and initialize number of threads to calculate primes
    long long U = 10*MILLION;
    long long F=0; //total frequency
    long long d = U / N; // the quotient of 10mil/number of threads
    vector<thread> tV; //declare thread vector
    vector<long long> f, u, l; //vector for freq, upper and lower bounds
    f.resize(N);//initialize f
    for (long long i = 0; i<N; i++) { //initialize and populate vectors for upper and lower bounds
        if (i == 0) {
            l.push_back(2);
            u.push_back(d);
        }
        else {
            l.push_back(u.at(i-1)+ 1);
            u.push_back(u.at(i-1) + d);
        }
    }
    u.at(N-1) = U;  //make sure last thread has value of U for upper bound
    for (long long i = 0; i < N; i++) { //initialize thread vectors
        tV.push_back(thread(frequencyOfPrimes, u.at(i), l.at(i), &f.at(i)));
    }

    for_each(tV.begin(), tV.end(), mem_fn(&thread::join));

    ticks = clock() - ticks;

    for (long long i = 0; i < N; i++)
        F = f.at(i) + F;
    cout << "Frequency is " << F << endl;
    cout << "It took " << ticks << " ticks (";
    cout << ((float)ticks) / CLOCKS_PER_SEC << " seconds)" << endl;
    this_thread::sleep_for(chrono::seconds(5));
    return 0;
}

Answer 1

这与多线程无关。 始终测试您的功能:

#include <iostream>
#include <cmath>
using namespace std;

// this is your function with a shorter name
void fop_strange(long long upper, long long lower, long long* freq)
{
    long long i, j;
    if (lower == 2) { *freq = upper; }
    else { *freq = upper - lower; }
    for (i = lower; i <= upper; ++i)
        for (j = (long long)sqrt(i); j>1; --j)
            if (i%j == 0) { --(*freq); break; }
    return;
}

// attention, I switched order of upper and lower
long long fop(long long a, long long b) {
  long long f = 0;
  fop_strange (b, a, &f);
  return f;
}

int main() {
  cout << fop(2, 4) << endl;
  cout << fop(10, 14) << endl;
  return 0;
}

让我们首先手动计算素数:

2 to 4 (inclusive) => 2 (2, 3)
10 to 14 (inclusive) => 2 (11, 13)

现在你的函数(live on ideone)

3
1

为什么？嗯，当你遇到一个非素数时，你正确地减少了计数，但你没有正确地初始化它。从 2 到 4(含)的范围有 3 个数字，而不是 4。从 2 到 100 万的范围有 100 万 - 2 + 1，而不是 100 万个数字。 10到14之间有5个数，不只有4个等等。

这解释了您得到的结果:对于从 2 开始的范围，您的函数返回多 1 个数字，适合每个其他范围少 1 个数字。因此，当仅使用一个线程并因此仅使用一个以 2 开头的范围时，您的结果会增加一个，而您添加的每个线程都会增加一个范围，从而减少一个，从而将总体结果减少一个。