java - 总结巨大的斐波那契数(最多 10^18)

Question

我最近遇到一个问题，给定一个 l和 r您需要找出所有 x 的总和，使得 l <= x <= r (mod10^9 + 7)。

而且， 1 <= l <= r <= 10^18

令 sum(x) 为斐波那契数之和，直到 x。设 fibo(x) 为 xth斐波那契数。据了解，

sum(x) = fibo(x+2) - 1

使用这个我使用了this post在 O(logn) 时间内计算第 n 个斐波那契项。我想知道是否可以比这更快地完成。下面是我的实现

public class FastFibonacci {
    private static Map<BigInteger, BigInteger> map;
    private static BigInteger mod = BigInteger.valueOf(1000000007);


    public static BigInteger nthFibonacci(BigInteger num) {
        if (num.compareTo(BigInteger.valueOf(2)) <= 0) return BigInteger.ONE;
       return solve(num.subtract(BigInteger.ONE)).mod(BigInteger.valueOf(10000));
    }

    public static BigInteger solve(BigInteger num) {
        if (map.get(num) != null) {
            return map.get(num);
        } else {
            BigInteger k = num.divide(BigInteger.valueOf(2));
            if (num.mod(BigInteger.valueOf(2)).compareTo(BigInteger.ZERO) == 0) {
                // f(2*k)
                map.put(num, (solve(k).multiply(solve(k)).mod(mod).add(solve(k.subtract(BigInteger.ONE)).multiply(solve(k.subtract(BigInteger.ONE))).mod(mod)).mod(mod)));
                return map.get(num);
            } else {
                // f(2*k + 1)
                map.put(num, (solve(k).multiply(solve(k.add( BigInteger.ONE))).mod(mod).add(solve(k).multiply(solve(k.subtract(BigInteger.ONE))).mod(mod))).mod(mod));
                return map.get(num);
            }
        }
    }

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        map = new HashMap<>();
        map.put(BigInteger.ZERO, BigInteger.ONE);
        map.put(BigInteger.ONE, BigInteger.ONE);
        int test = in.nextInt();
        BigInteger[] ls = new BigInteger[test];
        BigInteger[] rs = new BigInteger[test];
        for (int i = 0; i < test; i++) {
            ls[i] = new BigInteger(in.readString());
            rs[i] = new BigInteger(in.readString());
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < test; i++) {
            BigInteger sumUptoL = nthFibonacci(ls[i]).subtract(BigInteger.ONE);
            BigInteger sumUptoR = nthFibonacci(rs[i].add(BigInteger.valueOf(1))).subtract(BigInteger.ONE);
            sb.append(sumUptoR.subtract(sumUptoL));
            sb.append("\n");
        }
        System.out.print(sb.toString());

    }
}

Answer 1

假设对于给定的数字 N 你只想知道 fib(N+2)-1 而你真的不需要显示所有序列，你可以使用非递归方法。以下函数使用 double ，但您可以将其重构为 BigInteger 以接受更大的值:

public double getFibonacci(int n) {
    double f1 = Math.pow(((1 + Math.sqrt(5)) / 2.0), n);
    double f2 = Math.pow(((1 - Math.sqrt(5)) / 2.0), n);

    return Math.floor((f1 - f2) / Math.sqrt(5));
}