### tweety's blog

By tweety, history, 5 weeks ago, ,

Hello fellow people of Codeforces

I hope everyone doing well in these uncertain and unprecedented times. I wanted to share this cool C++20 trick that I learned recently.

Check out this cool implementation of is_prime(n) to test if n integer is prime in O(1) runtime (without any runtime precomputation!)

bool is_prime(int n);

This code computes primes up to MAXN during compilation and stores them in a table right in the compiled binary. On a runtime is_prime(n) call, it queries the compiled table to find the result. Check this compiled assembly to find the sieve mask baked in the binary: https://godbolt.org/z/G6o84x.

This trick is achieved by passing the constructed Sieve as a template argument, which is always evaluated on compile-time. If you compile this code using older C++ standard, you will get the error:

error: a non-type template parameter cannot have type 'Sieve<MAXN>'


However, since C++20, non-type template parameter can have any LiteralType (note). In short, it is possible to compile-time compute an instance of any class with a constexpr constructor.

Here is a time test of compile-time vs run-time sieve computation:

main.cpp

Compiled with GCC 9.3.0 using the command g++ -std=c++2a main.cpp. This is the execution output on my laptop:

Runtime ans: 90. Elapsed (ms): 1008
Compiletime ans: 90. Elapsed (ms): 0


Of course no one re-computes sieve 1000 times, this is done here for the sole purpose of showing that the algorithm is not computing sieve in run time 1000 times.

• +166

 » 5 weeks ago, # |   0 Nice :) I wonder if you can do this in earlier versions of C++ by having just the is_prime array be compile-time computed (instead of the Sieve instance)It might be worth it to try space-saving tricks like bit-packing and wheel sieve to increase max_N, the runtime penalty should be small, bit-packing should increase max_n by 8x, the simplest wheel sieve (omit all even numbers) should increase it further by 2x.
 » 5 weeks ago, # | ← Rev. 2 →   +27 I think this can be done with C++14. Also you don't need a Wrapper class: bool fast_is_prime(int n) { static constexpr Sieve s; return s.is_prime[n]; } Runtime ans: 100. Elapsed (ms): 583 Compiletime ans: 100. Elapsed (ms): 0 See C++14 on ideone
•  » » 5 weeks ago, # ^ |   +10 That's cool! I thought declaring something as constexpr only hints the compiler to compute it during compilation and I had to pass a constexpr constructor as a template argument to force it to be computed compile-time. But seems like declaring static constexpr works too
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 constexpr on a function declaration is a hint that (under certain conditions) it may be evaluated at compile time and the result be stored in the read-only part of the binary. However, if you declare a "variable" constexpr the compiler is forced to compute the right-hand side of the assignment. You cannot change the value afterwards (constexpr implies const). If you want an actual variable you may use constinit from C++20. If you always want compile time evaluation of a function, you can declare it consteval with the latest standard. I'd say, these new keywords may be rarely of any use in competitive programming.
 » 5 weeks ago, # |   0 Do you have more tricks up your sleeve? If so please make a series or something like that. I found this really helpful.
•  » » 5 weeks ago, # ^ |   0 Why is it helpful?
•  » » » 5 weeks ago, # ^ |   0 Cause it interesting.
•  » » 5 weeks ago, # ^ |   +63 I think he has a few more tricks up his sieve...
•  » » » 5 weeks ago, # ^ |   -6 Nice!
 » 5 weeks ago, # |   0 Amazing, provide a new idea to cost compile-time instead of exec-time ! It may useful for particluar questions since CP only care about exec-time.But: ‘constexpr’ loop iteration count has limit of 262144 (use ‘-fconstexpr-loop-limit=’ to increase the limit), and we can't use -fconstexpr-loop-limit= parameter in CP, sadly this ideal may can't put prime sieve in practice even ...._.._ provide C++14(So C++17 works) version of your idea.
 » 5 weeks ago, # |   -27 https://www.cs.utexas.edu/users/misra/scannedPdf.dir/linearSieve.pdf the original paper
•  » » 5 weeks ago, # ^ |   +14 Unless I’m misreading something, this post is about moving the computation into the compilation, not about how to actually write a prime sieve (which is what the paper is about).