Step 9 of 9

Challenge: compile-time computation

constexpr functions can run during compilation when their inputs are constants. The result is baked into the program as a literal, and static_assert can check it before the program even exists. Lookup tables, hashes of fixed strings, unit conversions and configuration checks are often done this way in performance-critical code: the work costs nothing at run time.

Since C++20, constexpr functions may use loops, local variables, std::array and even std::vector (as long as it doesn't escape the function).

#include <array>
#include <cstddef>
#include <iostream>

template <std::size_t N>
constexpr std::array<long, N> squares() {
    std::array<long, N> out{};
    for (std::size_t i = 0; i < N; i++) out[i] = (long)(i * i);
    return out;
}

constexpr int digit_sum(unsigned n) {
    int s = 0;
    while (n > 0) { s += n % 10; n /= 10; }
    return s;
}

constexpr auto table = squares<6>();          // built by the compiler
static_assert(table[5] == 25);
static_assert(digit_sum(2024) == 8);

int main() {
    for (long x : table) std::cout << x << " ";
    std::cout << "\n" << digit_sum(999) << "\n";
}

0 1 4 9 16 25 
27

How it works

constexpr auto table = squares<6>(); forces compile-time evaluation, because a constexpr variable must be initialized with a constant.
The template parameter N sizes the returned std::array, so each N gives a different function.
Inside a constexpr function, every variable must be initialized (out{}, s = 0), and you can't call non-constexpr functions such as I/O.

Your task

First N primes: fill the array in order. Test each candidate from 2 upward by trying divisors d while d * d <= candidate; if none divides it, it's prime. Stop when N are found.
FNV-1a hash: a simple, well-known hash. Start with h = 2166136261u, and for each character, h ^= (unsigned char)c; then h *= 16777619u;. Using std::uint32_t makes the multiplication wrap around at 32 bits, which is exactly what the algorithm expects. Cast the char to unsigned char first so bytes above 127 aren't sign-extended.

Your task

constexpr std::array<int, N> first_primes<N>(): the first N primes
constexpr std::uint32_t hash32(std::string_view s): 32-bit FNV-1a (start 2166136261u, for each byte h ^= byte; h *= 16777619u;)

Both must work at compile time: the tests use them inside static_assert.

Challenge 2

Write template <std::size_t N> constexpr std::array<long long, N> fib_table() holding the first N Fibonacci numbers 0, 1, 1, 2, .... The tests use it in static_assert, so it must run at compile time.

Challenge 3

Write template <std::size_t N> constexpr std::array<char, N> caesar(const char (&s)[N], int shift) that shifts every lowercase letter forward by shift places (wrapping from z to a) and copies everything else, including the final '\0'. It must work at compile time.

Previous: CRTP and static polymorphism