root/core/fibonacci.hpp

/* [<][>][^][v][top][bottom][index][help] */

INCLUDED FROM


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

/* [<][>][^][v][top][bottom][index][help] */