Boost C++ Libraries

Fibonacci numbers (F_n) follows the linear recurrence F_n=F_n-1+F_n-2 starting with F₀=0, F₁=1.

Synopsis

#include <boost/math/special_functions/fibonacci.hpp>

namespace boost { namespace math {

template <class T, class Policy>
constexpr T fibonacci(unsigned long long n) // Checked version (default policy)

template <class T, class Policy>
constexpr T fibonacci(unsigned long long n, const Policy &pol) // Checked version (policy for errors etc.)

template <typename T>
constexpr T unchecked_fibonacci(unsigned long long n) noexcept(std::is_fundamental<T>::value); {  // Unchecked version (no policy).

}} // namespaces

The functions return F_n for a given input n having type T.

Description

The checked versions checks for the overflow before starting the computation. If n is so large that the result can not be represented in type T, it then calls overflow_error. The overflow check is susceptible to off-by-one errors around the overflow limit. See Binet's Formula below for more details on the check.

These functions are all constexpr from C++14 onwards, and in addition unchecked_fibonacci is noexcept when T is a fundamental type.

The final Policy argument is optional and can be used to control the behaviour of the function: how it handles errors, what level of precision to use etc. Refer to the policy documentation for more details.

If in the checked version, the overflow check succeeds then the unchecked version is called which computes the desired F_n. Checked version is slower because of the overhead involved in overflow check.

Generator

#include <boost/math/special_functions/fibonacci.hpp>

template <typename T>
class fibonacci_generator {
  // returns consecutive fibonacci number starting from 0, 1, 1, 2, ...
  T operator()();
  // reset the generator to start from nth fibonacci number
  void set(unsigned long long n);
}

The generator returns consecutive fibonacci numbers starting with 0, 1, 1, 2...

The state of the generator can be modified using set() which makes generator return consecutive fibonacci numbers starting from n[sup th] fibonacci number.

boost::math::fibonacci_generator<int> gen;
int x = gen(); // x is 0
int y = gen(); // y is 1
for(int i = 0; i < 5; ++i) // this loop is same as gen.set(7);
    gen();
int z = gen(); // z is 13 

Generator is non-throwing for all fundamental types and will not check for overflows.

Type Requirements

The type must be an arithmetic type supporting +, -, * and can be initialized from trivial integral types.

Example

The file reciprocal_fibonacci_constant.cpp uses fibonacci_generator to calculate the reciprocal fibonacci constant to 1000 digit precision like so:

#include <boost/math/special_functions/fibonacci.hpp>
#include <boost/multiprecision/mpfr.hpp>
#include <iomanip>
#include <iostream>

int main() {
    using Real = boost::multiprecision::mpfr_float_1000;
    boost::math::fibonacci_generator<Real> gen;
    gen.set(1); // start producing values from 1st fibonacci number
    Real ans = 0;
    const int ITR = 1000;
    for (int i = 0; i < ITR; ++i) {
        ans += 1.0 / gen();
    }
    std::cout << std::setprecision(1000) << "Reciprocal fibonacci constant after "
              << ITR << " iterations is: " << ans << std::endl;
}

Implementation

The time complexity for computing fibonacci number is O(log n), without considering the time complexities of multiplication and addition (where n is the input parameter). The implementation is iterative version of Dijkstra's identities and which simply walks down the bits of n.

Binet's Formula

There is a closed form expression for computing fibonacci numbers but since it suffers from imprecision issues (using floating point computation), it is not implemented.

However an approximate formula is used for the overflow checking in the checked version.