import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
import java.math.RoundingMode;
/*
============================================================================
Author : Catarina Moreira
Copyright : Catarina Moreira all rights reserved
Description : Implementation of the fibonacci sequence using Binet\'s formula
============================================================================
*/
public class Binet
{
public BigInteger runFibonacci(int n)
{
if( n == 0)
return BigInteger.ZERO;
if( n == 1)
return BigInteger.ONE;
double sqrt_5 = Math.sqrt(5);
BigDecimal big_sqrt_5 = new BigDecimal( Double.toString( sqrt_5 ) );
BigDecimal part1 = big_sqrt_5.add(BigDecimal.ONE);
BigDecimal part2 = BigDecimal.ONE.subtract(big_sqrt_5);
BigDecimal power2 = new BigDecimal("2");
power2 = power2.pow(n);
BigDecimal result = (( part1.pow(n) ).subtract( part2.pow(n) )).divide( power2.multiply(big_sqrt_5) );
return result.setScale(0, RoundingMode.FLOOR).toBigInteger();
}
}