Good day. I wrote a code that calculates the remainder of dividing the n-th Fibonacci number by the number entered from the console, where n can be very large (up to 10 ^ 18): http://pastebin.com/H9U5q6sr

I use an optimized algorithm with Q-matrices: https://habrahabr.ru/post/148336/ , I also bring in the power too quickly: by the algorithm of fast exponentiation. No cycles in the calculation of the elements of the matrix either. For some reason everything works very slowly (slow multiplication, as determined). I do not understand why so and how to fix it. Who faced, advise, please, how to solve the problem.

public void bigfib(){ Scanner sc = new Scanner(System.in); BigInteger n = sc.nextBigInteger(); BigInteger m = sc.nextBigInteger(); BigInteger [][] a = new BigInteger[][]{{BigInteger.ONE,BigInteger.ONE},{BigInteger.ONE,BigInteger.ZERO}}; System.out.println(pow(a,n)[0][1].mod(m)); } private BigInteger[][] mult(BigInteger[][] m1, BigInteger[][] m2) { BigInteger a = m1[0][0]; BigInteger a2 = m2[0][0]; BigInteger b = m1[0][1]; BigInteger b2 =m2[0][1]; BigInteger c = m1[1][0]; BigInteger c2 = m2[1][0]; BigInteger d = m1[1][1]; BigInteger d2 =m2[1][1]; BigInteger a11 = a.multiply(a2).add(b.multiply(c2)); BigInteger a12 = a.multiply(b2).add(b.multiply(d2)); BigInteger a21 = c.multiply(a2).add(d.multiply(c2)); BigInteger a22 = c.multiply(b2).add(d.multiply(d2)); BigInteger[][] mResult = new BigInteger[][]{{a11,a12},{a21,a22}}; return mResult; } private BigInteger[][] pow(BigInteger a[][], BigInteger p) { BigInteger my2 = new BigInteger("2"); BigInteger[][] result; if (p.equals(BigInteger.ONE)) return a; if (p.equals(my2)) return mult(a,a); if (p.mod(my2).equals(BigInteger.ONE)) { return mult(a,pow(a,p.subtract(BigInteger.ONE))); } else { result = pow(a,p.divide(my2)); return mult(result,result); } }
  • one
    The implementation on BigInteger will not be fast by definition. - Nofate ♦
  • The good news is that you don’t need to contact large numbers at all, because at every step you don’t need to get results that exceed m . - Nofate ♦
  • @Nofate, wait a minute, schA. I need to consider n, which certainly can be up to 10 ^ 18, i.e. everywhere yuzat long? Or do you suggest not doing pow(a,n)[0][1].mod(m) , but return mult(a,pow(a,p.subtract(BigInteger.ONE))).mod(m) ? - TheDoctor

1 answer 1

Wikibooks solution

 private static long fib(long n, long m) { long a = 1, b = 1, // матрица А c = 1, d = 0, // матрица А rc = 0, rd = 1, // вектор R ta, tb, tc; while (n > 0) { if ((n & 1) == 1) { // Если степень нечетная // Умножаем вектор R на матрицу A tc = rc; rc = (rc * a + rd * c) % m; rd = (tc * b + rd * d) % m; } // Умножаем матрицу A на саму себя ta = a; tb = b; tc = c; a = (a * a + b * c) % m; b = (ta * b + b * d) % m; c = (c * ta + d * c) % m; d = (tc * tb + d * d) % m; n >>= 1; // Уменьшаем степень вдвое } return rc; } public static void main(String[] args) { System.out.println(fib(11527523930876953L, 26673)); // 10552 }
  • Saw very similar to c ++ ... Let's see, he messed up on large numbers (negative residues). I have already solved the problem, by the way, it is by stuffing the modulo division into the calculation of matrix elements, everything works. In any case, thank you very much for the help :) - TheDoctor