Очень большой Фибоначчи в Java

Я пытаюсь быстро вычислить большие числа Фибоначчи. Вот мой код. Это число запретительно медленное для чисел свыше 1 миллиона, как его можно улучшить?Очень большой Фибоначчи в Java

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's хорошо работает. Спасибо, парни!

источник

2015-04-10 Chris Parry

You может профилировать его. Или вы можете попробовать алгоритм log (n). http://tech-queries.blogspot.com.au/2010/09/nth-fibbonacci-number-in-ologn.html?m=1 –

Я думаю, что это может быть хорошим вопросом на [Codereview] (http: //codereview.stackexchange.com/) –

Используйте формулу [формулу закрытой формы] (http://www.scibuff.com/2009/05/13/golden-nature-closed-form-formula-for-fibonacci-sequence /). Как [Бине] (http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html). –

Один из способов вычислить (N-1)th мощность матрицы 2х2:

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

Тогда мы имеем

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

И сила матрицы A можно вычислить эффективно использовать Exponentiation by squaring

источник

2015-04-10 04:11:30

Хорошая формула, откуда она взялась? Я не нашел его так, как мне было нужно, и должен был получить свой собственный от Binet (который сам был непригодным из-за ошибки округления), и это было больно. – maaartinus

Очень большой Фибоначчи в Java

ответ

Смежные вопросы