hikarin522
7/12/2019 - 1:58 AM

## Fibonacci

Fibonacci

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

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

}

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