Corei13's blog

By Corei13, 9 years ago, In English

The main challenges with compile time computations are

  • we can only work with constants (so no looping is possible)
  • maximum recursion depth is very limited compared to runtime computations (for example, maximum recursion depth is only 900 in g++)

Here is an example of how to use template meta programming for compile time computations. The example shows how to implement primality checking in compile time, but the same principle can be applied to other problems. For instance, in the main function, replacing Generate <level, Prime>::value by Generate <level, Sqrt>::value will generate integer square roots for all numbers between [0, 2^level).

#include <bits/stdc++.h>

using namespace std;

namespace Helpers {
    template <int lhs, int rhs>
    struct Plus {
        static const int value = lhs + rhs;
    };
    struct True {
        static const bool value = true;
    };
    struct False {
        static const bool value = false;
    };
    // Array <T, T args...> contains the array {args...} of size ::size at ::value
    // For example if A = Array <int, 1, 2, 3>, then A::value[] = {1, 2, 3} and A::size = 3
    template <typename T, T... args>
    struct Array {
        static const T value[sizeof...(args)];
        static const int size = sizeof...(args);
    };
    template <typename T, T... args>
    const T Array <T, args...>::value[sizeof...(args)] = {args...};
}

// Sqrt <N>::value is the integer square root of N
template <int N>
struct Sqrt {
    template <int lo, int hi>
    struct Helper {
        static const int mid = (lo + hi + 1) / 2;
        static const int value = conditional < (N / mid < mid), Helper < lo, mid - 1 >, Helper <mid, hi> >::type::value;
    };
    template <int n>
    struct Helper <n, n> {
        static const int value = n;
    };
    static const int value = Helper <0, N>::value;
};


// Prime <N>::value is true if and only if N is a prime
template <int N>
struct Prime {
    // Helper::value is true iff any prime in [lo, hi] divides N
    template <int lo, int hi>
    struct Helper {
        static const int mid = (lo + hi) / 2;
        static const bool value = conditional < Helper <lo, mid>::value, Helpers::True, Helper < mid + 1, hi >>::type::value;
    };
    template <int d>
    struct Helper <d, d> {
        static const bool value = Prime <d>::value and N % d == 0;
    };
    static const bool value = not conditional < (N <= 1), Helpers::True, Helper <1, Sqrt <N>::value> >::type::value;
};

/*
    Generate <N, F> contains the Helpers::Array with ::value = {F<0>::value, ..., F<2 ^ N - 1>::value} at ::value
    Example:
        using A = Generate<5, Sqrt>::value;
        for (int i = 0; i < A::size; ++i) {
            cout << A::value[i] << endl;
        }
*/

template <int N, template <int> class F>
struct Generate {
    template <int n, int... args>
    struct Helper {
        using value = typename Helper < n - 1, args..., Helpers::Plus <args, sizeof...(args)>::value... >::value;
    };

    template <int... args>
    struct Helper <0, args...> {
        using value = Helpers::Array <decltype(F <0>::value), F <args>::value...>;
    };
    using value = typename Helper <N, 0>::value;
};


int main(int argc, char const *argv[]) {
    const int level = 10; // for primes upto 2^level
    using A = Generate <level, Prime>::value;
    cout << A::size << endl;
    for (int i = 0; i < A::size; ++i) {
        cout << "> " << boolalpha << i << ' ' << A::value[i] << endl;
    }
    return 0;
}
  • Vote: I like it
  • +60
  • Vote: I do not like it

»
9 years ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

with c++11 you may replace some templates with constexpr functions.

constexpr int intSqrt(int n, int l, int r) {
    #define m ((l+r) / 2)
    return l + 1 == r ?
           l :
           (m * 1LL * m <= n ? intSqrt(n, m, r) : intSqrt(n, l, m));
    #undef m
}

constexpr int intSqrt(int n) {
    return intSqrt(n, 0, n + 1);
}

constexpr bool hasDivisors(int n, int l, int r) {
    return l + 1 == r ? 
           n % l == 0 :
           (hasDivisors(n, l, (l + r) / 2) || hasDivisors(n, (l + r) / 2, r));
}

constexpr bool isPrime(int n) {
    return n >= 2 && !hasDivisors(n, 2, intSqrt(n) + 1);
}

It becomes less verbose I believe.

After that you may put it in template to force compile-time execution like

template <int n>
 class Prime {
      static const bool value = isPrime(n);
 }
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is it possible to store the data generated in compile time for runtime usage? For example, it is possible to use constexpr to generate std::tuple object, but to access element from tuples we need to call get() where n should be a compile time constant. Is there any way to store the data in array / vector etc without template?

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 5   Vote: I like it 0 Vote: I do not like it

      UPD: Thats completely wrong

      Well, vector/etc are created in runtime( I hardly can imagine compile time memory allocation) so you can't put something to them in compile time, but you can generate values in compile time and put them without calculating in runtime like:

      for(int i = 0; i < n; ++i) {
         v[i] = Prime<i>::value; //Prime<i>::value calculated in compile time
         v[i] = isPrime(n); // here it's not guaranteed to be calculated in compile time
      }
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        You can't use Prime<i>::value when i is not a constant.

        Also you can put something in vector etc in compile time if they are const. For example, You can change the implementation of Helpers::Array to following to deal with vectors in compile time. (However in that case you have to replace using value = Helpers::Array <decltype(F <0>::value), F <args>::value...> with using value = Helpers::Array <int, F <args>::value...> in the implementation of Generate<> template)

            template <typename T, T... args>
            struct Array {
                static const vector<T> value;
                static const int size = sizeof...(args);
            };
        
            template <typename T, T... args>
            const vector<T> Array <T, args...>::value = {args...};
        
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          Rev. 4   Vote: I like it 0 Vote: I do not like it

          Ah, sure, that was wrong.

          we could do something like:

          #include <array>
          #include <iostream>
          
          template<int ... N>
          struct seq
          {
              using type = seq<N...>;
          
              static const std::size_t size = sizeof ... (N);
          
              template<int I>
              struct push_back : seq<N..., I> {};
          };
          
          template<int N>
          struct genseq : genseq<N-1>::type::template push_back<N-1> {};
          
          template<>
          struct genseq<0> : seq<> {};
          
          template<int N>
          using genseq_t = typename genseq<N>::type;
          
          template <int n>
          struct Twice {
          	static const int value = n * 2;
          };
          
          template<int...N>
          auto repeat(seq<N...>) -> std::array<int, sizeof...(N)> 
          {
             //unpack N
             return {Twice<N>::value...};
          }
          
          
          template <int n>
          std::array<int, n> go() {
          	return repeat(genseq_t<n>{});
          }
          
          int main() {
          	constexpr const int n =5;
          	auto a = go<n>();
          	for(int i = 0; i < n; ++i) {
          		std::cout << a[i] << ' ' ;
          	}
          }
          
          

          First of all genseq is standard thing to generate [0...n-1], then I return an array of doubled values

          We could replace with any template that transform int to some value (like checking if number is prime)

          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            This should work, but we are back to templates from constexpr, it seems there is no way to use only constexpr to store values in containers.

            Also note that this version will exceed template-depth for large enough n (900 for g++ by default). You have to generate by bisecting for larger values.

            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Ah, I see what you meant: we need templates here, and I'm not sure if it's possible to do that in compile time using only constexprs.

              But, using your code, it's possible to have template for "generator" visible to user, but write main logic (prime checking) in constexprs.

              I'll think on eliminating templates completely.

»
9 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Now I wonder, does OJ and ACM normally have compilation time limit? If not, then this could be used to reduce running time in many cases..

»
9 years ago, # |
Rev. 3   Vote: I like it +21 Vote: I do not like it

Am I right that this code is correct for C++14?

I don't have opportunity to compile it, cause relaxing requirements on constexpr will appears only in gcc 5.0.

If the answer is "Yes", welcome to the new era of compile-time precomputations :D