Ayro

Fibonacci computation

Oct 1st, 2012
196
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.math.BigInteger;
  2.  
  3. public class Fib {
  4.  
  5.     static BigInteger calcSlow(int n) {
  6.         if (n <= 1)
  7.             return n == 0 ? BigInteger.ZERO : BigInteger.ONE;
  8.         BigInteger f0 = BigInteger.ZERO, f1 = BigInteger.ONE, f2;
  9.         for (int i = 0; i < n - 1; i++) {
  10.             f2 = f0.add(f1);
  11.             f0 = f1;
  12.             f1 = f2;
  13.         }
  14.         return f1;
  15.     }
  16.  
  17.     static int calcMod(int n, long MOD) {
  18.         Matrix m = new Matrix(2);
  19.         m.a[0][0] = m.a[0][1] = m.a[1][0] = 1;
  20.         return (int) Matrix.powMod(m, n, MOD).a[0][1];
  21.     }
  22.  
  23.     static class Matrix {
  24.         int n;
  25.         long[][] a;
  26.  
  27.         Matrix(int n) {
  28.             this.n = n;
  29.             this.a = new long[n][n];
  30.         }
  31.  
  32.         static Matrix multiply(Matrix m1, Matrix m2, long MOD) {
  33.             int n = m1.n;
  34.             Matrix ret = new Matrix(n);
  35.             for (int i = 0; i < n; i++) {
  36.                 for (int j = 0; j < n; j++) {
  37.                     for (int t = 0; t < n; t++) {
  38.                         ret.a[i][j] += m1.a[i][t] * m2.a[t][j];
  39.                         ret.a[i][j] %= MOD;
  40.                     }
  41.                 }
  42.             }
  43.             return ret;
  44.         }
  45.  
  46.         static Matrix id(int n) {
  47.             Matrix ret = new Matrix(n);
  48.             for (int i = 0; i < n; i++)
  49.                 ret.a[i][i] = 1;
  50.             return ret;
  51.         }
  52.  
  53.         // evaluates matr^n modulo MOD
  54.         static Matrix powMod(Matrix matr, int n, long MOD) {
  55.             if (n == 0)
  56.                 return id(2);
  57.             Matrix t = Matrix.powMod(matr, n / 2, MOD);
  58.             t = Matrix.multiply(t, t, MOD);
  59.             return n % 2 == 0 ? t : Matrix.multiply(t, matr, MOD);
  60.         }
  61.     }
  62. }
RAW Paste Data