Faster algorithm to find fibonacci n mod m

Question

I have almost 3 days hitting my head against the wall to find a fast algorithm to find the fib n mod m, that is, the remainder of fibonacci number n divided by m, where: 1 <= n <= 10^18 and 2 <= m <= 10^5

As an example, I'm given as:

Input: 281621358815590 30524 // n and m
Output: 11963

With this test, my code works, but then the test fails with this: 100 100000

This is my code:

import java.math.BigInteger;
import java.util.Scanner;

public class FibonacciHuge {
    private static BigInteger fibmod(long n, BigInteger m) {
        BigInteger a=BigInteger.ZERO;
        BigInteger b=BigInteger.ONE;
        BigInteger c;
        long i;
        for (i=2; i<=n;i++){
            c=a.add(b);
            a=b;
            b=c;
        }
        return b.mod(m);
      }

    private static BigInteger fibComplex (long n, BigInteger m) {
        int count = 2;
        for (int i = 2; i < (m.pow(2)).longValue()-1; i++) {
            long a2=fibmod(i+1,m).longValueExact();
            long a3=fibmod(i+2,m).longValueExact();
            count= count+1;
            if (a2==0 && a3==1){
                break;
            }

        }   
        return fibmod(n % count,m);
    }

      public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        BigInteger m = in.nextBigInteger();
        System.out.println(fibComplex(n,m));
        in.close();
      }
}

In fibmod(), I find the fibonacci of n and at the end I use m as modulator. In fibComplex(), I'm suppose to find the length of the Pisani period, so I use reduce n to the remainder of n % (lengthofPisaniPeriod) and then apply the mod m (so n isn't so big). For Java, this should be done in 1.5 secs but for big Pisani periods (as 100,000) its just too much. Some friend said they have done it without finding the Fib n first, just iterating to find the length of the period and using the tip to reduce n to the remainder of n % (length of period).

I've searched for the fastest fibonacci algorithm here but the solution seems to be easier, about reducing n, as I describe before, but I can grasp the concept after 3 days. I'm working with BigIntegers but I'm not sure if its really needed,since the hint say:

"In this problem, the given number n may be really huge. Hence an algorithm looping for n iterations will not fit into one second for sure. Therefore we need to avoid such a loop".

You can find a Pisani cycle/period calculator here, it works fast even for large numbers so I wish i could know what algorithm they use.

Sorry if something in my question is not clear, it 11 am and I havent slept all night trying to solve this. I can edit it so its more clear afer a couple hours of sleep if needed.

Answer 1

The dynamic method you're using isn't fast enough. You could try the matrix exponentiation, or even better, fast doubling. The idea is that given F(k) and F(k+1), we can calculate these:

F(2k) = F(k) [2F(k+1) − F(k)]
F(2k+1) = F(k+1)^2 + F(k)^2

In Java it would be something like this:

private static BigInteger fastFibonacciDoubling(int n) {
        BigInteger a = BigInteger.ZERO;
        BigInteger b = BigInteger.ONE;
        int m = 0;
        for (int i = 31 - Integer.numberOfLeadingZeros(n); i >= 0; i--) {
            // Loop invariant: a = F(m), b = F(m+1)

            // Double it
            BigInteger d = multiply(a, b.shiftLeft(1).subtract(a));
            BigInteger e = multiply(a, a).add(multiply(b, b));
            a = d;
            b = e;
            m *= 2;

            if (((n >>> i) & 1) != 0) {
                BigInteger c = a.add(b);
                a = b;
                b = c;
                m++;
            }
        }
        return a;
    }

Apply this method instead of the one you inserted in your answer, you'll see the difference. ;)

You can find more comparisons about different Fibonacci methods at https://www.nayuki.io/page/fast-fibonacci-algorithms .

Answer 2

This is the final solution that passed the 22 tests. It's a bit sloppy and probably could be refactorized but with 2 hours of sleep, I'm glad it worked.

import java.math.BigInteger;
import java.util.Scanner;

public class FibonacciHugev2 {

    private static long lenP(BigInteger m) {
        long q=m.longValueExact();
        long a=0;
        long b=1;
        long c=0;
        long i;
        int count = 0;
        for (i=0; i<=(q*q)-1;i++){
            if (a==0 && b==1 && count > 0){
                break;
            }

            c=(a+b) % q;
            a=b % q;
            b=c % q;
            count = count + 1;  
        }
        return count;
      }

    private static BigInteger fibmod(long n, BigInteger m) {
        long r=n % lenP(m); 
        BigInteger a=BigInteger.ZERO;
        BigInteger b=BigInteger.ONE;
        BigInteger c;
        long i;
        if (r==0){
            return BigInteger.ZERO;
        }
        if (r==1){
            return BigInteger.ONE;
        }
        for (i=2; i<=r;i++){
            c=a.add(b);
            a=b;
            b=c;
        }
        return b.mod(m);
      }

      public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        BigInteger m = in.nextBigInteger();
        //System.out.println(lenP(m));
        System.out.println(fibmod(n,m));
        in.close();
      }
    }

Answer 3

The trick is to keep the number of digits from growing too large as you calculate. Let us return to the first procedure. This is a mathematical fact: (a + b) mod M == ((a mod M) + (b mod M)). Therefore: Change the procedure to calculate 'c' mod M; then at the end you will only need to return 'b' directly.

I know calculating mod M on each iteration seems expensive, but it won't be as bad as it seems, because 'a' and 'b' stay smaller than M. In fact, if you do this, you don't even need to use the 'mod()' function: 'a' and 'b' stay under M throughout the loop, so the next value of 'c' will be under 2M; you just need to check if it goes over M, and if so, subtract M -once-. In fact, I would write the code for 'c' as follows (conceptually, of course; you'll need to use BigNum methods):

    c = a + b;
    c1 = c - M;   // need to declare c1
    if ( !c1.negative() ) c = c1;

[I do it this way because 'c >= M' and 'c = c - M' are almost the same operation under the hood, so why incur the cost twice? Of course I am also assuming BigNum has a faster sign-test method than comparison to zero].