Is it possible to evaluate array on compilation time?

Question

I need to store the array of first N Fibonacci numbers.

const int N = 100;
long long int fib[N] = {0};
fib[0] = 1;
fib[1] = 1;
for(int i = 2; i < N; ++i)
    fib[i] = fib[i-2] + fib[i-1];
return 0;

Is it possible to make fib[] constexpr, and evaluate it at compilation time somehow ?

Answer 1

First of all you have to write Fibonacci algorithm in compile time version, so consider following:

template <size_t N>
struct Fibo {
    static constexpr const size_t value {Fibo<N-2>::value + Fibo<N-1>::value};
};

template <>
struct Fibo<0> {
    static constexpr const size_t value {1};
};

template <>
struct Fibo<1> {
    static constexpr const size_t value {1};
};

and you can use this as simply as that:

std::cout << Fibo<0>::value << std::endl;
std::cout << Fibo<1>::value << std::endl;
std::cout << Fibo<2>::value << std::endl;
std::cout << Fibo<3>::value << std::endl;
std::cout << Fibo<10>::value << std::endl;
std::cout << Fibo<50>::value << std::endl;

and output values are:

1
1
2
3
89
20365011074

But this is still not you are looking for.

I do not know if you can make constexpr array (but probably there is a possibility), but you can do it slightly different. Consider:

template <size_t N>
struct Storage {
    static size_t data[N+1];
};

template <size_t N> size_t Storage<N>::data[N+1] {};

template <size_t N, size_t F>
struct Filler {
    static constexpr void fill () {
        Storage<N>::data[F] = Fibo<F>::value;
        Filler<N, F-1>::fill ();
    }
};

template <size_t N>
struct Filler<N, 0> {
    static constexpr void fill () { 
        Storage<N>::data[0] = Fibo<0>::value;
    }
};

template <size_t N>
struct Calc {
    static constexpr void calc () {        
        Filler<N, N>::fill ();
    }
};

and the usage would be like this:

constexpr const size_t N = 12;

Calc<N>::calc ();
size_t* ptr = Storage<N>::data;

for (int i = 0; i <= N; ++i) {
    std::cout << ptr[i] << std::endl;
}

and output:

1
1
2
3
5
8
13
21
34
55
89
144
233

What is important here is the Storage class which stores our array with appropriate number of elements.

General Filler class (with two template parameters) is used for any F value that can be passed, except value of 0. Because if we reach the 0 index, we don't want to call once again fill() member function, because we are done. So that's the reason why partial specialization of Filler class exists.

Hope I can help with this.