Skip to content

Instantly share code, notes, and snippets.

@chiroptical
Last active December 20, 2017 20:10
Show Gist options
  • Save chiroptical/c55b2b6cc38f191600df96a3140de9df to your computer and use it in GitHub Desktop.
Save chiroptical/c55b2b6cc38f191600df96a3140de9df to your computer and use it in GitHub Desktop.
Recursive fibonacci at compile time (protected from negative numbers blowing up compiler)
namespace impl {
template <int n, bool isPositive>
struct fib_impl {
static constexpr int val = fib_impl<n - 1, isPositive>::val + fib_impl<n - 2, isPositive>::val;
};
template <>
struct fib_impl<1, true> {
static constexpr int val = 1;
};
template <>
struct fib_impl<0, true> {
static constexpr int val = 0;
};
// If calling fib<-1>::val it will try to do the recursion up to -ftemplate-depth=N
// -> On GCC 7.2.1, N=900
// -> Template specialization for that case
template <int n>
struct fib_impl<n, false> {
static constexpr int val = -1;
};
}
template <int n>
struct fib {
static_assert(n >= 0, "Error: fib can't be called with a negative integer");
static constexpr int val = impl::fib_impl<n, (n >= 0)>::val;
};
int main() {
static_assert(fib<0>::val == 0);
static_assert(fib<1>::val == 1);
static_assert(fib<10>::val == 55);
// static_assert(fib<-1>::val); // This will fail.
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment