Матричный алгоритм возведения в степень для больших значений N

Question

Я хочу вычислить Фибоначчи очень большого значения N, т.е. 10^6 со сложностью O (logN). Вот мой код, но он дает результат для 10^6 за 30 секунд, что очень трудоемко. Помогите мне указать на ошибку. Я должен дать результат по модулю 10^9 + 7.

static BigInteger mod=new BigInteger("1000000007"); 

BigInteger fibo(long n){ 
    BigInteger F[][] = {{BigInteger.ONE,BigInteger.ONE},{BigInteger.ONE,BigInteger.ZERO}}; 
    if(n == 0) 
     return BigInteger.ZERO; 
    power(F, n-1); 
    return F[0][0].mod(mod); 
} 

void power(BigInteger F[][], long n) { 
    if(n == 0 || n == 1) 
     return; 
    BigInteger M[][] = {{BigInteger.ONE,BigInteger.ONE},{BigInteger.ONE,BigInteger.ZERO}}; 
    power(F, n/2); 
    multiply(F, F); 
    if(n%2 != 0) 
     multiply(F, M); 
    } 

void multiply(BigInteger F[][], BigInteger M[][]){ 
    BigInteger x = (F[0][0].multiply(M[0][0])).add(F[0][1].multiply(M[1][0])) ; 
    BigInteger y = F[0][0].multiply(M[0][1]).add(F[0][1].multiply(M[1][1])) ; 
    BigInteger z = F[1][0].multiply(M[0][0]).add(F[1][1].multiply(M[1][0])); 
    BigInteger w = F[1][0].multiply(M[0][1]).add(F[1][1].multiply(M[1][1])); 

    F[0][0] = x; 
    F[0][1] = y; 
    F[1][0] = z; 
    F[1][1] = w; 
} 

Answer 1

я получаю более разумно - хотя до сих пор очень медленно - время real 0m2.335s с помощью кода.

алгоритм для вычисления чисел Фибоначчи в порядке (есть некоторые хитрости, которые могли бы ускорить его немного, но ничего очень драматично), поэтому проблема заключается в том, что операции на больших BigInteger с медленно, и F(10^6) имеет около 700 000 бит ,

Так как вы хотите, чтобы вычислить остаток по модулю mod = 10^9 + 7 и (mod-1)^2 помещается в long, вы можете получить гораздо более быстрой реализации с использованием long сек вместо BigInteger с, вычисление остатка на каждом шагу. Прямая транскрипция

public class FiboL { 

    static final long mod = 1000000007L; 

    static long fibo(long n){ 

      long F[][] = {{1,1},{1,0}}; 

      if(n == 0) 
      return 0; 
      power(F, n-1); 
      return F[0][0]; //.mod(mod); 
     } 

    static void power(long F[][], long n){ 

      if(n == 0 || n == 1) 
       return; 
      long M[][] = {{1,1},{1,0}}; 

      power(F, n/2); 
      multiply(F, F); 

      if(n%2 != 0) 
      multiply(F, M); 
     } 

    static void multiply(long F[][], long M[][]){ 

      long x = (F[0][0] * M[0][0]) % mod + (F[0][1] * M[1][0]) % mod; 
      long y = (F[0][0] * M[0][1]) % mod + (F[0][1] * M[1][1]) % mod; 
      long z = (F[1][0] * M[0][0]) % mod + (F[1][1] * M[1][0]) % mod; 
      long w = (F[1][0] * M[0][1]) % mod + (F[1][1] * M[1][1]) % mod; 

      F[0][0] = x % mod; 
      F[0][1] = y % mod; 
      F[1][0] = z % mod; 
      F[1][1] = w % mod; 
    } 
    public static void main(String[] args) { 
     System.out.println(fibo(1000000)); 
    } 
} 

работает в real 0m0.083s.

Answer 2

использовать эти recurrences:

F п -1 =F _н + F _{п -1}

F п = (2 F _{п -1}+ F п) F _н

вместе с memoization. Например, в Python можно использовать @functools.lru_cache декоратор, как это:

from functools import lru_cache 

@lru_cache(maxsize=None) 
def fibonacci_modulo(n, m): 
    """Compute the nth Fibonacci number modulo m.""" 
    if n <= 3: 
     return (0, 1, 1, 2)[n] % m 
    elif n % 2 == 0: 
     a = fibonacci_modulo(n // 2 - 1, m) 
     b = fibonacci_modulo(n // 2, m) 
     return ((2 * a + b) * b) % m 
    else: 
     a = fibonacci_modulo(n // 2, m) 
     b = fibonacci_modulo(n // 2 + 1, m) 
     return (a * a + b * b) % m 

это вычисляет 10 го числа Фибоначчи (по модулю 10 + 7) в течение нескольких микросекунд:

>>> from timeit import timeit 
>>> timeit(lambda:fibonacci_modulo(10 ** 6, 10 ** 9 + 7), number=1) 
0.000083282997366