Java中的非常大斐波那契 [英] Very Large Fibonacci in Java

问题描述

我正在尝试快速计算较大的斐波那契数.这是我的代码.对于100万以上的数字，速度太慢了，如何改善?

I am trying to rapidly calculate large Fibonacci numbers. Here is my code. It is prohibitively slow for numbers above 1 million, how can it be improved?

public static BigInteger fib(BigInteger n) {

        int k = n.intValue();
        BigInteger ans = null;

        if(k == 0) { 
            ans = new BigInteger("0");
        } else if(Math.abs(k) <= 2) {
            ans = new BigInteger("1");
        } else {
            BigInteger km1 = new BigInteger("1");
            BigInteger km2 = new BigInteger("1");

            for(int i = 3; i <= Math.abs(k); ++i) {
                ans = km1.add(km2);
                km2 = km1;
                km1 = ans;
            }
        }

       if(k<0 && k%2==0) { ans = ans.negate(); }
       return ans;
    } 

Binet运作良好.谢谢你们！

Binet's worked well. Thanks guys!

推荐答案

一种方法是计算2x2矩阵的(N-1)th幂:

One way is to calculate the (N-1)th power of the 2x2 matrix:

A = ((1, 1), (1, 0))

那么我们就有

Fib(n) = A^(n-1)[0][0], for n >= 1

使用A的幂-power-function-powint-int>通过平方求幂

And the power of matrix A can be calculated efficiently using Exponentiation by squaring

这篇关于Java中的非常大斐波那契的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！