In
problem 1065 at
Light Online Judge, Modular Fibonacci, our task is to calculate huge Fibonacci numbers, modulo some given integer.
Interpretation
We are given two integers,
and
. We are then asked to calculate and output the
th Fibonacci number, modulo
.
As you can see,
can be pretty big. Let’s have a look at a few different methods to compute the
th Fibonacci number.
The naive method, where we do two recursive calls without any
optimizations, runs in exponential time. Computing the largest allowed
Fibonacci number with this method would take ages, literally.
The dynamic programming method, where we save each computed value (or
at least the last two), runs in linear time. We only need a few seconds
to compute the largest allowed Fibonacci number using this method, but
that’s still too slow. We need to be able to run all test cases in under 2 seconds.
There is no specified maximum amount of test cases, but
they could be as many as ten, or even hundred, and all of them could
possibly be the maximum value.
There is also a
closed-form formula for calculating the
th
Fibonacci number, which of course runs in constant time. But it assumes
that we are using Real numbers (with infinite precision), which we do
not have access to in computers, and thus we cannot use it here.
So what have we learned? A linear-time algorithm is too slow, so we
need something faster. A constant-time algorithm would be nice, but
seems to be a bit optimistic. We are definitely looking for something
there in between, maybe something that takes
time?
Matrix Exponentiation
There is another way to calculate the
th Fibonacci number, that is, using matrix exponentiation.
If you don’t know much about matrices, now would be a good time to head over to Khan Academy and take a peek at videos about
linear algebra (specifically “Introduction to matrices” and “Matrix multiplication”).
The Fibonacci numbers have the following matrix identity:
Now if we put the first Fibonacci numbers into the right-most matrix,
and instead of multiplying it once with the other matrix, we multiply
it
times, we get:
Or equivalently:
Now we just have to find a fast way to raise a matrix to the
th power.
Let’s assume we’re trying to raise a number
to the
th power (where
, meaning that it is an integer). One way would be to multiply
with itself
times. This is pretty slow and needs
multiplications.
A faster algorithm can be derived with the following identity in mind.
The key thing is to notice that we use
twice, but we only need to calculate it once.
Here is a function that calculates
using our fast algorithm:
Here is a function that calculates
using our fast algorithm:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public static int pow(int x, int n) {
if (n == 0)
return 1;
if (n % 2 != 0)
return x * pow(x, n - 1);
int sqrt = pow(x, n / 2);
return sqrt * sqrt;
}
|
This algorithm, often known as
exponentiation by squaring, also works for matrix exponentiation. The only change is that when
, we return the
identity matrix instead of
.
I’ve included a small matrix library in the complete source code (below). There, the exponentiation method looks like:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public Matrix pow(int n) {
if (n == 0) {
Matrix res = new Matrix(getRows(), getCols());
for (int i = 0; i < getRows() && i < getCols(); i++)
res.set(i, i, 1);
return res;
} else if (n % 2 == 0) {
Matrix res = pow(n / 2);
return res.multiply(res);
} else {
return multiply(pow(n - 1));
}
}
|
This algorithm only uses about
multiplications. Isn’t this the running time we were trying to achieve?
Implementation
Now we can calculate the
th Fibonacci number, in a fast way, using matrix exponentiation. The main code now looks like:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
public void run(Scanner in, PrintWriter out) {
Matrix fib = new Matrix(2, 2);
fib.set(0, 0, 1);
fib.set(0, 1, 1);
fib.set(1, 0, 1);
fib.set(1, 1, 0);
while (in.hasNextInt()) {
int n = in.nextInt(),
m = in.nextInt();
Matrix fib2 = fib.pow(n);
out.println(fib2.get(1, 0));
}
}
|
But there is still one thing we have yet to do. The problem asks us to output the
th Fibonacci number, modulo
. We can easily modify our code to do that. We just need to do every computation modulo
. Look inside the complete source for details.
CODE
| #include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
class MAT
{
public:
long int a,b,c,d;
}temp,req,cal,base;
int Mod;
MAT& multiply(MAT &A,MAT &B)
{
temp.a = A.a*B.a+A.b*B.c;
temp.a=temp.a%Mod;
temp.b = A.a*B.b+A.b*B.d;
temp.b=temp.b%Mod;
temp.c = A.c*B.a+A.d*B.c;
temp.c=temp.c%Mod;
temp.d = A.c*B.b+A.d*B.d;
temp.d=temp.d%Mod;
return temp;
}
void POW(int n)
{
if(n==1)
{
req = cal;
}
else if(n%2)
{
POW(n-1);
req = multiply(cal,req);
}
else
{
POW(n/2);
req = multiply(req,req);
}
}
int main()
{
int m,i1,test,a1,b1;
long long int N;
cin>>test;
for(i1=1;i1<=test;i1++)
{
cin>>a1>>b1>>N>>m;
Mod=int(pow(10,m));
cal.a=1,cal.b=1,cal.c=1,cal.d=0;
base.a=a1+b1,base.b=b1,base.c=b1,base.d=a1;
if(N==0)
{
printf("Case %d: %d\n",i1,a1);
}
else if(N==1)
{
printf("Case %d: %d\n",i1,b1);
}
else if(N==2)
{
printf("Case %d: %d\n",i1,a1+b1);
}
else
{
POW(N-1);
req = multiply(req,base);
printf("Case %d: %ld\n",i1,req.b);
}
}
return 0;
}
We were ask |
Conclusion
We were asked to calculate huge Fibonacci numbers, and we figured out
a fast way to do it with matrix exponentiation. Our algorithm is very
fast, calculating the
th Fibonacci number (modulo
) in less than 100 milliseconds. That’s pretty good, considering that the
th Fibonacci number has
digits.
So what do you think? Did/would you solve it differently? Leave a comment and let me know.
Test Case :
Sample Input
6
2 1 11 3
2 1 0 3
0 1 11 3
0 1 42 4
0 1 22 4
0 1 21 4
Sample Output
Case 1: 199
Case 2: 2
Case 3: 89
Case 4: 4296
Case 5: 7711
Case 6: 946
