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

Here's a C++11 solution using C++14 library features [1] (GCC >= 4.9.0, Clang >= 3.5.0) using a template argument for the length. You write a loop using recursion. Using a disassembler, you can see the sequence is embedded into the program as raw data, even with no optimizations (-O0).

[1] std::index_sequence can be implemented yourself in C++11 if it is not available in your standard library.

#include <array>
#include <cstddef>
#include <iostream>
#include <type_traits>
#include <utility>

namespace {
// Create an std::array from a C array (internal) via an
// std::index_sequence.
template <typename T, typename TSequence> struct MakeArrayImpl;
template <typename T, std::size_t... TIndices>
struct MakeArrayImpl<T, std::index_sequence<TIndices...>> {
  static constexpr std::array<T, sizeof...(TIndices)>
  make_array(T values[sizeof...(TIndices)]) {
    return std::array<T, sizeof...(TIndices)>{{values[TIndices]...}};
  }
};

// Create an std::array from a C array.
template <typename T, std::size_t TLength>
constexpr std::array<T, TLength> make_array(T values[TLength]) {
  return MakeArrayImpl<T, std::make_index_sequence<TLength>>::make_array(
      values);
}

// Return an std::array of the first numbers in the Fibonacci sequence.
template <std::size_t TLength>
constexpr std::array<long long int, TLength> fibs() {
  // Original algorithm.
  long long int fib[TLength] = {0};
  fib[0] = 1;
  fib[1] = 1;
  for (std::size_t i = 2; i < TLength; ++i) {
    fib[i] = fib[i - 2] + fib[i - 1];
  }
  return make_array<long long int, TLength>(fib);
}
}

int main() {
  // Original algorithm.
  const int N = 92;
  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];

  // Test constexpr algorithm against original algorithm.
  static constexpr auto values = fibs<N>();
  static_assert(values.size() == N, "Expected N values in Fibs");
  for (int i = 0; i < N; ++i) {
    if (fib[i] != values[i]) {
      std::cerr << "Mismatch at index " << i << "\n";
      std::cerr << "Expected: " << fib[i] << "\n";
      std::cerr << "Actual  : " << values[i] << "\n";
    }
  }
}

Answer 2

Here's a C++14 solution (GCC >= 5.0.0, Clang >= 3.5.0) using a template argument for the length. You write an imperative loop (identical to your original post) in a constexpr function. Using a disassembler, you can see the sequence is embedded into the program as raw data, even with no optimizations (-O0).

#include <array>
#include <cstddef>
#include <iostream>
#include <type_traits>
#include <utility>

namespace {
// Create an std::array from a C array (internal) via an
// std::index_sequence.
template <typename T, typename TSequence> struct MakeArrayImpl;
template <typename T, std::size_t... TIndices>
struct MakeArrayImpl<T, std::index_sequence<TIndices...>> {
  static constexpr std::array<T, sizeof...(TIndices)>
  make_array(T values[sizeof...(TIndices)]) {
    return std::array<T, sizeof...(TIndices)>{{values[TIndices]...}};
  }
};

// Create an std::array from a C array.
template <typename T, std::size_t TLength>
constexpr std::array<T, TLength> make_array(T values[TLength]) {
  return MakeArrayImpl<T, std::make_index_sequence<TLength>>::make_array(
      values);
}

// Return an std::array of the first numbers in the Fibonacci sequence.
template <std::size_t TLength>
constexpr std::array<long long int, TLength> fibs() {
  // Original algorithm.
  long long int fib[TLength] = {0};
  fib[0] = 1;
  fib[1] = 1;
  for (std::size_t i = 2; i < TLength; ++i) {
    fib[i] = fib[i - 2] + fib[i - 1];
  }
  return make_array<long long int, TLength>(fib);
}
}

int main() {
  // Original algorithm.
  const int N = 92;
  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];

  // Test constexpr algorithm against original algorithm.
  static constexpr auto values = fibs<N>();
  static_assert(values.size() == N, "Expected N values in Fibs");
  for (int i = 0; i < N; ++i) {
    if (fib[i] != values[i]) {
      std::cerr << "Mismatch at index " << i << "\n";
      std::cerr << "Expected: " << fib[i] << "\n";
      std::cerr << "Actual  : " << values[i] << "\n";
    }
  }
}

Answer 3

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.

Answer 4

There is a way (ugly one), but I can't think of anything else.

#include <iostream>
#include <cmath>

constexpr unsigned long long f(int x)
{
    return 1/sqrt(5)*pow(((1+sqrt(5))/2),x) - 1/sqrt(5)*pow(((1-sqrt(5))/2),x);
}

#define FIBB1(x)  1
#define FIBB2(x)  FIBB1(x-1),1
#define FIBB3(x)  FIBB2(x-1),f(x)
#define FIBB4(x)  FIBB3(x-1),f(x)
#define FIBB5(x)  FIBB4(x-1),f(x)
#define FIBB6(x)  FIBB5(x-1),f(x)
#define FIBB7(x)  FIBB6(x-1),f(x)
#define FIBB8(x)  FIBB7(x-1),f(x)
#define FIBB9(x)  FIBB8(x-1),f(x)
#define FIBB10(x) FIBB9(x-1),f(x)
#define FIBB11(x) FIBB10(x-1),f(x)
#define FIBB12(x) FIBB11(x-1),f(x)
#define FIBB13(x) FIBB12(x-1),f(x)
#define FIBB14(x) FIBB13(x-1),f(x)
#define FIBB15(x) FIBB14(x-1),f(x)
#define FIBB16(x) FIBB15(x-1),f(x)
#define FIBB17(x) FIBB16(x-1),f(x)
#define FIBB18(x) FIBB17(x-1),f(x)
#define FIBB19(x) FIBB18(x-1),f(x)
#define FIBB20(x) FIBB19(x-1),f(x)
// ...
#define FIBB93(x) FIBB92(x-1),f(x)
//#define FIBB94(x) FIBB93(x-1),f(x) //unsigned long long overflow, can't calculate more

#define FIBB(x) {FIBB##x(x)}

constexpr unsigned long long fib[93] = FIBB(93);

int main()
{
    // all possible fibbonacci numbers for unsigned long long implementation
    for(int i=0; i<93; ++i)
        std::cout << fib[i] << std::endl;
}

I think it's the only way for C++ built-in array.

Answer 5

1. In the code sample you posted, there is a decent chance that the compiler may unroll the loop, or at least part of it, on its own, if -O3 optimizations are used. Playing around on godbolt, it appears that this doesn't happen at N=100 but does at N up to about 40. In this case it does happen at compile time, whether or not it is constexpr.

2. Which also points out -- on many machines, long long int is not large enough to hold the 100'th fibonacci number. Fibonacci numbers grow exponentially, you should expect the 100th number to require about 100 bits or so. Your code as written will exhibit undefined behavior due to integer overflow, on a typical machine.

Using a template you can do it like this:

// Fibonacci recurrence
template <long int n> 
struct fib_pair {
  typedef fib_pair<n-1> prev;
  static constexpr long int fib_n = prev::fib_n_plus_one;
  static constexpr long int fib_n_plus_one = prev::fib_n + prev::fib_n_plus_one;
};

template <>
struct fib_pair<0> {
  static constexpr long int fib_n = 0;
  static constexpr long int fib_n_plus_one = 1;
};

// List structure
template <long int ... > struct list {};

// Concat metafunction
template <typename A, typename B> struct concat;
template <long int... As, long int... Bs> struct concat<list<As...>, list<Bs...>> {
  typedef list<As..., Bs...> type;
};

// Get a sequence from the fib_pairs
template <long int n>
struct fib_seq {
  typedef typename fib_seq<n-1>::type prev;

  typedef typename concat<prev, list<fib_pair<n>::fib_n>>::type type;
};

template <>
struct fib_seq<0> {
  typedef list<0> type;
};


// Make an array from pack expansion
#include <array>
template <typename T> struct helper;

template <long int ... nums>
struct helper <list<nums...>> {
  typedef std::array<const long int, sizeof...(nums)> array_type;
  static constexpr array_type get_array() {
    return {{ nums... }};
  }
};

// Easy access
template <long int n>
constexpr std::array<const long int, n + 1> get_fib_array() {
  return helper<typename fib_seq<n>::type>::get_array();
}

#include <iostream>

int main () {
  for (const long int x : get_fib_array<15>()) {
    std::cout << x << std::endl;
  }
}