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?

Would you like to try this solution? Its written in C++ but its algorithm so you can get the basic idea for the pisano_period https://medium.com/competitive/huge-fibonacci-number-modulo-m-6b4926a5c836 — Michael Michailidis, Oct 02 '19 at 14:37
`new BigInteger(String.valueOf(modulo))` can be one constant before the while: `BigInteger.valueOf(modulo)` — Joop Eggen, Oct 02 '19 at 14:40
my sugestion is do not calculate all the fibonacci numbers in advance, because you might not even use most of them. whenever you need a fib number calculate it on the fly using the formula (https://stackoverflow.com/a/12772137/6183889) and keep it in a cache map for later use. this way you only calculate the fibonaccis you actually use and cache them to save time. — Tom Elias, Oct 02 '19 at 14:59
Note that there is no guarantee that the Pisano period is <= m, since each Fibonacci number depends on *two* previous ones. — Matt Timmermans, Oct 02 '19 at 17:24
https://stackoverflow.com/questions/14661633/finding-out-nth-fibonacci-number-for-very-large-n — Matt Timmermans, Oct 02 '19 at 17:38
I updated my answer with C++ example of naive and fast approach for comparison the fast algo is more than `10000000x` times faster on 31 bit. You need 64bit but there the speed up should be even better due much lower complexity — Spektre, Oct 03 '19 at 08:24
Possible duplicate of [Fibonacci Sequence Mod 1000000007](https://stackoverflow.com/questions/26441995/fibonacci-sequence-mod-1000000007) — Sneftel, Oct 03 '19 at 08:40

Spektre · Accepted Answer · 2019-10-03T10:25:35.210

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 ...

By the same property that you used in the first few lines, all those algorithms can be run in modular arithmetic. — conditionalMethod, Oct 02 '19 at 17:56
@conditionalMethod You're right the matrix modpow is returning correct values but the controlling counter must not be done on modular arithmetics !!! otherwise it would be corrupted (that was mine concern in the first place) — Spektre, Oct 03 '19 at 08:19
Why would anyone put the counter in modular arithmetic? The result needed is F_n mod m, not F_{n mod m} mod m. — conditionalMethod, Oct 03 '19 at 13:57
@conditionalMethod yes for this method but many recursive fast algorithms are using the actual value (not just parameter n)... and after mod it is no longer possible to use those ... as I did not remember the fast algos I was not sure if it was the case or not ... after re-implementing it its not so its usable... — Spektre, Oct 03 '19 at 14:21

WJS · Answer 2 · 2019-10-03T01:20:55.280

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

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.
I also added a map to store the fibFirst fibonacci with it's modulus.
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.
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.

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

2 Answers2