//-----------------------------------------------------------------------------

#include <cassert>
#include <functional>
#include <mutex>
#include <random>
#include <vector>

//-----------------------------------------------------------------------------

using type = long long unsigned;
const type MAX = 93;                        // fib(MAX + 1) doesn't fit in type
const type VALUE = 12200160415121876738ull; // fib(MAX) == VALUE

//-----------------------------------------------------------------------------

template<typename T> T fib1(T n)
{
    if (n < 2)
        return n;
    else
        return fib1(n - 2) + fib1(n - 1);
}

//-----------------------------------------------------------------------------

template<typename T> T fib2(T n)
{
    T i = 1, j = 0;
    for (T k = 0; k < n; ++k)
    {
        T t = i + j;
        i = j;
        j = t;
    }
    return j;
}

//-----------------------------------------------------------------------------

template<class T> T fib3(T n)
{
    if (n < 2)
        return n;

    T t1 = 0, t2 = 1, a = t2, b = t1, c = t1, d = t2;
    for (T i = n - 1; i > 0; i >>= 1)
    {
        if ((i & 1) != 0)
        {
            t1 = a * c + b * d;
            t2 = (a + b) * d + b * c;
            a = t1;
            b = t2;
        }
        t1 = c * c + d * d;
        t2 = (2 * c + d) * d;
        c = t1;
        d = t2;
    }
    return a + b;
}

//-----------------------------------------------------------------------------

template<class T> T fib4(T n)
{
    static std::vector<T> solutions = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34};

    try
    {
        return solutions.at(n);
    }
    catch (...)
    {
        std::size_t size = solutions.size();
        solutions.resize(n + 1);
        for (auto i = solutions.begin() + size; i != solutions.end(); ++i)
            *i = *(i - 2) + *(i - 1);
    }

    return solutions[n];
}

//-----------------------------------------------------------------------------

template<class T> T fib5(T n)
{
    static std::vector<T> solutions = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34};
    std::size_t size = solutions.size();

    if (n >= size)
    {
        solutions.resize(n + 1);
        for (auto i = solutions.begin() + size; i != solutions.end(); ++i)
            *i = *(i - 2) + *(i - 1);
    }

    return solutions[n];
}

//-----------------------------------------------------------------------------

template<class T> T fib6(T n)
{
    static std::once_flag flag;
    std::call_once(flag, [&] { fib5(MAX); });

    return fib5(n);
}

//-----------------------------------------------------------------------------

type r = 0;

template<typename F> void test(F &f)
{
    assert(f(MAX) == VALUE);

    std::random_device device;
    std::default_random_engine engine(device());
    std::uniform_int_distribution<type> distribution(MAX / 2, MAX + 1);
    auto rng = std::bind(distribution, engine);

    for (std::size_t i = 0; i < 999999; ++i)
        r += f(rng());
}

//-----------------------------------------------------------------------------

int main()
{
    // test(fib1<type>);
    test(fib2<type>);
    test(fib3<type>);
    test(fib4<type>);
    test(fib5<type>);
    test(fib6<type>);
    return r;
}

//-----------------------------------------------------------------------------