#include <iostream>
#include <tuple>
//#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/gmp.hpp>

namespace mp = boost::multiprecision;

//typedef mp::cpp_int mpint;
typedef mp::mpz_int mpint;

mpint fib(uint32_t n);
std::tuple<mpint, mpint> fib2(uint32_t n);

int main()
{
	std::cout << "Hello World!\n";
	uint32_t n = ~(uint32_t)0;
	std::cout << "msb(fib(" << n << ")) = " << mp::msb(fib(n)) << std::endl;
}

mpint fib(uint32_t n)
{
	if (n == 0)
	{
		return 0;
	}
	auto tmp = fib2(n >> 1);
	auto m = std::get<0>(tmp);
	auto m1 = std::get<1>(tmp);

	if ((n & 1) == 0)
	{
		return ((m1 << 1) + m) * m;
	}
	else
	{
		return (m * (m + m1) << 1) + m1 * m1;
	}
}

std::tuple<mpint, mpint> fib2(uint32_t n)
{
	if (n == 0)
	{
		return std::make_tuple(0, 1);
	}

	auto tmp = fib2(n >> 1);
	auto m = std::get<0>(tmp);
	auto m1 = std::get<1>(tmp);

	return (n & 1) == 0
		? std::make_tuple<mpint, mpint>(((m1 << 1) + m) * m, m * m + m1 * m1)
		: std::make_tuple<mpint, mpint>((m * (m + m1) << 1) + m1 * m1, ((m1 << 1) + m) * m);
}