13

我实际上对我的问题有一个答案,但它没有并行化,所以我对改进算法的方法很感兴趣。无论如何,它可能对某些人有用。

int Until = 20000000;
BitArray PrimeBits = new BitArray(Until, true);

/*
 * Sieve of Eratosthenes
 * PrimeBits is a simple BitArray where all bit is an integer
 * and we mark composite numbers as false
 */

PrimeBits.Set(0, false); // You don't actually need this, just
PrimeBits.Set(1, false); // remindig you that 2 is the smallest prime

for (int P = 2; P < (int)Math.Sqrt(Until) + 1; P++)
    if (PrimeBits.Get(P))
        // These are going to be the multiples of P if it is a prime
        for (int PMultiply = P * 2; PMultiply < Until; PMultiply += P)
            PrimeBits.Set(PMultiply, false);

// We use this to store the actual prime numbers
List<int> Primes = new List<int>();

for (int i = 2; i < Until; i++)
    if (PrimeBits.Get(i))
        Primes.Add(i);

也许我可以一起使用多个BitArrays 和BitArray.And()

4

8 回答 8

7

您可以通过使用双向链表交叉引用您的位数组来节省一些时间,这样您就可以更快地进入下一个素数。

此外,在第一次遇到新的素数 p 时,在消除以后的复合时 - p 剩余的第一个复合倍数将是 p*p,因为之前的所有内容都已被消除。实际上,您只需要将 p 乘以列表中所有剩余的潜在素数,只要您的乘积超出范围(大于直到)就停止。

还有一些很好的概率算法,例如 Miller-Rabin 测试。 维基百科页面是一个很好的介绍。

于 2008-08-29T09:08:27.030 回答
4

除了并行化,您不想在每次迭代时都计算 sqrt(Until)。您还可以假设 2、3 和 5 的倍数,并且只计算 {1,5} 中的 N%6 或 {1,7,11,13,17,19,23,29} 中的 N%30。

您应该能够很容易地并行化因式分解算法,因为第 N 阶段仅取决于第 sqrt(n) 次结果,因此一段时间后不会有任何冲突。但这不是一个好的算法,因为它需要大量的除法。

如果您有保证在读取之前完成的写入器工作包,您还应该能够并行化筛选算法。大多数情况下,作者不应该与读者发生冲突 - 至少一旦你完成了一些条目,他们应该在读者之上至少 N 工作,所以你只需要相当偶尔的同步读取(当 N 超过最后一次同步读取时价值)。您不需要在任意数量的写入器线程之间同步 bool 数组,因为不会出现写入冲突(在最坏的情况下,多个线程会将 true 写入同一位置)。

主要问题是确保任何等待写入的工作人员都已完成。在 C++ 中,您可以使用 compare-and-set 切换到随时等待的 worker。我不是 C# 专家,所以不知道如何使用这种语言,但应该可以使用 Win32 InterlockedCompareExchange 函数。

您也可以尝试基于参与者的方法,因为这样您可以安排参与者使用最低值工作,这可能更容易保证您正在读取筛子的有效部分,而不必在每次增量时锁定总线N。

无论哪种方式,您都必须确保所有工作人员在阅读之前都已超过条目 N,而这样做的成本是在并行和串行之间进行权衡的地方。

于 2008-08-27T20:52:54.093 回答
1

如果没有分析,我们无法判断程序的哪一部分需要优化。

如果您在一个大型系统中,那么可以使用分析器来发现素数生成器是需要优化的部分。

对包含十几个指令的循环进行分析通常不值得 - 与循环体相比,分析器的开销很大,并且改进如此小的循环的唯一方法是更改​​算法以进行更少的迭代. 因此,IME,一旦您消除了任何昂贵的功能并拥有几行简单代码的已知目标,您最好更改算法并安排端到端运行,而不是尝试按指令级别改进代码分析。

于 2008-09-04T20:38:54.093 回答
0

@DrPizza Profiling 仅真正有助于改进实现,它不会揭示并行执行的机会,或建议更好的算法(除非您有其他经验,在这种情况下,我真的很想看看您的分析器)。

我家里只有单核机器,但是运行了一个相当于你的 BitArray 筛子的 Java,以及一个单线程版本的筛子反转 - 将标记素数保存在一个数组中,并使用轮子将搜索空间减少因子五,然后使用每个标记素数以轮的增量标记一个位数组。它还将存储减少到 O(sqrt(N)) 而不是 O(N),这在最大 N、分页和带宽方面都有帮助。

对于 N 的中等值(1e8 到 1e12),可以很快找到直到 sqrt(N) 的素数,之后您应该能够很容易地在 CPU 上并行执行后续搜索。在我的单核机器上,轮式方法在 28 秒内找到高达 1e9 的素数,而您的筛子(将 sqrt 移出循环后)需要 86 秒 - 改进是由于轮式;反转意味着您可以处理大于 2^32 的 N,但会使其变慢。代码可以在这里找到。您也可以在通过 sqrt(N) 之后并行化来自朴素筛子的结果输出,因为在该点之后不会修改位数组;但是,一旦您处理的 N 足够大,以至于数组大小对于整数来说太大了。

于 2008-09-01T00:06:01.740 回答
0

您还应该考虑可能的算法更改。

考虑一下,当您找到它们时,简单地将元素添加到您的列表中可能会更便宜。

也许为您的列表预先分配空间会使构建/填充成本更低。

于 2008-09-17T01:43:13.213 回答
0

你在寻找新的质数吗?这听起来可能很愚蠢,但您可能能够加载某种具有已知素数的数据结构。我敢肯定有人在那里有一个清单。找到计算新数字的现有数字可能要容易得多。

您还可以查看 Microsoft 的Parallel FX Library以使您现有的代码多线程以利用多核系统。通过最少的代码更改,您可以使您的 for 循环多线程。

于 2008-09-17T01:57:54.473 回答
0

有一篇关于埃拉托色尼筛的非常好的文章:埃拉托色尼的真正筛子

它在功能设置中,但大多数优化也适用于 C# 中的过程实现。

两个最重要的优化是从 P^2 而不是 2*P 开始划线,并为下一个素数使用轮子。

对于并发,您可以与 P 并行处理直到 P^2 的所有数字,而无需做任何不必要的工作。

于 2008-09-17T07:15:11.747 回答
-1
    void PrimeNumber(long number)
    {
        bool IsprimeNumber = true;
        long  value = Convert.ToInt32(Math.Sqrt(number));
        if (number % 2 == 0)
        {
            IsprimeNumber = false;
            MessageBox.Show("No It is not a Prime NUmber");
            return;
        }
        for (long i = 3; i <= value; i=i+2)
        {             
           if (number % i == 0)
            {

                MessageBox.Show("It is divisible by" + i);
                IsprimeNumber = false;
                break;
            }

        }
        if (IsprimeNumber)
        {
            MessageBox.Show("Yes Prime NUmber");
        }
        else
        {
            MessageBox.Show("No It is not a Prime NUmber");
        }
    }
于 2015-07-24T07:16:29.133 回答