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; } }
用BigDecimal类实现Fibonacci算法,布布扣,bubuko.com
原文：http://www.cnblogs.com/j3eee/p/3764355.html