Java斐波那契數列BigInteger

Question

我試圖運行一個程序，在斐波那契數列中找到第n個序列;但是，問題是，我想在其中實現BigInteger，因此它可以運行1000甚至更多的值。

有什麼方法可以有效地添加它？

import java.util.*; 
import java.math.*; 
public class fib { 
//Arkham 
    /*public static BigInteger fibonacci2(int n) { 
    if (n == 0 || n == 1) { 
     return BigInteger.ONE; 
    } 
    return fibonacci2(n - 2).add(fibonacci2(n-1)); 
}*/ 

    public static int Fibonacci(int n) { 

     int num = Math.abs(n); 
     if (num == 0) { 
      return 0; 
     } 
     else if (num <= 2) { 
      return 1; 
     } 

     int[][] number = { { 1, 1 }, { 1, 0 } }; 
     int[][] result = { { 1, 1 }, { 1, 0 } }; 

     while (num > 0) { 
      if (num%2 == 1) result = MultiplyMatrix(result, number); 
      number = MultiplyMatrix(number, number); 
      num/= 2; 
     } 
     return result[1][1]*((n < 0) ? -1:1); 
    } 

    public static int[][] MultiplyMatrix(int[][] mat1, int[][] mat2) { 
     return new int[][] { 
       { mat1[0][0]*mat2[0][0] + mat1[0][1]*mat2[1][0], 
        mat1[0][0]*mat2[0][1] + mat1[0][1]*mat2[1][1] }, 
       { mat1[1][0]*mat2[0][0] + mat1[1][1]*mat2[1][0], 
        mat1[1][0]*mat2[0][1] + mat1[1][1]*mat2[1][1] } 
     }; 
    } 

    public static void main(String[] args) { 

     Scanner reader = new Scanner(System.in); // Reading from System.in 
     System.out.println("Enter a number: "); 
     int n = reader.nextInt(); 

     System.out.println("\n" + Fibonacci(n)); 
    } 
} 

Answer 1

當您更換int通過BigInteger你應該做一些改變，但是，我改變了你的代碼，並用這樣的事情上來：

public static BigInteger FibonacciB(int n) { 
    final BigInteger one = BigInteger.ONE; 
    final BigInteger zero = BigInteger.ZERO; 
    final BigInteger two = new BigInteger(String.valueOf(2)); 
    final BigInteger minusOne = one.negate(); 

    BigInteger num = new BigInteger(String.valueOf(n)); 

    if (num.equals(zero)) { 
     return zero; 
    } else if (num.compareTo(two) <= 0) { 
     return one; 
    } 

    BigInteger[][] number = {{one, one}, {one, zero}}; 
    BigInteger[][] result = {{one, one}, {one, zero}}; 

    while (num.compareTo(zero) > 0) { 
     if (num.mod(two).equals(one)) result = MultiplyMatrixB(result, number); 
     number = MultiplyMatrixB(number, number); 
     num = num.divide(two); 
    } 

    if (num.compareTo(zero) < 0) 
     return result[1][1].multiply(minusOne); 
    return result[1][1]; 

} 

//矩陣mutltiplier方法：

public static BigInteger[][] MultiplyMatrixB(BigInteger[][] mat1, BigInteger[][] mat2) { 

    return new BigInteger[][]{ 
      {(mat1[0][0].multiply(mat2[0][0])).add((mat1[0][1].multiply(mat2[1][0]))), 
        (mat1[0][0].multiply(mat2[0][1])).add((mat1[0][1].multiply(mat2[1][1]))) 
      }, 
      { 
        (mat1[1][0].multiply(mat2[0][0])).add((mat1[1][1].multiply(mat2[1][0]))), 
        (mat1[1][0].multiply(mat2[0][1])).add((mat1[1][1].multiply(mat2[1][1]))) 
      } 
    }; 
} 

我希望這會幫助你

Answer 2

是java正確的工具嗎？也許Kotlin會更好地工作：

tailrec fun fibonacci(i:BigInteger, current:BigInteger=zero, next:BigInteger=one):BigInteger { 
    return if (i == zero) current else iterate(i - one, next, current + next) 
    } 

（從https://github.com/russel/Fibonacci/blob/master/Kotlin/src/main/kotlin/uk/org/winder/maths/fibonacci/fibonacci.kt拍攝）