primes - Eratosthenes的筛子有巨大的“ overdraw ”-毕竟Sundaram更好吗？

标准的Eratosthenes筛网可多次剔除大多数复合材料。实际上，唯一没有被多次标记的是恰好是两个素数的乘积。自然地，随着筛网变大，透支会增加。

对于奇数筛子（即无偶数筛子），透支命中率达到100％，n = 3,509,227，其中1,503,868个复合材料和1,503,868个已经划掉的数字被划掉。当n = 2 ^ 32时，透支额上升到134.25％（透支2,610,022,328对流行次数1,944,203,427 =（2 ^ 32/2）-203,280,221）。

如果-仅在-智能地计算循环极限时，Sieve of Sundaram-在maths.org处有另一个说明-可能会更聪明。但是，这是我所见过的资料似乎被“优化”所掩盖的东西，而且似乎每次未优化的Sundaram都被赔率只有Eratosthenes击败。

有趣的是，两者都创建了完全相同的最终位图，即位k对应于数字（2 * k + 1）的位图。因此，两种算法都必须最终设置完全相同的位，它们的处理方式不同。

有人对竞争激烈的Sundaram有亲身实践经验吗？它能击败古希腊吗？

我已经缩小了我的小筛子（2 ^ 32，希腊唯一的赔率）的代码，并将段大小调整为256 KB，这在旧版Nehalem上具有256 KB L2的最佳性能，在新CPU上（甚至尽管后者对更大的细分受众群宽容得多）。但是现在我撞到了砖墙，血腥的筛子仍然需要8.5秒的时间来初始化。从硬盘上加载筛子不是一个很有吸引力的选择，并且多线程很难以可移植的方式进行（因为诸如boost之类的库往往使活动扳手变得轻便）。

Sundaram可以从启动时间缩短几秒钟吗？

附言：这样的透支不是问题，并且将由L2缓存吸收。关键是标准的Eratosthenes似乎完成的工作比必要的多一倍，这表明有可能更快地完成更少的工作。

最佳答案

由于没有人接受“ Sundaram vs. Eratosthenes”问题，所以我坐下来分析了它。结果：经典的Sundaram的透支率比仅赔率的Eratosthenes高得多；如果应用明显的小优化，则透支完全相同-出于显而易见的原因。如果您修复了Sundaram以避免完全透支，那么您会得到Pritchard's Sieve之类的东西，它要复杂得多。

exposition of Sundaram's Sieve in Lucky's Notes可能是迄今为止最好的。稍微改写以使用假设类型（即非标准且此处未提供）的bitmap_t看起来像这样。为了测量透支位图类型，需要执行与BTS（位测试和设置）CPU指令相对应的操作，该指令可通过Wintel编译器和gcc的MinGW版本固有的_bittestandset（）获得。内在函数对性能非常不利，但对计算透支非常方便。

注意：要筛选最多N个素数，将调用max_bit = N / 2的筛子；如果结果位图的第i位被设置，则数字（2 * i + 1）是复合的。该函数的名称为“ 31”，因为对于大于2 ^ 31的位图，索引数学运算会中断；因此，此代码只能筛选最多2 ^ 32-1的数字（对应于max_bit

uint64_t Sundaram31_a (bitmap_t &bm, uint32_t max_bit)
{
   assert( max_bit <= UINT32_MAX / 2 );

   uint32_t m = max_bit;
   uint64_t overdraw = 0;

   bm.set_all(0);

   for (uint32_t i = 1; i < m / 2; ++i)
   {
      for (uint32_t j = i; j <= (m - i) / (2 * i + 1); ++j)
      {
         uint32_t k = i + j + 2 * i * j;

         overdraw += bm.bts(k);
      }
   }

   return overdraw;
}

幸运的绑定在j上是准确的，但i上的绑定非常松散。拧紧它，并丢失我为使代码看起来更像网络上的通用博览会而添加的m别名，我们得到：

uint64_t Sundaram31_b (bitmap_t &bm, uint32_t max_bit)
{
   uint32_t i_max = uint32_t(std::sqrt(double(2 * max_bit + 1)) - 1) / 2;
   uint64_t overdraw = 0;

   bm.set_all(0);

   for (uint32_t i = 1; i <= i_max; ++i)
   {
      for (uint32_t j = i; j <= (max_bit - i) / (2 * i + 1); ++j)
      {
         uint32_t k = i + j + 2 * i * j;

         overdraw += bm.bts(k);
      }
   }

   return overdraw;
}

assert已被转储以减少噪声，但实际上仍然有效且必要。现在是时候降低强度了，将乘法变成迭代加法：

uint64_t Sundaram31_c (bitmap_t &bm, uint32_t max_bit)
{
   uint32_t i_max = uint32_t(std::sqrt(double(2 * max_bit + 1)) - 1) / 2;
   uint64_t overdraw = 0;

   bm.set_all(0);

   for (uint32_t i = 1; i <= i_max; ++i)
   {
      uint32_t n = 2 * i + 1;
      uint32_t k = n * i + i;   // <= max_bit because that's how we computed i_max
      uint32_t j_max = (max_bit - i) / n;

      for (uint32_t j = i; j <= j_max; ++j, k += n)
      {
         overdraw += bm.bts(k);
      }
   }

   return overdraw;
}

将循环条件转换为使用k可以使我们失去j；到现在为止，事情应该看起来非常熟悉了...

uint64_t Sundaram31_d (bitmap_t &bm, uint32_t max_bit)
{
   uint32_t i_max = uint32_t(std::sqrt(double(2 * max_bit + 1)) - 1) / 2;
   uint64_t overdraw = 0;

   bm.set_all(0);

   for (uint32_t i = 1; i <= i_max; ++i)
   {
      uint32_t n = 2 * i + 1;
      uint32_t k = n * i + i;   // <= max_bit because that's how we computed i_max

      for ( ; k <= max_bit; k += n)
      {
         overdraw += bm.bts(k);
      }
   }

   return overdraw;
}

事情看起来像他们所做的那样，是时候分析数学是否需要进行某些明显的小改变了。证明供读者练习。

uint64_t Sundaram31_e (bitmap_t &bm, uint32_t max_bit)
{
   uint32_t i_max = unsigned(std::sqrt(double(2 * max_bit + 1)) - 1) / 2;
   uint64_t overdraw = 0;

   bm.set_all(0);

   for (uint32_t i = 1; i <= i_max; ++i)
   {
      if (bm.bt(i))  continue;

      uint32_t n = 2 * i + 1;
      uint32_t k = n * i + i;   // <= m because we computed i_max to get this bound

      for ( ; k <= max_bit; k += n)
      {
         overdraw += bm.bts(k);
      }
   }

   return overdraw;
}

唯一不同于经典赔率的Eratosthenes（名称除外）唯一的区别是k的初始值，对于古希腊语，通常为(n * n) / 2。但是，用2 * i + 1替换为n时，差异变为1/2，四舍五入为0。因此，Sundaram's是仅赔率的Eratosthenes，而没有“优化”的方法来跳过复合词，以避免至少部分交叉。已经划掉的数字。 i_max的值与希腊文的max_factor_bit相同，只是使用完全不同的逻辑步长得出并使用略有不同的公式计算得出。

PS：在代码中多次看到overdraw之后，人们可能会想知道它实际上是什么...将数字筛选直至2 ^ 32-1（即完整的2 ^ 31位图），Sundaram的透支8,643,678,027（约2 * 2 ^ 32）或444.6％;小幅修复将其变成仅赔率的Eratosthenes，透支额变为2,610,022,328或134.2％。