-
-
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; | |
} |
1000th member is supposed to have more than 176 digits(which is beyond the capacity of unsigned long int), I think unsigned long int just doesn't show the overflow error
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;
}`
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
.
Better implementation in order to avoid integer overflow:
Then you can go up to the 1000th member of the suite like this:
fibonacci<1000, unsigned long int>::value