Contents

Recently, I have given a workshop about language features introduced in C++14 and C++17. Since a major part of those features includes `constexpr`

things, I gave my trainees the task to port “FizzBuzz” to compile time. Here is a possible approach to that kind of problem.

## FizzBuzz at run time

Implementing FizzBuzz is a popular interview question: For the numbers of 1 through N, write “fizz” for every number that is divisible by 3, “buzz” for every number that is divisible by 5, “fizzbuzz” if it’s divisible by 15. Write the number itself otherwise.

For the sake of brevity, I will omit all discussions whether a question like this makes sense and give you a run time implementation right away:

```
std::string nthFizzBuzz(unsigned N) {
std::string str;
if (N%3 == 0) {
str += "fizz";
}
if (N%5 == 0) {
str += "buzz";
}
if (str.empty()) {
str = std::to_string(N);
}
return str;
}
std::string fizzBuzzUntil(unsigned N) {
assert(N>0);
std::string str = nthFizzBuzz(1);
for (unsigned n = 2; n <= N; ++n) {
str += ", " + nthFizzBuzz(n);
}
return str;
}
```

Now, calling, for example, `fizzBuzzUntil(7)`

will give us a string

```
1, 2, fizz, 4, buzz, fizz, 7
```

This is a straightforward implementation, the kind you’d write down as a first draft. We won’t modify it, e.g. to reduce the number of allocations that have to be done for all those string concatenations. Instead, we’ll take it as the reference algorithm for the constexpr implementation.

## Going constexpr

### The tools we (don’t) have

With C++14’s extension to what is allowed in constexpr functions and C++17’s `if constexpr`

, the structure of our little program can be mostly the same. However, there are a few things used in the run-time algorithm that are not available at compile time: In C++17, heap allocations are not allowed in constexpr functions. Therefore `std::string`

and, consequently, `std::to_string`

are not available.

The most straightforward way to solve this dilemma is to use `std::array<char, Size>`

. The first challenge will, therefore, be to implement a function `to_array`

that does the compile-time equivalent to `std::to_string`

. Since we’ll be dealing with `std::array<char, Size>`

a lot here, I’ll just add a template alias to that so the code is more readable on mobile devices.

### to_array – dealing with compile-time parameters

```
template <std::size_t Size>
using chars = std::array<char, Size>;
constexpr chars<Size> to_array(unsigned N) {
/* ... */
}
```

It turns out we hit the first hurdle right away: What is the value of `Size`

? It depends on N, and therefore N can not be a normal function parameter. The reasoning for that is relatively simple: constexpr functions may be called at run time, with values that are not known at compile time.

```
unsigned n;
std::cin >> n;
auto number = to_array(n);
```

We can’t possibly know `n`

at compile time here and therefore can not calculate `Size`

. In general, compile-time properties of constexpr functions (like the `Size`

template parameter to its return type) can not depend on normal (run-time) function parameters.

The solution to this problem is to use template parameters which are always known at compile time. While we’re at it, the `Size`

and, therefore, the return type, are derived inside the implementation, so we better let the compiler determine it for us by using C++14’s auto return type deduction. The algorithm itself can be implemented relatively simple:

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

I renamed the function to `to_chars`

to match the type alias we use.

### array concatenation

As you see, we will also need a concatenation function for the char arrays. We’ll need it in other places as well, basically everywhere the run time version has string additions. We won’t be able to have the `+=`

addition we had there, since concatenating arrays will give a longer array and therefore a different type.

The algorithm for concatenation is straightforward: create an array of the right size and copy the elements of the original arrays over. Oh, but `std::copy`

isn’t constexpr yet in C++17. We’ll have to implement our own.

```
constexpr void copy(char const* first, char const* last, char* to) {
while (first < last) {
*to++ = *first++;
}
}
template <std::size_t N1, std::size_t N2>
constexpr auto concat(
chars<N1> const& str1,
chars<N2> const& str2)
{
chars<N1+N2> result{};
copy(str1.begin(), str1.end(), result.begin());
copy(str2.begin(), str2.end(), result.begin()+N1);
return result;
}
```

Note that I did not write `copy`

as a template and `concatenate`

is restricted to char arrays. We don’t need the code to be more general here, so I left it as simple as it can be to avoid unnecessary complexity and mistakes.

## Back to the task: constexpr FizzBuzz

Now we have the tools to actually implement compile-time FizzBuzz. Similarly to `to_chars`

, the two functions `nthFizzBuzz`

and `fizzBuzzUntil`

have to take the input as a template parameter. We also still have the slight annoyance of not having a `+=`

, so the special case of numbers divisible by both 3 and 5 has to be treated explicitly.

```
template <unsigned N>
constexpr auto nthFizzBuzz()
{
constexpr chars<4> FIZZ{'f', 'i', 'z', 'z'};
constexpr chars<4> BUZZ{'b', 'u', 'z', 'z'};
if constexpr (N%3==0 && N%5 ==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 fizzBuzzUntil()
{
constexpr chars<2> SEPARATOR{',', ' '};
static_assert(N > 0);
if constexpr (N != 1) {
return concat(fizzBuzzUntil<N-1>(),
concat(SEPARATOR, nthFizzBuzz<N>())
);
} else {
return nthFizzBuzz<N>();
}
}
```

## Conclusion

Constexpr calculations are not perfectly easy since we do not yet have all the tools we have at run time. But we’re getting there step by step, and when we put in some work, we can do some decent calculations at compile-time, possibly reducing the code size and improving the run-time performance.

In this example, there’s still some work we could put into it, like resolving the recursion in `fizzBuzzUntil`

and allowing for concatenation of multiple char arrays, but I’ll leave that as an exercise to you for now.

Permalink

Nice, pretty similar to my solution that I came up some time ago

https://www.numbercrunch.de/blog/2018/02/fizzbuzz-or-the-beauty-of-compile-time-calculations-in-c17/

Permalink

Good post! I think this presentation is somewhat connected, although it’s about Fibonacci, but uses a lot of advanced techniques.

https://www.youtube.com/watch?v=TyiiNVA1syk