斐波那契数

斐波那契数的定义

斐波那契数是一个自然数序列，以数字 0 和 1 开头，每个后续数字都等于前两个数字的总和：

前 10 个斐波那契数：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

获得第一个n斐波那契数

要找到第一个n斐波那契数，您可以创建一个大小为 的数组n，前两个元素将是 0 和 1，其余元素可以使用循环和上述公式获得：

int[] f = new int[n];
f[0] = 0;
f[1] = 1;
for (int i = 2; i < n; ++i) {
    f[i] = f[i - 1] + f[i - 2];
}

该代码假定存在n可以从键盘输入的变量，如下所示：

Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();

填充数组后，可以使用循环将f获得的第一个n斐波那契数显示在屏幕上：

for (int i = 0; i < n; ++i) {
    System.out.println(f[i]);
}

在线示例代码

值得注意的是int，Java中的类型只允许你存储最多2 ³¹ -1的数字，所以上面的方法只会计算前46个斐波那契数（试图计算第47个斐波那契数时，会发生溢出并且会得到一个负数）。使用数据类型long而不是int无溢出将计算前 91 个斐波那契数。要计算后续的斐波那契数，可以使用JavaBigInteger中实现长算法的类。

获取n第 斐波那契数

只获取n第 -th 斐波那契数，不需要使用数组，创建两个变量a和就足够了b，它将存储最后两个斐波那契数，并重新计算这些变量的n - 2时间：

int a = 0;
int b = 1;
for (int i = 2; i <= n; ++i) {
    int next = a + b;
    a = b;
    b = next;
}
System.out.println(b);

在线示例代码

斐波那契数的递归计算

还有一种计算斐波那契数的递归方法。但是，不建议使用它，因为与前两种方法不同，它在线性时间内工作n，递归方法可能需要更长的时间。

// функция, возвращающая n-ое число Фибоначчи
public static int f(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return f(n - 1) + f(n - 2);
    }
}

在线示例代码

递归方法在指数时间内工作n，例如，n等于 46，递归方法花费的时间超过五秒，而记住最后两个斐波那契数的方法花费不到十分之一秒）。

递归方法可以工作很长时间，因为在计算过程中会从同一个参数多次调用函数（例如，计算f(5)函数时会递归调用f(4)and f(3)，两个递归调用都会转为f(2)），这将导致重复重复相同的操作。

O(log n)使用快速矩阵乘法（使用乘法运算）快速计算斐波那契数

考虑矩阵：

使用矩阵乘法，最后两个斐波那契数的递归关系可以写成：

扩大这个比率，我们得到：

因此，要找到第 th 个斐波那契数，只需将矩阵乘以1 次方n就足够了。这可以通过快速求幂算法来完成。An - 1

// матричное умножение двух матриц размера 2 на 2
public static BigInteger[][] matrixMultiplication(BigInteger[][] a, BigInteger[][] b) {
    // [a00 * b00 + a01 * b10, a00 * b01 + a01 * b11]
    // [a10 * b00 + a11 * b10, a10 * b01 + a11 * b11]
    return new BigInteger[][]{
            {a[0][0].multiply(b[0][0]).add(a[0][1].multiply(b[1][0])), a[0][0].multiply(b[0][1]).add(a[0][1].multiply(b[1][1]))},
            {a[1][0].multiply(b[0][0]).add(a[1][1].multiply(b[1][0])), a[1][0].multiply(b[0][1]).add(a[1][1].multiply(b[1][1]))},
    };
}

// возведение матрицы размера 2 на 2 в степень n
public static BigInteger[][] matrixPowerFast(BigInteger[][] a, int n) {
    if (n == 0) {
        // любая матрица в нулевой степени равна единичной матрице
        return new BigInteger[][]{
                {BigInteger.ONE, BigInteger.ZERO},
                {BigInteger.ZERO, BigInteger.ONE}
        };
    } else if (n % 2 == 0) {
        // a ^ (2k) = (a ^ 2) ^ k
        return matrixPowerFast(matrixMultiplication(a, a), n / 2);
    } else {
        // a ^ (2k + 1) = (a) * (a ^ 2k)
        return matrixMultiplication(matrixPowerFast(a, n - 1), a);
    }
}

// функция, возвращающая n-ое число Фибоначчи
public static BigInteger fibonacci(int n) {
    if (n == 0) {
        return BigInteger.ZERO;
    }

    BigInteger[][] a = {
            {BigInteger.ONE, BigInteger.ONE},
            {BigInteger.ONE, BigInteger.ZERO}
    };
    BigInteger[][] powerOfA = matrixPowerFast(a, n - 1);
    // nthFibonacci = powerOfA[0][0] * F_1 + powerOfA[0][0] * F_0 = powerOfA[0][0] * 1 + powerOfA[0][0] * 0
    BigInteger nthFibonacci = powerOfA[0][0];
    return nthFibonacci;
}

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

在线示例代码

除了@diralik的回答

无需矩阵的快速计算

矩阵幂可以用斐波那契数来表示。用归纳法很容易证明

然后

这个表达式为我们提供了将斐波那契数指数加倍的公式：

这个公式在下面的代码中实现Fib.fast(int)。

import java.math.BigInteger;

public class Fib {
    public BigInteger next_ = BigInteger.ONE;
    public BigInteger current_ = BigInteger.ZERO;
    public int n = 0;

    public Fib next() {
        BigInteger tmp = next_.add(current_);
        current_ = next_;
        next_ = tmp;
        n++;
        return this;
    }

    public static Fib slow(int n) {
        var result = new Fib();
        for (var i = 0; i < n; i++) {
            result.next();
        }
        return result;
    }

    public static Fib fast(int n) {
        if (n < 16) {
            return Fib.slow(n);
        } 

        var result = Fib.fast(n/2);
        result.n *= 2;
        // F_{2n+1} = F_{n+1}**2 + F_{n}**2
        var _next = result.next_.multiply(result.next_).add(result.current_.multiply(result.current_));
        // F_{2n} = (2*F_{n+1} - F_{n})*F_{n}
        var _current = (result.next_.add(result.next_).subtract(result.current_)).multiply(result.current_);
        result.next_ = _next;
        result.current_ = _current;
        if (n%2 == 1) {
            result.next();
        }
        return result;
    }
}

通过黄金比例进行评估

对于斐波那契数，有比奈公式，它无需迭代即可计算斐波那契数。

由于斐波那契数很快就超出了类型double，为了通过比内公式估计斐波那契数，我使用BigDecimal四舍五入到 20 位有效数字。结果，此四舍五入给出了 10 个正确数字。

    private static final MathContext _mc = new MathContext(20, RoundingMode.HALF_UP);
    private static final double _sqrt5 = Math.sqrt(5);
    public static final BigDecimal Sqrt5 = new BigDecimal(_sqrt5, _mc);
    public static final BigDecimal Phi = new BigDecimal((1 + _sqrt5)/2, _mc);

    public static BigDecimal estimate(int n) {
        return Phi.pow(n, _mc).divide(Sqrt5, _mc);
    }

速度比较

计算斐波那契数的快速公式每次迭代使用三个乘法。但由于迭代次数以对数增长n，因此快速公式的总计算时间比经典公式少几倍。

以下是 的比较结果n=100, 1000, 10000, 100000, 1000000。以毫秒为单位的时间。Estimate- 这只是根据比内公式的估计。

Slow: 100: 0.3249 (ms)
Fast: 100: 0.0736 (ms)
As double: 100: 3.5422484817E+20
Estimate : 100: 3.5422484817926308651E+20
Slow: 1000: 0.4168 (ms)
Fast: 1000: 0.1707 (ms)
As double: 1000: 4.3466557686E+208
Estimate : 1000: 4.3466557686938912905E+208
Slow: 10000: 5.604 (ms)
Fast: 10000: 1.526 (ms)
As double: 10000: 3.3644764876E+2089
Estimate : 10000: 3.3644764876443071607E+2089
Slow: 100000: 231.6341 (ms)
Fast: 100000: 8.0684 (ms)
As double: 100000: 2.5974069347E+20898
Estimate : 100000: 2.5974069347308882558E+20898
Slow: 1000000: 15967.3608 (ms)
Fast: 1000000: 89.9357 (ms)
As double: 1000000: 1.9532821287E+208987
Estimate : 1000000: 1.9532821287733027741E+208987

输出使用一个函数asFloatString，对于大整数，该函数将近似表示构建为实数

    private static String asFloatString(BigInteger bint, int ndig) {
        var _full = bint.toString(10);
        var s = _full.substring(0, ndig+1);
        s = s.substring(0,1) + "." + s.substring(1) + "E+" + (_full.length()-1);
        return s;
    }