libjmmcg  release_579_6_g8cffd
A C++ library containing an eclectic mix of useful, advanced components.
fibonacci.hpp
Go to the documentation of this file.
1 #ifndef LIBJMMCG_CORE_FIBONACCI_HPP
2 #define LIBJMMCG_CORE_FIBONACCI_HPP
3 
4 /******************************************************************************
5 ** Copyright © 2013 by J.M.Hearne-McGuiness, coder@hussar.me.uk
6 **
7 ** This library is free software; you can redistribute it and/or
8 ** modify it under the terms of the GNU Lesser General Public
9 ** License as published by the Free Software Foundation; either
10 ** version 2.1 of the License, or (at your option) any later version.
11 **
12 ** This library is distributed in the hope that it will be useful,
13 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
14 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 ** Lesser General Public License for more details.
16 **
17 ** You should have received a copy of the GNU Lesser General Public
18 ** License along with this library; if not, write to the Free Software
19 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 */
21 
22 namespace jmmcg { namespace LIBJMMCG_VER_NAMESPACE {
23 
24 namespace mpl {
25 
26  template<unsigned long long N>
27  struct fibonacci {
28  typedef unsigned long long element_type;
29  static constexpr element_type n=N;
30  static constexpr element_type value=fibonacci<N-1>::value+fibonacci<N-2>::value;
31  };
32  template<>
33  struct fibonacci<1ull> {
34  typedef unsigned long long element_type;
35  static constexpr element_type n=1;
36  static constexpr element_type value=1;
37  };
38  template<>
39  struct fibonacci<0ull> {
40  typedef unsigned long long element_type;
41  static constexpr element_type n=1;
42  static constexpr element_type value=1;
43  };
44 
45  template<unsigned long long N>
46  constexpr typename fibonacci<N>::element_type fibonacci<N>::n;
47  template<unsigned long long N>
48  constexpr typename fibonacci<N>::element_type fibonacci<N>::value;
49  constexpr typename fibonacci<1ull>::element_type fibonacci<1ull>::n;
50  constexpr typename fibonacci<1ull>::element_type fibonacci<1ull>::value;
51  constexpr typename fibonacci<0ull>::element_type fibonacci<0ull>::n;
52  constexpr typename fibonacci<0ull>::element_type fibonacci<0ull>::value;
53 }
54 
55 namespace dyn {
56 
57  struct fibonacci {
58  typedef unsigned long long element_type;
59 
60  /**
61  Complexity: O(N)
62 
63  \param N The number for which the Fibonacci number should be computed.
64  \return Return the Fibonacci number.
65  */
66  static element_type result(element_type N) noexcept(true) {
67  // fib(2)=fib(2-1)+fib(2-2)=fib(1)+fib(0)=1+1
68  // fib(3)=fib(3-1)+fib(3-2)=fib(2)+fib(1)
69  // 1, 1, 2, 3, 5, 8, ...
70  // 1, 1, (1+1), (1+2), (2+3), (3+5), ...
71  element_type fib_im2=0, fib_im1=1, fib_i=fib_im1+fib_im2;
72  for (element_type i=0; i<N; ++i) {
73  fib_i=fib_im1+fib_im2;
74  fib_im2=fib_im1;
75  fib_im1=fib_i;
76  }
77  // i=0: fib_im2=1, fib_im1=1, fib_i=fib_im1+fib_im2=1+1=2
78  // i=1: fib_im2=1, fib_im1=1, fib_i=fib_im1+fib_im2=1+1=2
79  // i=2: fib_i=fib_im1+fib_im2=1+1=2, fib_im2=fib_im1=1, fib_im1=fib_i=2
80  // i=3: fib_i=fib_im1+fib_im2=2+1=3, fib_im2=fib_im1=2, fib_im1=fib_i=3
81  // i=4: fib_i=fib_im1+fib_im2=3+2=5, fib_im2=fib_im1=3, fib_im1=fib_i=5
82  return fib_i;
83  }
84  };
85 
86 }
87 
88 } }
89 
90 #endif