The Fibonacci sequence is a sequence Fn of natural numbers defined recursively:
F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2, if n>1
Write a function to generate the nth Fibonacci number. Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion).
The sequence is sometimes extended into negative numbers by using a straightforward inverse of the positive definition:
Fn = Fn+2 - Fn+1, if n<0
Support for negative n in the solution is optional.
Using unsigned int, this version only works up to 48 before fib overflows.
#include <iostream> int main() { unsigned int a = 1, b = 1; unsigned int target = 48; for(unsigned int n = 3; n <= target; ++n) { unsigned int fib = a + b; std::cout << "F("<< n << ") = " << fib << std::endl; a = b; b = fib; } return 0; }
This version does not have an upper bound.
#include <iostream> #include <gmpxx.h> int main() { mpz_class a = mpz_class(1), b = mpz_class(1); mpz_class target = mpz_class(100); for(mpz_class n = mpz_class(3); n <= target; ++n) { mpz_class fib = b + a; if ( fib < b ) { std::cout << "Overflow at " << n << std::endl; break; } std::cout << "F("<< n << ") = " << fib << std::endl; a = b; b = fib; } return 0; }
Version using transform:
#include <algorithm> #include <vector> #include <functional> #include <iostream> unsigned int fibonacci(unsigned int n) { if (n == 0) return 0; std::vector<int> v(n+1); v[1] = 1; transform(v.begin(), v.end()-2, v.begin()+1, v.begin()+2, std::plus<int>()); // "v" now contains the Fibonacci sequence from 0 up return v[n]; }
Far-fetched version using adjacent_difference:
#include <numeric> #include <vector> #include <functional> #include <iostream> unsigned int fibonacci(unsigned int n) { if (n == 0) return 0; std::vector<int> v(n, 1); adjacent_difference(v.begin(), v.end()-1, v.begin()+1, std::plus<int>()); // "array" now contains the Fibonacci sequence from 1 up return v[n-1]; }
Version which computes at compile time with metaprogramming:
#include <iostream> template <int n> struct fibo { enum {value=fibo<n-1>::value+fibo<n-2>::value}; }; template <> struct fibo<0> { enum {value=0}; }; template <> struct fibo<1> { enum {value=1}; }; int main(int argc, char const *argv[]) { std::cout<<fibo<12>::value<<std::endl; std::cout<<fibo<46>::value<<std::endl; return 0; }
The following version is based on fast exponentiation:
#include <iostream> inline void fibmul(int* f, int* g) { int tmp = f[0]*g[0] + f[1]*g[1]; f[1] = f[0]*g[1] + f[1]*(g[0] + g[1]); f[0] = tmp; } int fibonacci(int n) { int f[] = { 1, 0 }; int g[] = { 0, 1 }; while (n > 0) { if (n & 1) // n odd { fibmul(f, g); --n; } else { fibmul(g, g); n >>= 1; } } return f[1]; } int main() { for (int i = 0; i < 20; ++i) std::cout << fibonacci(i) << " "; std::cout << std::endl; }
- Output:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Content is available under GNU Free Documentation License 1.2.
