Constexpr FizzBuzz – An Exercise in Compile-Time Calculations

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;
}

Run it in CompilerExplorer!

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>(); 
  }
}

Run it in CompilerExplorer!

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.