I was going through this blog which explains how to check whether a number is prime or not in O(1) runtime complexity.
In the comments I found a piece of code which compares the time taken to check for prime numbers using the conventional runtime sieve and the explained compile-time evaluated sieve.
My doubt lies in the slow_is_prime() function on line no. 31.
What does the statement: (Sieve<MAXN>{}).is_prime[n] mean?
I understand that MAXN is the parameter passed to the Sieve struct, which is what we would have done while creating a variable of its type as well, but what significance does the {} braces have?
How is it different from: Sieve<MAXN> a; return a.is_prime[n]; ?
Also, if you tweak the code a little bit and rather than what is given, if you replace the contents of the slow_is_prime function with: Sieve<MAXN> a; return a.is_prime[n];
there is a considerable difference in the runtimes.
I would be grateful to know your views and/or inputs.
My knowledge of C++ is not deep so I am not able to give a convincing answer.
Regarding the empty bracket you mention itâs just sending no parameter to the constructor of the structure, like if you call vector<int>{}. Try for example: cout << (vector<int>{}).size() and see the output is 0 but if you call cout << (vector<int>{7}).size() you obtain 1.
My intuition about the differences in running times is that when you call (Sieve<MAXN>{}).is_prime[n] a new instance of the object is created and therefore the sieve is recalculated. It may be the case when you change that to:
Sieve<MAXN> a;
return a.is_prime[n];
the compiler use the fact that âaâ never changes and refere to the same instance in every call to the function. Maybe it depends on the optimization flags.
Iâm not sure if what I say is correct, so donât take it as confirmed truth.
Arenât constructors called like other functions, using parentheses --> () ?
And if the {} mean that we are creating an object, then the runtime reasoning seems to make sense.
Thank you for the inputs!
means invoke the default constructor, then the returned object is set to empty. So it involves an additional operation. Think of it as invoking constructor like below
vector<int> vec = {};
Now consider this alternative invocation written below
(Sieve<MAXN>()).is_prime[n]
means invoke the default constructor, then use the returned object. Think of it as invoking constructor like below
vector<int> vec;
Hence, (Sieve()).is_prime[n] performs slightly better than (Sieve{}).is_prime[n]
Regarding your next question why explicit description improves the performance even when not declared as a static constexpr.
Sieve<MAXN> dynamic;
return dynamic.is_prime[n];
this translates to âdynamicâ is constructed as a sieve and is being used by the function. Seeing that instruction is to repeatedly create and destroy the object âdynamicâ after doing a return, compiler optimises it and doesnât construct and destroy s again and again.
This is not what I meant by the second part of my question.
A few articles suggested that an enum declared as constexpr is always evaluated at compile time( functions may or may not be). So whether we declare dynamic as a constexpr or not does not really make a difference.
This trick isnât particularly useful I think. If you try it on larger numbers the judge will throw you an error. But yes the power of C++ is the ability to use an O(N Log^2n) solution in a problem that expects an O(NlogN) solution.