package org.nxt.algorithm.series;
import java.math.BigInteger;
/**
* fibonacci series
* @author nanxiaotao
*
*/
public class FibonacciSeries {
private static BigInteger[][] matrix(BigInteger[][] arrLeft, BigInteger[][] arrRight){
BigInteger result[][] = {{new BigInteger("0"),new BigInteger("0")},{new BigInteger("0"),new BigInteger("0")}};
for (int i = 0; i <= 1; i++){
for (int j = 0; j <= 1; j++){
result[i][j] = arrLeft[i][0].multiply(arrRight[0][j]).add(arrLeft[i][1].multiply(arrRight[1][j]));
}
}
return result;
}
private static BigInteger[][] square(BigInteger [][] arrIn){
BigInteger result[][] = {{new BigInteger("0"),new BigInteger("0")},{new BigInteger("0"),new BigInteger("0")}};
BigInteger [][] arrLeft = arrIn;
BigInteger [][] arrRight = arrIn;
if (arrIn != null){
for (int i = 0; i <= 1; i++){
for (int j = 0; j <= 1; j++){
result[i][j] = arrLeft[i][0].multiply(arrRight[0][j]).add(arrLeft[i][1].multiply(arrRight[1][j]));
}
}
}
return result;
}
private static BigInteger[][] matrixFast(BigInteger[][] arrIn, int n){
BigInteger result[][] = arrIn;
BigInteger tmp[][] = {{new BigInteger("1"),new BigInteger("0")},{new BigInteger("0"),new BigInteger("1")}};//初始值为单位阵
while (n != 0){
if ((n & 1) == 1){
tmp = matrix(tmp.clone(), result);
result = square(result.clone());
n = n >> 1;
}else {
result = square(result.clone());
n = n>>1;
}
}
return tmp;
}
public static BigInteger computeN(int n) {
BigInteger arrIn[][] = {{new BigInteger("1"),new BigInteger("1")},{new BigInteger("1"),new BigInteger("0")}};
BigInteger res[][] = matrixFast(arrIn, n);
return res[0][0];
}
public static void main(String[] args) {
System.out.println(computeN(6));
}
}