使用openMP｛Copeland Erdõs constant｝改进字符串的串行构建

Question

我正在构建一个程序，在C++11 中查找Copeland Erdõs常数的子串

Copeland Erdõs常数是一个所有素数都按顺序排列的字符串：2,3,5,7,11,13…→23571113…

我需要检查给定的子字符串是否在该常量内，并用一种快速的方法进行检查。

到目前为止，我已经使用Miller Rabin函数构建了一个串行程序，用于检查计数器生成的数字是否为素数，并添加到主字符串（常量）中。为了找到第8个马森数（2³¹-1），程序花费8分钟。

然后，我用find来检查给定的子串是否在常数中以及它开始的位置。

问题：

我使用串行编程。我从0开始，检查所有数字是否都是素数，以将它们相加。。。我不知道是否有其他方法可以做到这一点。子串可以是素数的混合。例如：1.{1131}..7（11,13,17的子串）

你有什么建议可以通过使用OpenMP来提高程序执行时间吗？

我想计算"人类时间"中的第9梅森数。我已经花了一天多的时间，但它找不到（好吧，到达号码）。

gcc version 4.4.7 20120313

Main.cpp

while (found == -1 && lastNumber < LIMIT)   //while not found & not pass our limit
{
    //I generate at least a string with double size of the input (llargada)
    for (lastNumber; primers.length() <= 2*llargada; lastNumber++){
        if (is_prime_mr(lastNumber))
            primers += to_string(lastNumber);    //if prime, we add it to the main string
    }
    found = primers.find(sequencia);    //search substring and keep position
    if (found == string::npos){         //if not found
        indexOfZero += primers.length()/2;      //keep IndexOfZero, the position of string in global constant
        primers.erase(0,primers.length()/2);     //delete first middle part of calculated string
    }
}
if (found != -1){
    cout << "FOUNDED!" << endl;
    cout << "POS: " << indexOfZero << " + " << found << " = " << indexOfZero+found << endl;} //that give us the real position of the substring in the main string
    //although we only spend 2*inputString.size() memory
    else
        cout << "NOT FOUND" << endl;

Answer 1

改进串行执行：

对于初学者来说，你不需要检查每个数字是否是素数，而是检查每个奇数（除了2）。我们知道，过二的偶数都不可能是素数。这样可以将执行时间减少一半。

另外，我不明白为什么你有一个嵌套的循环。你只需要检查一下你的清单。

此外，我担心你的算法可能不正确。目前，如果你找不到子字符串，你会删除一半的字符串，然后继续。然而，如果你一行有50个非素数，你可能会删除除了最后一个字符之外的整个字符串。但是，如果您要查找的子字符串是3位数字，并且需要前面的2个字符，该怎么办？然后，您已经删除了找到解决方案所需的一些信息！

最后，只有在实际找到素数的情况下，才应该搜索子字符串。否则，您已经在上一次迭代中搜索了它，并且没有向string中添加任何内容。

结合所有这些想法，你就有了：

primers = "23";
lastNumber = 3;
found = -1;
while (found == -1)
{
    lastNumber += 2;
    if (is_prime_mr(lastNumber)) {
        primers += to_string(lastNumber);        //if prime, we add it to the main string
        found = primers.find(sequencia);         //search substring and keep position
        if (found == string::npos)
            found = -1;
        else
            break;
    }
}

此外，您应该编写自己的find函数，只检查最后几位数字（其中，few=最近连接到全局字符串primers的长度）。如果子字符串不在前一个全局字符串中，那么它在最新字符串中只能弹出几个位置。该算法应该是O(1)，而不是O(n)。

int findSub(std::string total, std::string substring, std::string lastAddition);

通过此更改，您的if语句应更改为：

if (found != -1)
    break;

添加并行性：

不幸的是，你的算法本质上是串行的，因为你必须一个接一个地迭代所有素数，将它们一行添加到列表中才能找到答案。没有简单的OpenMP方法可以并行化您的算法。

但是，可以利用并行性，将字符串分解为多个部分，并让每个线程分别工作。然后，你要做的唯一棘手的事情就是考虑最后字符串之间的边界，以再次检查你没有遗漏任何内容。如下所示：

bool globalFound = false;
bool found;
std::vector<std::string> primers;
#pragma omp parallel private(lastNumber, myFinalNumber, found, my_id, num_threads)
{
    my_id = omp_get_thread_num();
    num_threads = omp_get_num_threads();
    if (my_id == 0) { // first thread starts at 0... well, actually 3
        primers.resize(num_threads);
        #pragma omp barrier
        primers[my_id] = "23";
        lastNumber = 3;
    }
    else {
        // barrier needed to ensure that primers is initialized to correct size
        #pragma omp barrier
        primers[my_id] = "";
        lastNumber = (my_id/(double)num_threads)*LIMIT - 2; // figure out my starting place
        if (lastNumber % 2 == 0) // ensure I'm not even
            lastNumber++;
    }
    found = false;
    myFinalNumber = ((my_id+1)/(double)num_threads)*LIMIT - 2;
    while (!globalFound && lastNumber < myFinalNumber)
    {
        lastNumber += 2;
        if (is_prime_mr(lastNumber)) {
            primers[my_id] += to_string(lastNumber);
            found = findSub(primers[my_id], sequencia, to_string(lastNumber)); // your new version of find
            if (found) {
                #pragma omp atomic
                globalFound = true;
                break;
            }
        }
    }
}
if (!globalFound) {
    // Result was not found in any thread, so check for boundaries/endpoints
    globalFound = findVectorSubstring(primers, sequencia);
}

我将让您完成这项工作（通过编写智能find，findVectorSubstring-应该只检查primers元素之间的边界，并仔细检查您是否理解此新算法的逻辑）。此外，如果您设置的任意LIMIT太小，您总是可以将整个内容封装在i*LIMIT和(i+1)*LIMIT之间的搜索循环中。

最后，是的，会有负载平衡问题。我当然可以想象线程会发现数量不等的素数。因此，某些线程将在find函数中比其他线程做更多的工作。然而，find()的智能版本应该是O(1)，而is_prime_mr()可能是O(n)或O(logn)，所以我假设大部分执行时间将用于is_prime_mr()函数。因此，我认为负载平衡不会太差。

希望这能有所帮助。