Nooblhu - 8 months ago 108

Java 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()`

In

`fibComplex()`

`n % (lengthofPisaniPeriod)`

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

The dynamic method you're using isnt 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 here