筛选eratosthenes：逐位优化 [英] Sieve of eratosthenes : bit wise optimized

问题描述

搜索网以后，我知道eratosthenes筛的位版本是相当高效的。
问题是我无法理解它使用的数学/方法。

我一直在忙的版本看起来像这样：

  #define MAX 100000000 
 #define LIM 10000 
 
无符号标志[MAX>> 6] = {0}; 
 
 #define ifc（n）（flag [n> 6]&（1<<（（n> 1）& 31）））// LINE 1 
 #define isc（n）（flag [n> 6] | =（1 <（（n> 1）& 31）））// LINE 2 
 
 void sieve（）{
 unsigned i，j，k; （i = 3; i  if（！ifc（i））
 for（j = i * i，k = i < j  isc（j）; 
} 
  

我理解的点（如果我错了，请纠正我） p>

1. 第1行中的语句检查该数字是否是复合的。


2. 第2行中的语句标记数字' n'作为复合。


3. 程序将值0或1存储在int的某位。这倾向于将内存使用减少到x / 32。 （x是本来使用的大小，用于存储0或1，而不是像我上面的解决方案中那样）

现在我的头上方的点：

1. LINE 1的功能是如何工作的。


2. 如何在LINE 2中的函数设置位。


3. 我也知道按位筛是时间效率为
   。是因为只使用了位运算符，还是使用了
   ，还有其他原因也有助于它。

建议？

解决方案

技术上，代码中还有一个错误：

unsigned flag [MAX >> 6] = {0};

将 MAX 但如果 MAX 不是64的精确倍数，则该数组是一个元素short。

分开：

 （flag [n> 6]&（1<<（（n& 1）& 31）））
  

flag [n& 6] （n> 6 = n / 64）给出保存<$ c $的位值的32位整数c> n / 2 。

由于只有奇数数字是可能的素数，所以 n 除以两个： n> 1）。

1<<（（n> 1）& 31）到 0..31 - （& 31 n / 2 c $ c>确保它在范围）。

最后，使用& 将左侧的值与右侧的值组合。

因此，如果 n 的元素的位数 n modulo 32，结果为true set。

第二行基本上是相同的概念，只是它使用 | = 位对应的倍数。

After searching the net I came to know that the bit-wise version of the sieve of eratosthenes is pretty efficient. The problem is I am unable to understand the math/method it is using.

The version that I have been busy with looks like this:

#define MAX 100000000
#define LIM 10000

unsigned flag[MAX>>6]={0};

#define ifc(n) (flag[n>>6]&(1<<((n>>1)&31)))         //LINE 1
#define isc(n) (flag[n>>6]|=(1<<((n>>1)&31)))        //LINE 2

void sieve() {
    unsigned i, j, k;
    for(i=3; i<LIM; i+=2)
        if(!ifc(i))
            for(j=i*i, k=i<<1; j<LIM*LIM; j+=k)
                isc(j);
}

Points that I understood (Please correct me if I am wrong):

1. Statement in line 1 checks if the number is composite.
2. Statement in line 2 marks the number 'n' as composite.
3. The program is storing the value 0 or 1 at a bit of an int. This tends to reduce the memory usage to x/32. (x is the size that would have been used had an int been used to store the 0 or 1 instead of a bit like in my solution above)

Points that are going above my head as of now :

1. How is the finction in LINE 1 functioning.How is the function making sure that the number is composite or not.
2. How is function in LINE 2 setting the bit.
3. I also came to know that the bitwise sieve is timewise efficient as well. Is it because of the use of bitwise operators only or something else is contributing to it as well.

Any ideas or suggestions?

解决方案

Technically, there is a bug in the code as well:

unsigned flag[MAX>>6]={0};

divides MAX by 64, but if MAX is not an exact multiple of 64, the array is one element short.

Line 1: Let's pick it apart:

 (flag[n>>6]&(1<<((n>>1)&31)))

The flag[n>>6] (n >> 6 = n / 64) gives the 32-bit integer that holds the bit value for n / 2.

Since only "Odd" numbers are possible primes, divide n by two: (n>>1).

The 1<<((n>>1)&31) gives us the bit corresponding to n/2 within the 0..31 - (& 31 makes sure that it's "in range").

Finally, use & to combine the value on the left with the value on the right.

So, the result is true if element for n has bit number n modulo 32 set.

The second line is essentially the same concept, just that it uses |= (or equal) to set the bit corresponding to the multiple.

这篇关于筛选eratosthenes：逐位优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！