Yarin Sieve

general
, ,
1

Hello Everyone,

I was trying to explore the best implementations for some popular algorithms, when I found one called \red{\text{Yarin Sieve}}. I remember reading this for the first time in my first year of Engineering (2018) but didn’t understand even a bit of it. I found this now while I was checking the notes and wanted to test if it does work or not. It’s quite interesting to note that this runs at least 3 times faster than the \red{\text{Naive Sieve}} implementation most of us use in CP. This will be helpful when the time/memory limit is strict.

The Implementation of Yarin Sieve in CPP: 
// This is the famous "Yarin Sieve", for use when memory is tight

#define MAXSIEVE 100000001
#define MAXSIEVEHALF (MAXSIEVE >> 1)
#define MAXSQRT 5000 // sqrt(MAXSIEVE) / 2
#define isprime(n) ((is_prime[n >> 4] & (1 << ((n >> 1) & 7))) && ((n & 1) || (n == 2)))

char is_prime[MAXSIEVE / (1 << 4) + 2];

int Yarin() {
    auto start = chrono::high_resolution_clock::now();
    memset(is_prime, (1 << (1 << 3)) - 1, sizeof(is_prime));
    is_prime[0] = 0xFE;
    for(int i = 1; i < MAXSQRT; i++) {
        if(is_prime[i >> 3] & (1 << (i & 7))) {
            for(int j = 2 * i * (i + 1); j < MAXSIEVEHALF; j += (i << 1) + 1) {
                is_prime[j >> 3] &= ~(1 << (j & 7));
            }
        }
    }
    auto end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
    cerr << "Time taken by function: " << duration.count() << " microseconds" << '\n';
    return 0;
}

The implementation is fuzzy. Refer Codeforces blog for the explanation.

Here are the benchmarks.

Sieve 
#include <bits/stdc++.h>
using namespace std;

#define SIEVE_SIZE 100000001
#define MAXSQRT 10001

bitset<SIEVE_SIZE> is_prime;

int sieve() {

    auto start = chrono::high_resolution_clock::now();
    is_prime.set(2);

    for(int i = 3; i < SIEVE_SIZE; i += 2) {
        is_prime.set(i);
    }

	for(int i = 3; i < MAXSQRT; i += 2) {
		if(is_prime.test(i))
			for(int j = i * i; j < SIEVE_SIZE; j += i)
                is_prime.reset(j);
	}
    auto end = chrono::high_resolution_clock::now();

    auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
    cerr << "Time taken by function: " << duration.count() << " microseconds" << '\n';

    return 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if(!sieve()) {
        for(int i = 0; i < SIEVE_SIZE; i++) {
            if(is_prime.test(i))
                cout << i << '\n';
        }
    }
    return 0;
}
Yarin Sieve 
#include <bits/stdc++.h>
using namespace std;

// Yarin Sieve
// This is the famous "Yarin Sieve", for use when memory is tight

#define MAXSIEVE 100000001
#define MAXSIEVEHALF (MAXSIEVE >> 1)
#define MAXSQRT 5000
#define isprime(n) ((is_prime[n >> 4] & (1 << ((n >> 1) & 7))) && ((n & 1) || (n == 2)))

char is_prime[MAXSIEVE / (1 << 4) + 2];

int Yarin() {
    auto start = chrono::high_resolution_clock::now();
    memset(is_prime, (1 << (1 << 3)) - 1, sizeof(is_prime));
    is_prime[0] = 0xFE;
    for(int i = 1; i < MAXSQRT; i++) {
        if(is_prime[i >> 3] & (1 << (i & 7))) {
            for(int j = (i << 1) + i + 1; j < MAXSIEVEHALF; j += (i << 1) + 1) {
                is_prime[j >> 3] &= ~(1 << (j & 7));
            }
        }
    }
    auto end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
    cerr << "Time taken by function: " << duration.count() << " microseconds" << '\n';
    return 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if(!Yarin()) {
        for(int i = 0; i < MAXSIEVE; i++) {
            if(isprime(i))
                cout << i << '\n';
        }
    }
    return 0;
}
Yarin (slightly Optimised) 
#include <bits/stdc++.h>
using namespace std;

// Yarin Sieve
// This is the famous "Yarin Sieve", for use when memory is tight

#define MAXSIEVE 100000001
#define MAXSIEVEHALF (MAXSIEVE >> 1)
#define MAXSQRT 5000
#define isprime(n) ((is_prime[n >> 4] & (1 << ((n >> 1) & 7))) && ((n & 1) || (n == 2)))

char is_prime[MAXSIEVE / (1 << 4) + 2];

int Yarin() {
    auto start = chrono::high_resolution_clock::now();
    memset(is_prime, (1 << (1 << 3)) - 1, sizeof(is_prime));
    is_prime[0] = 0xFE;
    for(int i = 1; i < MAXSQRT; i++) {
        if(is_prime[i >> 3] & (1 << (i & 7))) {
            for(int j = 2 * i * (i + 1); j < MAXSIEVEHALF; j += (i << 1) + 1) {
                is_prime[j >> 3] &= ~(1 << (j & 7));
            }
        }
    }
    auto end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
    cerr << "Time taken by function: " << duration.count() << " microseconds" << '\n';
    return 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if(!Yarin()) {
        for(int i = 0; i < MAXSIEVE; i++) {
            if(isprime(i))
                cout << i << '\n';
        }
    }
    return 0;
}
Benchmarks 
suman@Skynet:~$ g++ -o Sieve Sieve.cpp -O2 -std=c++17
suman@Skynet:~$ ./Sieve > OUTPUT1
Time taken by function: 534290 microseconds
suman@Skynet:~$ ./Sieve > OUTPUT1
Time taken by function: 532301 microseconds
suman@Skynet:~$ ./Sieve > OUTPUT1
Time taken by function: 535835 microseconds
suman@Skynet:~$ ./Sieve > OUTPUT1
Time taken by function: 526626 microseconds
suman@Skynet:~$ ./Sieve > OUTPUT1
Time taken by function: 540165 microseconds
Average: 533843.4 microseconds

suman@Skynet:~$ g++ -o Yarin Yarin.cpp -O2 -std=c++17
suman@Skynet:~$ ./Yarin > OUTPUT2
Time taken by function: 174534 microseconds
suman@Skynet:~$ ./Yarin > OUTPUT2
Time taken by function: 166747 microseconds
suman@Skynet:~$ ./Yarin > OUTPUT2
Time taken by function: 179019 microseconds
suman@Skynet:~$ ./Yarin > OUTPUT2
Time taken by function: 182238 microseconds
suman@Skynet:~$ ./Yarin > OUTPUT2
Time taken by function: 164615 microseconds
Average: 173430.6 microseconds

suman@Skynet:~$ g++ -o Yarin_Optimised Yarin_Optimised.cpp -O2 -std=c++17
suman@Skynet:~$ ./Yarin_Optimised > OUTPUT3
Time taken by function: 156206 microseconds
suman@Skynet:~$ ./Yarin_Optimised > OUTPUT3
Time taken by function: 150556 microseconds
suman@Skynet:~$ ./Yarin_Optimised > OUTPUT3
Time taken by function: 171621 microseconds
suman@Skynet:~$ ./Yarin_Optimised > OUTPUT3
Time taken by function: 170140 microseconds
suman@Skynet:~$ ./Yarin_Optimised > OUTPUT3
Time taken by function: 155482 microseconds
Average: 160801.0 microseconds

suman@Skynet:~$ cmp OUTPUT1 OUTPUT2
suman@Skynet:~$ cmp OUTPUT2 OUTPUT3

The above benchmarks show how fast Yarin Sieve is - not more than 0.2 seconds is required for generating primes below 10^8. (All credits go to respective owners).

Happy Coding :slightly_smiling_face:

2 Likes