How to generate a look-up table in compile time in C++?

Question

I have been attempting to implement a compiler generated look-up table containing the values of the sine function. The C++ code looks like this

#include <cstdlib>
#include <cmath>
#include <array>
#include <iostream>

using namespace std;

template<typename T>
constexpr T look_up_table_elem(int i)
{
    return {};
}

template<>
constexpr float look_up_table_elem(int i)
{
    return sin(static_cast<float>(i)*2*3.14/64);
}

template<typename T, int... N>
struct lookup_table_expand{};

template<typename T, int... N>
struct lookup_table_expand<T, 1, N...>
{
    static constexpr std::array<T, sizeof...(N) + 1> values =
    {{look_up_table_elem<T>(0), N...}};
};

template<typename T, int L, int... N> struct lookup_table_expand<T, L, N...>
: lookup_table_expand<T, L-1, look_up_table_elem<T>(L-1), N...> {};

template<typename T, int... N>
constexpr std::array<T, sizeof...(N) + 1> lookup_table_expand<T, 1, N...>::values;

const std::array<float, 65> lookup_table = lookup_table_expand<float, 65>::values;

int main(int argc, char** argv) {
    
    for(const float &item : lookup_table){
        std::cout << "Sin: " << item << std::endl;
    }
    
    return 0;
}

I have been struggling with the compilation process.

main.cpp: In instantiation of 'struct lookup_table_expand<float, 65>':
main.cpp:49:74:   required from here
main.cpp:44:52: error: conversion from 'float' to 'int' in a converted constant expression
   44 | : lookup_table_expand<T, L-1, look_up_table_elem<T>(L-1), N...> {};
      |                               ~~~~~~~~~~~~~~~~~~~~~^~~~~
main.cpp:44:52: error: could not convert 'look_up_table_elem<float>((65 - 1))' from 'float' to 'int'
main.cpp:49:76: error: 'values' is not a member of 'lookup_table_expand<float, 65>'
   49 | const std::array<float, 65> lookup_table = lookup_table_expand<float, 65>::values;
      |                                                                            ^~~~~~

Can anybody tell me what I am doing wrong?

In C++20, you can use `consteval` to force a function evaluation at compile time. This would make your code much simpler, provided that you can find a `constexpr` implementation of a sine function. — mcilloni, Jul 19 '21 at 08:44
[`std::sin`](https://en.cppreference.com/w/cpp/numeric/math/sin) is not `constexpr` — Jarod42, Jul 19 '21 at 10:12

Markus Mayr · Answer 1 · 2021-07-20T05:02:35.560

I do not really understand what you are trying to do here, but the error message indicates that look_up_table_elem returns a float and that you are feeding it into an int ... parameter pack at the following lines:

template<typename T, int L, int... N> struct lookup_table_expand<T, L, N...>
: lookup_table_expand<T, L-1, look_up_table_elem<T>(L-1), N...> {};

By the way, this is how I would implement a function like this:

constexpr float lookup_table_elem(std::size_t i, std::size_t n)
{
    return static_cast<float>(i) / static_cast<float>(n); // Have a constexpr sin function here!
}

template <class T>
struct lookup_table_impl;

template <std::size_t... I>
struct lookup_table_impl<std::index_sequence<I...>>
{
    static constexpr std::size_t N = sizeof...(I);
    static constexpr std::array<float, N> values{ lookup_table_elem(I, N) ... };
};

template <std::size_t N>
using lookup_table = lookup_table_impl<std::make_index_sequence<N>>;

template <std::size_t N>
constexpr auto lookup_table_values = lookup_table<N>::values;

Please note that std::sin is not a constexpr function (yet?). You would have to write your own compile-time approximation here.

And as @HolyBlackCat suggested in a comment below, the following, very simple solution is also possible with modern C++ (>= 17, I think):

template <std::size_t N>
constexpr std::array<float, N> make_lookup_table()
{
    std::array<float, N> v;
    for (std::size_t i = 0u; i < N; ++i)
    {
        v[i] = static_cast<float>(i); // Insert constexpr sin function here!
    }
    return v;
}

template <std::size_t N>
constexpr auto lookup_table_values = make_lookup_table<N>();

`int n` is unused and can be removed, as extra `, int N` (which is `sizeof...(I)`) — Jarod42, Jul 19 '21 at 10:17
@Jarod42: A more meaningful implementation of `lookup_table_elem` would use the `n` parameter. Regarding the `N` parameter of `lookup_table_impl` you are right, it can be removed. — Markus Mayr, Jul 20 '21 at 04:59

Quxflux · Answer 2 · 2021-07-19T18:40:55.663

3

The code may be greatly simplified to generate the LUT:

template <std::size_t N, typename F = std::identity>
constexpr auto gen_float_array(const F& f = F{}) 
{
   std::array<float, N> arr;
   for (std::size_t i = 0; i < N; ++i)
      arr[i] = f(static_cast<float>(i));

   return arr;
}

It may be used as follows:

constexpr auto lookup_map =
      gen_float_array<32>([](auto f) { 
        return f * 3.14f; // here could a call be placed to a constexpr sin function
      });

Example: https://godbolt.org/z/ssEhK6bd7

As Markus Mayr pointed out, you are still in need of a constexpr sin function to get the desired results for your use case.

edited Jul 19 '21 at 18:40

answered Jul 19 '21 at 08:05

Quxflux

3,133
2
26
46

1

You are right, the "trickery" is over complicating things. I've removed it from the answer – Quxflux Jul 19 '21 at 08:40
Looks better now! It works in C++20, and can be ported to C++17 by using `std::array arr{};` and a manual call instead of `invoke`. – HolyBlackCat Jul 19 '21 at 08:43
Does `std::forward(f)` do anything useful here? It can't (and must not) trigger move semantics here? – Markus Mayr Jul 19 '21 at 08:53
@MarkusMayr right, without a forwarding reference for F `std::forward` makes no sense. Adapted the example. Thanks – Quxflux Jul 19 '21 at 18:42

How to generate a look-up table in compile time in C++?

2 Answers2