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, $0 \leq n \leq 2147483647$ and $0 \leq m \leq 20$ . We are then asked to calculate and output the $n$ th Fibonacci number, modulo $2^m$ .
As you can see, $n$ can be pretty big. Let’s have a look at a few different methods to compute the $n$ 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 $n$ 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 $\log{n}$ time?

Matrix Exponentiation

          There is another way to calculate the $n$ 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:

$\displaystyle \left( \begin{array}{cc} \text{fib}_{n 2} & \text{fib}_{n 1} \\ \text{fib}_{n 1} & \text{fib}_n \end{array} \right)=\left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)\times \left( \begin{array}{cc} \text{fib}_{n 1} & \text{fib}_n \\ \text{fib}_n & \text{fib}_{n-1} \end{array} \right)$

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 $n$ times, we get:

Or equivalently:

$\displaystyle \left( \begin{array}{cc} \text{fib}_{n 1} & \text{fib}_n \\ \text{fib}_n & \text{fib}_{n-1} \end{array} \right)=\left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)^n$

Now we just have to find a fast way to raise a matrix to the $n$ th power.
Let’s assume we’re trying to raise a number $x$ to the $n$ th power (where $n \in \mathbb{Z}$ , meaning that it is an integer). One way would be to multiply $x$ with itself $n$ times. This is pretty slow and needs $n$ multiplications.
A faster algorithm can be derived with the following identity in mind.

$\displaystyle x^n= \begin{cases} 1, & \mbox{if } n = 0 \\ x \cdot x^{n - 1}, & \mbox{if } n \mbox{ is odd} \\ \left( x^{\frac{n}{2}} \right)^2, & \mbox{if } n \mbox{ is even} \end{cases}$

The key thing is to notice that we use $x^{n/2}$ twice, but we only need to calculate it once.
Here is a function that calculates $x^n$ using our fast algorithm:

Here is a function that calculates $x^n$ using our fast algorithm:

public static int pow(int x, int n) {

    // our base case: x^0 = 1

    if (n == 0)

        return 1;

    // if n is odd

    if (n % 2 != 0)

        return x * pow(x, n - 1);

    // if n is even, calculate x^(n / 2)

    int sqrt = pow(x, n / 2);

    // and return it squared

    return sqrt * sqrt;

}

This algorithm, often known as exponentiation by squaring, also works for matrix exponentiation. The only change is that when $n = 0$ , we return the identity matrix instead of $1$ .
I’ve included a small matrix library in the complete source code (below). There, the exponentiation method looks like:

// raise the matrix to the n-th power

public Matrix pow(int n) {

    if (n == 0) {

        // if n is 0, we return the identity matrix

        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) {

        // if n is even, return the square root, squared

        Matrix res = pow(n / 2);

        return res.multiply(res);

    } else {

        // if n is even, return the matrix multiplied by the matrix to the (n - 1)th power

        return multiply(pow(n - 1));

    }

}

This algorithm only uses about $\log{n}$ multiplications. Isn’t this the running time we were trying to achieve?

Implementation

Now we can calculate the $n$ th Fibonacci number, in a fast way, using matrix exponentiation. The main code now looks like:

public void run(Scanner in, PrintWriter out) {

    // initialize the matrix to:

    // [ 1  1 ]

    // [ 1  0 ]

    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);

    // loop through each test case

    while (in.hasNextInt()) {

        // read n and m

        int n = in.nextInt(),

            m = in.nextInt();

        // calculate fib^n

        Matrix fib2 = fib.pow(n);

        // output the n-th Fibonacci number

        out.println(fib2.get(1, 0));

    }

}

But there is still one thing we have yet to do. The problem asks us to output the $n$ th Fibonacci number, modulo $2^m$ . We can easily modify our code to do that. We just need to do every computation modulo $2^m$ . 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 $2147483647$ th Fibonacci number (modulo $2^{20}$ ) in less than 100 milliseconds. That’s pretty good, considering that the $2147483647$ th Fibonacci number has $448797540$ 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

Solution For LightOJ

বৃহস্পতিবার, ১৩ সেপ্টেম্বর, ২০১২

Solution Of Light Online Judge : 1065 - Number Sequence

Interpretation

Matrix Exponentiation

Implementation

CODE

Conclusion

কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন