代码之家 › 专栏 › 技术社区 › Nick Larsen

如何使这个质数查找器并行工作

primes parallel-processing multithreading

Nick Larsen · 技术社区 · 14 年前

我知道prime发现已经被很好地研究过了,并且有很多不同的实现。我的问题是,使用提供的方法(代码示例),我如何开始分解工作?它将运行的机器有4个四核超线程处理器和16GB的ram。我意识到可以做一些改进,特别是在 IsPrime 方法。我也知道一旦名单上有超过 int.MaxValue

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Prime
{
    class Program
    {
        static List<ulong> primes = new List<ulong>() { 2 };

        static void Main(string[] args)
        {
            ulong reportValue = 10;
            for (ulong possible = 3; possible <= ulong.MaxValue; possible += 2)
            {
                if (possible > reportValue)
                {
                    Console.WriteLine(String.Format("\nThere are {0} primes less than {1}.", primes.Count, reportValue));

                    try
                    {
                        checked
                        {
                            reportValue *= 10;
                        }
                    }
                    catch (OverflowException)
                    {
                        reportValue = ulong.MaxValue;
                    }
                }

                if (IsPrime(possible))
                {
                    primes.Add(possible);
                    Console.Write("\r" + possible);
                }
            }

            Console.WriteLine(primes[primes.Count - 1]);
            Console.ReadLine();
        }

        static bool IsPrime(ulong value)
        {
            foreach (ulong prime in primes)
            {
                if (value % prime == 0) return false;
                if (prime * prime > value) break;
            }

            return true;
        }
    }
}

我看到的基本方案有两种:1)使用所有线程测试单个数字,这可能对较高的素数很好,但我真的想不出如何实现它;2)使用每个线程测试单个可能的素数,这可能会导致找到一个不连续的素数字符串,并在下一个数字出现时遇到未使用的资源问题要测试的值大于找到的最高素数的平方。

对我来说,这两种情况只是在建立素数列表的早期阶段才具有挑战性,但我并不完全确定。这样做是为了打破这种工作的个人练习。

2 回复 | 直到 14 年前

Jean-Bernard Pellerin 14 年前

如果需要,您可以并行化这两个操作:检查一个素数和同时检查多个素数。虽然我不确定这是否有用。老实说,我会考虑删除main()中的线程。

我试着忠实于您的算法,但为了加快速度,我使用了x*x而不是reportvalue;如果您愿意,可以很容易地还原它。

为了进一步改进我的核心拆分,您可以确定一个算法,根据数字的大小计算出执行拆分所需的计算量,并以这种方式拆分列表。(也就是说,较小的数字需要较少的时间来除以,所以使第一个分区变大)

另外,我对线程池的概念可能并不是以我想要的方式存在的

List<int> primes = {2};  
List<int> nextPrimes = {};
int cores = 4;
main()
{   
  for (int x = 3; x < MAX; x=x*x){  
    int localmax = x*x;
    for(int y = x; y < localmax; y+=2){  
      thread{primecheck(y);}
    }
  "wait for all threads to be executed"
  primes.add(nextPrimes);
  nextPrimes = {};
  }
}

void primecheck(int y)
{  
  bool primality;  
  threadpool? pool;
  for(int x = 0; x < cores; x++){
    pool.add(thread{
      if (!smallcheck(x*primes.length/cores,(x+1)*primes.length/cores ,y)){
        primality = false;
        pool.kill();
      }
    });
  }  
  "wait for all threads to be executed or killed"
  if (primality)
    nextPrimes.add(y);  
}

bool smallcheck(int a, int b, int y){  
  foreach (int div in primes[a to b])  
    if (y%div == 0)  
      return false;  
  return true;
}

E:我补充了我认为合用应该是什么样子的,如果你想看到没有合用的话,请看修订版。

Community Ian Goodfellow 7 年前

改用埃拉托斯烯筛。除非首先使用一个好的算法,否则并行化是不值得的。

使用一个位数组来表示素数,它比显式地表示它们占用更少的空间。

另请参见 this answer