-
-
Save toch/7ed3a1786d0ed464fd94 to your computer and use it in GitHub Desktop.
template<int n> | |
struct fibonacci | |
{ | |
static constexpr int value = fibonacci<n-1>::value + fibonacci<n-2>::value; | |
}; | |
template<> | |
struct fibonacci<0> | |
{ | |
static constexpr int value = 0; | |
}; | |
template<> | |
struct fibonacci<1> | |
{ | |
static constexpr int value = 1; | |
}; | |
int main() | |
{ | |
fibonacci<40>::value; | |
return 0; | |
} |
I'd like to know the complexity of this algorithm and if it's more efficient than the usual recursive algorithm which is: `int fib(int n) { if (n <= 1) return n; return fib(n-1) + fib(n-2); }
int main () { int n = 9; cout << fib(n); getchar(); return 0; }`
The template implementation is constant-time at runtime; it's evaluated at compile time. But it only works for expressions that can be evaluated at compile time - it wouldn't work for your main (because "n" isn't constant), and it wouldn't work if "n" were read from stdin; for that you'd need the usual function implementation.
Compile time implementation for the iterative approach. Which one would you use and why?
#include <iostream>
template <unsigned N>
struct Fibonacci
{
enum
{
prev = Fibonacci<N-1>::curr,
curr = Fibonacci<N-1>::curr + Fibonacci<N-1>::prev
};
};
template <>
struct Fibonacci<1> {
enum {
prev = 0,
curr = 1
};
};
template <>
struct Fibonacci<0> {
enum {
curr = 0, prev = 0
};
};
int main() { std::cout << Fibonacci<10>::curr << std::endl; }
Does this have an equivalent in Go after the introduction of generics?
Using
template <unsigned long long n>
struct fib {
enum : unsigned long long { result = fib<n - 1>::result + fib<n - 2>::result };
};
template<> struct fib<0> { enum { result = 0 }; };
template<> struct fib<1> { enum { result = 1 }; };
OR
template <unsigned long long n>
struct fib {
static constexpr unsigned long long result = fib<n - 1>::result + fib<n - 2>::result;
};
template<> struct fib<0> { static constexpr int result = 0; };
template<> struct fib<1> { static constexpr int result = 1; };
you an compute up-to fib<105>::result
which is 17704020980446223138
.
I'd like to know the complexity of this algorithm and if it's more efficient than the usual recursive algorithm which is:
`int fib(int n)
{
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
int main ()
{
int n = 9;
cout << fib(n);
getchar();
return 0;
}`