My algorithm for calculating the modulo of a very large fibonacci number is too slow

Question

The goal is to compute F(n) modulo m (m up to 10 power 5), where n may be really huge: up to 10 power 18.

My algorithm is too slow.

My approach: Calculate and store all Fibonacci numbers up to m, then iterate through that array and apply modulo on the fibonacci's.

Once the length of the pisano period is found, i can use this length to calculate the modulo of any F(n)

My code:

import java.math.BigInteger;
import java.util.*;

public class FibonacciAgain {


    private static ArrayList<BigInteger> calc_fib() {
        ArrayList<BigInteger> fib = new ArrayList<>();

        fib.add(BigInteger.ZERO);
        fib.add(BigInteger.ONE);
        for (int i = 2; i <= 100000; i++) {
            fib.add(fib.get(i - 2).add(fib.get(i - 1)));

        }
        return fib;
    }

    private static long calculatePeriod(ArrayList<BigInteger> fib, long modulo) {

        long periodLength = 0;
        boolean periodFound = false;
        long[] period = new long[1000000];
        period[0] = 0;
        period[1] = 1;
        period[2] = 1;


        int i = 3;
        while (!periodFound) {
            //period[i] = fib.get(i)
            //period[i]= fib.get(i).divide(new BigInteger(String.valueOf(i))).longValue();
            //System.out.println("Fib at " + i + ": " + fib.get(i));
            period[i] = fib.get(i).mod(new BigInteger(String.valueOf(modulo))).longValue();
            //System.out.println("1:" + period[i]);
            //System.out.println("2:" + period[i - 1]);
           // System.out.println("3: " + period[i - 2]);
            if (i == 100000){
                periodFound = true;
                periodLength = i - 1;

            }

           // if (period[i] == 1 && period[i - 1] == 1 && period[i - 2] == 0) {
            if (period[i - 1] == 1 && period[i - 2] == 0) {
                periodFound = true;
                periodLength = i - 2;

                //System.out.println("found");

            }
            i++;

        }
        //System.out.println("Period Length:" + periodLength);

        return periodLength;
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long m = scanner.nextLong();


        //M Fibonacci Numbers up to are stored here
        ArrayList<BigInteger> fib = new ArrayList<>();
        fib = calc_fib();

        // get the length of the pisano period
        long periodLength = calculatePeriod(fib, m);

        //
        long fibFirst = n%periodLength;
        System.out.println(fib.get((int) fibFirst).mod(new BigInteger(String.valueOf(m))).longValue());

    }
}

Any advice, how to make it faster?

Answer 1

there is no need to use BigInteger because:

1*2*3*4*...*N mod M
1+2+3+4+...+N mod M

is the same as

(...(((1*2 mod M)*3 mod M)*4 mod M)...*N mod M)
(...(((1+2 mod M)+3 mod M)+4 mod M)...+N mod M)

that should speed up a lot ... from (assumed karatsuba multiplication) O(3*N*(n^log2(3))) and or addition O(N*n) into linear O(N) where n is proportional bitwidth of your multiplicants/additionals with also far better constant time ...

IIRC there where also formulas for fast fibonaci computation (converting O(N) into something near O(log(N))

Here few examples: fast fibonacci algorithms

Here C++ example of naive (modfib0) and fast (modfib1 using power by squaring of 2x2 matrix) algo:

//---------------------------------------------------------------------------
int modfib0(int n,int m)
    {
    for (int i=0,x0=0,x1=1;;)
        {
        if (i>=n) return x1; x0+=x1; x0%=m; i++;
        if (i>=n) return x0; x1+=x0; x1%=m; i++;
        }
    }
//---------------------------------------------------------------------------
// matrix 2x2:  0 1
//              2 3
void modmul2x2(int *c,int *a,int *b,int m)  // c[4] = a[4]*b[4] %m
    {
    int t[4];
    t[0]=((a[0]*b[0])+(a[1]*b[2]))%m;
    t[1]=((a[0]*b[1])+(a[1]*b[3]))%m;
    t[2]=t[1]; // result is symetric so no need to compute: t[2]=((a[2]*b[0])+(a[3]*b[2]))%m;
    t[3]=((a[2]*b[1])+(a[3]*b[3]))%m;
    c[0]=t[0];
    c[1]=t[1];
    c[2]=t[2];
    c[3]=t[3];
    }
void modpow2x2(int *c,int *a,int n,int m)   // c[4] = a[4]^n %m
    {
    int t[4];
    t[0]=a[0]; c[0]=1;
    t[1]=a[1]; c[1]=0;
    t[2]=a[2]; c[2]=0;
    t[3]=a[3]; c[3]=1;
    for (;;)
        {
        if (int(n&1)!=0) modmul2x2(c,c,t,m);
        n>>=1; if (!n) break;
        modmul2x2(t,t,t,m);
        }
    }
int modfib1(int n,int m)
    {
    if (n<=0) return 0;
    int a[4]={1,1,1,0};
    modpow2x2(a,a,n,m);
    return a[0];
    }
//---------------------------------------------------------------------------

beware in order to comply with your constraints the used int variable must be at least 64bit wide !!! I am in old 32 bit environment and did not want to spoil the code with bigint class so I tested only with this:

int x,m=30000,n=0x7FFFFFFF;
x=modfib0(n,m);
x=modfib1(n,m);

And here results:

[10725.614 ms] modfib0:17301 O(N)
[    0.002 ms] modfib1:17301 O(log2(N))

As you can see the fast algo is much much faster than linear one ... however the measured time is too small for Windows environment and most of its time is most likely overhead instead of the function itself so I think it should be fast enough even for n=10^18 as its complexity is O(log2(N)) I estimate:

64-31 = 33 bits
0.002 ms * 33 = 0.066 ms

so the 64 bit computation should be done well below 0.1 ms of execution time on my machine (AMD A8-5500 3.2 GHz) which I think is acceptable...

The linear algo for 64bit would be like this:

10.725614 s * 2^33 = 865226435999039488 s = 27.417*10^9 years

but as you can see you would dye of old age long before that ...

Answer 2

To help speed up I modified your calculatePeriod() method. I did the following things.

1. Changed your fib cache to be memoized. It is calculated on the fly and added to the list. This would come in handy if you repeatedly prompted for values. Then no recalculation of the cache would be required.

2. I also added a map to store the fibFirst fibonacci with it's modulus.

3. I changed your BigInteger calls from new BigInteger(String.valueOf(modulo)) to BigInteger.valueOf(modulo). Not certain if it's faster but it is cleaner.

4. Finally, I moved values which were recalculated but didn't change outside of any loops.

Here is the modified method:

   static Map<Long, Map<Long,Long>> fibFirstMap = new HashMap<>();   

   static List<BigInteger> fibs = new ArrayList<>() {
      { 
      add(BigInteger.ZERO);
       add(BigInteger.ONE);
       add(BigInteger.ONE);
       add(BigInteger.TWO);
      }  
   };

   private static long calculateFirst(long nthfib, long modulo) {

      long fibFirst =
            fibFirstMap.computeIfAbsent(nthfib, k -> new HashMap<>()).getOrDefault(
                  modulo, -1L);

      if (fibFirst > 0L) {
         return fibFirst;
      }
      long periodLength = 0;
      boolean periodFound = false;
      long[] period = new long[1000000];
      period[0] = 0;
      period[1] = 1;
      period[2] = 1;
      int i = 3;
      BigInteger cons = BigInteger.valueOf(modulo);
      BigInteger nextFib;

      while (!periodFound) {

         if (i >= fibs.size()) {
            fibs.add(fibs.get(i - 2).add(fibs.get(i - 1)));
         }
         nextFib = fibs.get(i);

         period[i] = nextFib.mod(cons).longValue();
         if (i == 100000) {
            periodFound = true;
            periodLength = i - 1;
         }
         else if (period[i - 1] == 1 && period[i - 2] == 0) {
            periodFound = true;
            periodLength = i - 2;
         }
         i++;
      }

      fibFirst = nthfib % periodLength;
      fibFirstMap.get(nthfib).put(modulo, fibFirst);
      return fibFirst;

   }

A better approach might be to look into ways of getting away from BigInteger as has been suggested and looking for improvements in calculations based on advances in number theory.