Fibonacci

FibCpp.cpp

#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);
}

Program.cs

using System;
using System.Numerics;

namespace Fib
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");

            uint n;
            do
            {
                Console.Write("\nn = ");
            }
            while (!uint.TryParse(Console.ReadLine(), out n));

            Console.WriteLine($"Fib({n}) = {fib(n)}");

            Console.ReadLine();
        }

        private static BigInteger fib(uint n)
            => fib2(n).Item1;

        private static (BigInteger, BigInteger) fib2(uint n)
        {
            if (n == 0)
            {
                return (BigInteger.Zero, BigInteger.One);
            }

            var (m, m1) = fib2(n >> 1);
            return (n & 1) == 0
                ? (((m1 << 1) + m) * m, m * m + m1 * m1)
                : ((m * (m + m1) << 1) + m1 * m1, ((m1 << 1) + m) * m);
        }
    }
}