How to get factorial ....factorial at runtime?

Question

I want to fill a look up table with integers computed at compile time:

#include <iostream>
#include <type_traits>

template <int x> using number = std::integral_constant<int,x>;    
template <int n> struct factorial : number<n * factorial<n-1>::value> {};
template <> struct factorial<0> : number<1> {};

int get_factorial(int x) {
    if (x < 1) return -1;
    if (x > 5) return -1;
    static constexpr int lookup_table[] = { 
        factorial<1>::value,
        factorial<2>::value,
        factorial<3>::value,
        factorial<4>::value,
        factorial<5>::value
    };
    return lookup_table[x-1];
}

int main() {        
    int x;
    std::cin >> x;
    std::cout << get_factorial(x) << "\n";
}

This is fine for small number of elements, but what can I do when the look up table contains a large number of elements? How to populate the array without writing each element explicitly?

The factorial is only for the example. In a more realistic scenario I would like to store ~1000 elements in the lookup table.

How large a factorial<> can be? 20! = 2.432902e+18, do you plan to get *that* high? — Michael Chourdakis, Apr 05 '19 at 21:51
@MichaelChourdakis i knew the example has a weak point ;), take it with a grain of salt. I want to store roughly ~1000 elements — 463035818_is_not_an_ai, Apr 05 '19 at 21:56
Research factorials and max uint64_t. You will have to limit size or use multi-precision math ... such as gmpxx.h — 2785528, Apr 06 '19 at 00:50
@2785528 the factorial was just to have an example the question was about how to fill the array. Here is the actual problem https://stackoverflow.com/a/55544791/4117728 — 463035818_is_not_an_ai, Apr 06 '19 at 10:28

sebrockm · Accepted Answer · 2019-04-05T22:15:23.527

With C++14 you can use std::integer_sequence:

template <int... S>
constexpr std::array<int, sizeof...(S)> get_lookup_table_impl(std::integer_sequence<int, S...>)
{
    return { factorial<S>::value... };
}

template <int S>
constexpr auto get_lookup_table()
{
    return get_lookup_table_impl(std::make_integer_sequence<int, S>{});
}

See a fully working example here.

The trick is that std::make_integer_sequence<int, S>{} will create an instance of std::integer_sequence<int, S...>. So, the helper function get_lookup_table_impl is able to deduce its parameter pack. Then, factorial<S>::value... unpacks it and passes each value of S to factorial. Covered with curly braces, this can be used to initialize any kind of std container. I used std::array, but you can use whatever you want.

score 1 · Answer 2 · answered Apr 05 '19 at 22:06

A paramater pack expansion for array initialization can be used here:

#include <iostream>
#include <type_traits>
#include <utility>
template <int x> using number = std::integral_constant<int,x>;    
template <int n> struct factorial : number<n * factorial<n-1>::value> {};
template <> struct factorial<0> : number<1> {};

template<std::size_t... Is>
int get_factorial_impl(int x,std::index_sequence<Is...>)
{
    if (x < 1) return -1;
    if (x > 5) return -1;
    static constexpr int lookup_table[] = { factorial<Is+1>::value...};
    return lookup_table[x-1];
}

int get_factorial(int x)
{
    return get_factorial_impl(x,std::make_index_sequence<5>{});
}

int main() {        
    int x;
    std::cin >> x;
    std::cout << get_factorial(x) << "\n";
}

How to get factorial ....factorial at runtime?

2 Answers2

Linked

How to get factorial....factorial at runtime?

2 Answers2

Linked

How to get factorial ....factorial at runtime?