Fibonacci(N)=Fibonacii(N-1)+Fibonacci（N-2）
其中 Fibonacci(0)=0;Fibonacci(1)=1
用循环或则递归实现Fibonacci算法很简单，这里就不说了，如果要用公式实现的话，需要进行开根号和幂运算，普通的long型号只能精确到小数点之后的16位，这就意味着当N很大的时候由于小数位overflow无法进行精确运算，本人测试当N大于92时候因为数据溢出的原因就与实际结果不一样了，如果小数点后面不是精确16位，而是自己设定的话，那么运算结果会精确到自己的期望值。JAVA为我们提供了BigDecimal这个类，BigDecimal类提供了幂运算，但是没有提供开平方运算，Fibonacci公式中的开平方运算要自己实现。这里主要介绍一下自己是如何实现开平方运算的
private static BigDecimal mysqrt(BigDecimal a, int scale) {
BigDecimal x = new BigDecimal(Math.sqrt(a.doubleValue()),
MathContext.DECIMAL64);
if (scale < 17)
return x;
BigDecimal b2 = new BigDecimal("2");
for (int tempScale = 16; tempScale < scale; tempScale *= 2) {
// x = x - (x * x - a) / (2 * x);
x = x.subtract(x.multiply(x).subtract(a)
.divide(x.multiply(b2), scale, BigDecimal.ROUND_HALF_EVEN));
}
return x;
}
这里用到了牛顿线性迭代算法，如果不明白的话可以在百度搜索。返回的结果是小数点后精确到scale位的数字。
现在把所有代码给出
package com.fujitsu.soft.rad.devsemi.fibonacci3; import java.math.BigDecimal;
import java.math.MathContext; public class Fibonacci { /*
* by l.zhang
*/
public static void main(String[] args) { System.out.println(fibonacci(100)); } /*
* by l.zhang
*/ public static String fibonacci(int i) {// 大きい桁表現すればlong ２動作の問題 if (i < 0 || i > 1000) {
System.out.println("please input a new number ");
return "-1";
} else if (i == 0) { return "0";
} else if (i == 1) {
return "1";
} else {
return siki(i); } } /*
* 公式で計算 i>=2 by l.zhang
*/
private static String siki(int i) { BigDecimal temp1 = mysqrt(new BigDecimal("5.0"), 100);// Math.pow(5.0,
// 0.5)
BigDecimal temp2 = temp1.divide(new BigDecimal("5.0"));// Math.pow(5.0,
// 0.5) / 5.0;
BigDecimal temp3 = new BigDecimal("1.0");
BigDecimal temp4 = temp3.add(temp1);// (1 + Math.pow(5.0, 0.5))
BigDecimal temp5 = temp3.subtract(temp1);// (1 - Math.pow(5.0, 0.5))
BigDecimal temp6 = temp4.divide(new BigDecimal("2.0"));// (1 +
// Math.pow(5.0,
// 0.5)) / 2.0
BigDecimal temp7 = temp5.divide(new BigDecimal("2.0"));// (1 -
// Math.pow(5.0,
// 0.5)) / 2.0
BigDecimal temp8 = temp6.pow(i, new MathContext(100));// Mypow(temp6,
// i);//
// Math.pow((1 +
// Math.pow(5.0, 0.5))
// / 2.0, i) BigDecimal temp9 = temp7.pow(i, new MathContext(100));// Mypow(temp7,
// i);//
// Math.pow((1 -
// Math.pow(5.0, 0.5))
// / 2.0, i);
// double temp2 = Math.pow((1 + Math.pow(5.0, 0.5)) / 2.0, i);
// double temp3 = Math.pow((1 - Math.pow(5.0, 0.5)) / 2.0, i);
BigDecimal temp10 = temp8.subtract(temp9);
BigDecimal result = temp2.multiply(temp10); String str_res = result.toString();
System.out.println(str_res);
int index = str_res.indexOf(".", 0); return str_res.substring(0, index);
// (temp1 * (temp2 - temp3));
} private static BigDecimal mysqrt(BigDecimal a, int scale) { BigDecimal x = new BigDecimal(Math.sqrt(a.doubleValue()),
MathContext.DECIMAL64);
if (scale < 17)
return x; BigDecimal b2 = new BigDecimal("2");
for (int tempScale = 16; tempScale < scale; tempScale *= 2) {
// x = x - (x * x - a) / (2 * x);
x = x.subtract(x.multiply(x).subtract(a)
.divide(x.multiply(b2), scale, BigDecimal.ROUND_HALF_EVEN));
}
return x; } }