Вопрос по sorting, optimization, refactoring, c++, algorithm – Сито из эратосфена: немного оптимизировано

3

После поиска в сети я узнал, что побитовая версия сита из эратосфена довольно эффективна. Проблема в том, что я не могу понять математику / метод, который он использует.

Версия, которой я был занят, выглядит следующим образом:

#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);
}

Пункты, которые я понял (пожалуйста, поправьте меня, если я ошибаюсь):

Оператор в строке 1 проверяет, является ли число составным.Оператор в строке 2 помечает число «n» как составное.Программа хранит значение 0 или 1 с битом типа int. Это имеет тенденцию уменьшать использование памяти до x / 32. (x - это размер, который был бы использован, если бы int использовался для хранения 0 или 1, а не как в моем решении выше)

Точки, которые идут сейчас над моей головой:

Как работает функция в LINE 1? Как функция проверяет, является ли число составным или нет.Как функция в LINE 2 устанавливает бит.Я также узнал, что побитовое сито также эффективно по времени. Это из-за использования только побитовых операторов или что-то еще способствует этому.

Есть идеи или предложения?

Ваш Ответ

1   ответ
4

флаг без знака [MAX >> 6] = {0};

водоразделыMAX на 64, но еслиMAX не является точным кратным 64, массив - это один элемент.

Строка 1: Давайте разберем это:

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

flag[n>>6] (n >> 6 = n / 64) дает 32-разрядное целое число, которое содержит значение бита дляn / 2.

Поскольку только «нечетные» числа являются возможными простыми числами, разделитеn двумя:(n>>1).

1<<((n>>1)&31) дает нам бит, соответствующийn/2 в пределах0..31 - (& 31 удостоверяется, что это "в пределах досягаемости").

Наконец, используйте& объединить значение слева со значением справа.

Таким образом, результат верен, если элемент дляn имеет битовый номерn modulo 32 установлен.

Вторая строка по сути та же концепция, просто она использует|= (или равно), чтобы установить бит, соответствующий кратному.

@Casey: Дох, ты прав ... Mats Petersson
Большая помощь!! Благодарю. Наконец, после тщательного изучения нескольких случаев я понял, что там происходит. Последняя вещь. Здесь вы сказали: «Поскольку только« нечетные »числа являются возможными простыми числами, разделите n на два: (n >> 1).», Но в этой строке «для (i = 3; i <LIM; i + = 2)» мы не являемся пропуская четные числа. тогда зачем использовать n >> 1. Arman Singh
Массив не в два раза больше, чем нужно:n >> 6 == n / 64 неn / 32. Casey
Потому что таблица (битовая маска) все равно должна быть вдвое больше и содержать кучу единиц для всех четных чисел. Наличие вдвое большего размера таблицы также повлияет на производительность. Mats Petersson

Похожие вопросы