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];

}

//矩阵乘法器方法：

  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）

Java 斐波那契数列 BigInteger

Java Fibonocci sequence BigInteger

java

biginteger

fibonacci