последовательность Фибоначчи при п> 46 Java

Question

У меня есть следующий код, который обеспечивает правильные значения для п < 47.

public static int fib(int n) { 
    int nthTerm = 0; 
    if (n == 2) 
     nthTerm = 1; 
    else { 
     double goldenRatio = (1 + Math.sqrt(5))/2; 
     nthTerm = (int) (Math.round(Math.pow(goldenRatio, n) 
       - Math.pow(1 - goldenRatio, n))/Math.sqrt(5)); 

     if (n % 2 == 1 && n < 45) 
      nthTerm++; 
    } 
    return nthTerm; 
} 

Любое значение для п> 46 находится вне диапазона Int. Как я мог адаптировать этот подход к работе при n> 46?

P.S. Я знаю BigInteger, но не очень разбираюсь в этом, поэтому я был бы признателен за использование BigInteger.

Answer 1

Вы можете использовать это для transformated кода в BigInteger.

package your.pack 

import java.math.BigDecimal; 
import java.math.BigInteger; 

/** 
* Created on 3/6/16. 
*/ 
public class Fibonacci { 

    private static BigDecimal goldenRatio = new BigDecimal((1 + Math.sqrt(5))/2); 
    private static BigDecimal goldenRatioMin1 = goldenRatio.subtract(BigDecimal.ONE); 
    private static BigDecimal sqrt5 = new BigDecimal(Math.sqrt(5)); 

    private static BigInteger fib(int n) { 
     BigInteger nthTerm = new BigInteger("0"); 
     if (n == 2) 
      nthTerm = BigInteger.ONE; 
     else { 
      BigDecimal minResult = goldenRatio.pow(n).subtract(goldenRatioMin1.pow(n)); 
      nthTerm = minResult.divide(sqrt5,0).toBigInteger(); 

      if (n % 2 == 1 && n < 45){ 
       nthTerm = nthTerm.add(BigInteger.ONE); 
      } 

     } 
     return nthTerm; 
    } 

    private static int fib2(int n) { 
     int nthTerm = 0; 
     if (n == 2) 
      nthTerm = 1; 
     else { 
      double goldenRatio = (1 + Math.sqrt(5))/2; 
      nthTerm = (int) (Math.round(Math.pow(goldenRatio, n) 
        - Math.pow(1 - goldenRatio, n))/Math.sqrt(5)); 

      if (n % 2 == 1 && n < 45) 
       nthTerm++; 
     } 
     return nthTerm; 
    } 

    public static void main(String []args){ 
     System.out.println(
       fib(47) 
     ); 
    } 

} 

Метод fib2 - ваш код, fib - преобразованный в BigInteger. Cheers

Answer 2

Использование long вместо использования int, и помните, чтобы привести значение от Math.round() до long, а также (в письменной форме (long) Math.round(...) так же, как вы отлиты в int).

Answer 3

Причина вы не можете использовать int потому, что fib(47) является 2971215073, который перетекает в Java 32-разрядное int (2³¹-1). Вы можете использовать memoizationоптимизации реализовать его BigInteger как,

private static Map<Integer, BigInteger> memo = new HashMap<>(); 
static { 
    memo.put(0, BigInteger.ZERO); 
    memo.put(1, BigInteger.ONE); 
} 

public static BigInteger fib(int n) { 
    if (memo.containsKey(n)) { 
     return memo.get(n); 
    } 
    BigInteger v = fib(n - 2).add(fib(n - 1)); 
    memo.put(n, v); 
    return v; 
} 

Answer 4

Если вы используете long, вы поддерживаете отлично диапазон по 1000; но если вы хотите поддерживать все возможные значения, вам необходимо использовать BigInteger.

Пример из использования long:

public static long fib(int n) 
{ 
    long f0 = 1; 
    long f1 = 1; 

    long c = 2; 

    while(c < n) 
    { 
     long tmp = f0+f1; 
     f0 = f1; 
     f1 = tmp; 
     c++; 
    } 

    return f1; 
}