Compile-Time Calculations using C++ Templates
Tags: cpp, programming, tutorial, beginners
Published: 2023-03-10 16:27:53

C++ templates are a powerful tool that allows you to write generic code that can be used with different data types. One of the less commonly known features of C++ templates is the ability to perform compile-time calculations. This can be very useful in situations where you need to perform calculations that can be determined at compile-time, such as computing the size of an array or a constant value. In this article, we'll explore how to use C++ templates to do compile-time calculations.

## What are Compile-Time Calculations?

Compile-time calculations are calculations that can be evaluated at compile-time, rather than at run-time. This means that the value of the calculation is known before the program runs. This can have several advantages, such as avoiding the overhead of performing the calculation at run-time and enabling the compiler to perform optimizations that may not be possible with run-time calculations.

## Using C++ Templates for Compile-Time Calculations

To use C++ templates for compile-time calculations, we can define a template class or function that takes one or more arguments and performs the calculation. The result of the calculation is then used as a template parameter, which can be used in other parts of the program.

One commonly used example is to write a function that calculates the power of a number. The following implementation is frequently found in many sources:

```cpp
template <signed B, unsigned N>
struct pow {
    static const int value = B * pow<B, N - 1>::value;
};

template <signed B>
struct pow<B, 0> {
    static const int value = 1;
};

int main() {
    constexpr auto res = pow<-3, 5>::value;
    std::cout << res << std::endl; // output: -243
    return 0;
}
```

In the above implementation, we can see that the base case for the recursion is when `N` is 0, in which case is handled by the specialization `pow<B, 0>`.

As we can see, it is tedious and non-intuitive to write a "duplicated" base case. With the help of `constexpr` keyword and `if constexpr` support from C++17, we can implement the power function in a more intuitive and concise way, just like writing a normal function.

```cpp
template <signed B, unsigned N>
constexpr auto pow() {
    if constexpr (N == 0) {
        return 1;
    } else {
        return B * pow<B, N - 1>();
    }
}

int main() {
    constexpr auto res = pow<-3, 5>();
    std::cout << res << std::endl; // output: -243
    return 0;
}
```

Furthermore, we can easily evolve the above implementation to make it support the positive/negative power calculation of an integer or a float number. In addition, we can also optimize the algorithm to improve the time complexity from `O(N)` to `O(log N)`.

```cpp
template <typename T, signed N>
constexpr T pow(const T base) {
    if constexpr (N < 0) {
        return 1 / pow<T, -N>(base);
    }
    if constexpr (N == 0) {
        return 1;
    }
    if constexpr ((N & 1) == 0) {
        return pow<T, N / 2>(base * base);
    }
    return base * pow<T, N / 2>(base * base);
}

int main() {
    constexpr auto m = pow<int, 3>(-3);
    std::cout << m << std::endl; // output: -27

    constexpr auto n = pow<int, -3>(-3);
    std::cout << n << std::endl; // output: 0

    constexpr auto p = pow<double, 3>(2.5);
    std::cout << p << std::endl; // output: 15.625

    constexpr auto q = pow<double, -3>(2.0);
    std::cout << q << std::endl; // output: 0.125

    return 0;
}
```

Once again, all the calculations mentioned above will be done during the compile-time, which means that in the run-time the program just directly prints the final result.
Now, let's discuss a more complex problem to enhance our understanding of compile-time calculations using templates.

## Using `constexpr` and templates to solve FizzBuzz problem at compile-time

### FizzBuzz Problem

It is an easy problem that is commonly used in some tech interviews. The requirement is: write a program that can accept a positive integer `N` as input, then print out a series of numbers from `1` to `N`. More specifically, if the number is divisible by 3, then print `fizz`; if the number is divisible by 5, then print `buzz`; if the number is divisible by both 3 and 5, then print `fizzbuzz`.

### Solution at run-time

It is trivial to write a solution to solve it at run-time. Below is an example:

```cpp
std::string nFizzBuzz(const unsigned N) {
    if (N % 15 == 0) {
        return "fizzbuzz";
    } else if (N % 3 == 0) {
        return "fizz";
    } else if (N % 5 == 0) {
        return "buzz";
    }
    return std::to_string(N);
}

std::string fizzBuzz(const unsigned N) {
    if (N == 0) {
        return "";
    }

    std::string str = nFizzBuzzT(1);
    for (auto i = 2; i <= N; ++i) {
        str += ", " + nFizzBuzz(i);
    }
    return str;
}
```

When you call `fizzBuzz(16)`, it will print out:

```
1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz, 16
```

### Solution at compile-time

#### Implement auxiliary functions for compile-time use

In above solution, we use `std::string` and `std::to_string` which involves dynamic memory allocations under the hood. However, in C++17, heap allocations are not allowed in `constexpr` functions (Sidenote: in C++20, dynamic memory allocations are allowed, that means we can use `std::vector` and `std::string` in `constexpr` context). To solve this issue in C++17, we can manually implement the same functionality using `char` array.

First thing first, we can use a `std::array<char, Size>` to represent a string.

```cpp
template <std::size_t Size>
using chars = std::array<char, Size>;
```

As we can see, in the naive solution, we use `+=` for string cancatenation. So we also need to implement a `concat` for our `chars`. Since the underlying storage of `chars` is a fixed length array, we need to handle the array copy during the concatenation.

```cpp
constexpr auto copy(const char* start, const char* end, char* dst) {
    while (start < end) {
        *dst++ = *start++;
    }
}

template <std::size_t N1, std::size_t N2>
constexpr auto concat(const chars<N1>& arr1, const chars<N2>& arr2) {
    chars<N1 + N2> res{};
    copy(arr1.begin(), arr1.end(), res.begin());
    copy(arr2.begin(), arr2.end(), res.begin() + N1);
    return res;
}
```

Then, we need to handle the `std::to_string` which can convert an integer into a string.

```cpp
template <unsigned N>
constexpr auto to_chars() {
    constexpr char last_digit = '0' + N % 10;
    if constexpr (N >= 10) {
        return concat(to_chars<N / 10>(), chars<1>{last_digit});
    } else {
        return chars<1>{last_digit};
    }
}
```

#### Tackle the FizzBuzz problem at compile-time

Now with all the tools we have on hand, it is straightforward to translate the naive solution into a compile-time one:

```cpp
template <unsigned N>
constexpr auto nFizzBuzz() {
    constexpr chars<4> FIZZ{'f', 'i', 'z', 'z'};
    constexpr chars<4> BUZZ{'b', 'u', 'z', 'z'};
    if constexpr (N % 15 == 0) {
        return concat(FIZZ, BUZZ);
    } else if constexpr (N % 3 == 0) {
        return FIZZ;
    } else if constexpr (N % 5 == 0) {
        return BUZZ;
    } else {
        return to_chars<N>();
    }
}

template <unsigned N>
constexpr auto fizzBuzz() {
    static_assert(N > 0);
    constexpr chars<2> SEPERATOR{',', ' '};
    if constexpr (N > 1) {
        return concat(fizzBuzz<N - 1>(), concat(SEPERATOR, nFizzBuzz<N>()));
    } else {
        return nFizzBuzz<N>();
    }
}
```

## Conclusion

C++ templates can be used to perform compile-time calculations, which can be very useful in situations where you need to perform calculations that can be determined at compile-time. By defining a template class or function that takes one or more arguments and performs the calculation, you can compute the result at compile-time and use it as a template parameter in other parts of the program. With the help of `constexpr` keyword and `if constexpr` support, it is easier for us to write more intuitive and concise code in template metaprogramming. This can lead to more efficient and optimized code, as well as enabling new programming techniques that may not be possible with run-time calculations.