UVa 10229: Modular Fibonacci

UVa 10229: Modular Fibonacci

Written by on 9 May 2012

Topics: UVa Online Judge

In problem 10229 at UVa 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 three 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:

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 , 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:

// 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 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:

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

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.

The blog image is of a flower displaying patterns that relate to Fibonacci numbers. It was captured by Brian Wolfe who shared it under the creative commons license.

You can take a look at the complete source code here.
So what do you think? Did/would you solve it differently? Leave a comment and let me know.

3 Comments For This Post I'd Love to Hear Yours!

  1. Sultan says:

    Thanks for this nice article . But my thinking to solve this problem is :


    This problem requires an O(log n) method to calculate an arbitrary Fibonacci number. The algorithm works off of the idea that you can do the following matrix multiplication (MATLAB notation):

    [F(n+1) F(n) ; F(n) F(n-1)] * [1 1 ; 1 0]

    …and you will get the next set of Fibonacci numbers. Thus, we can derive:

    F(2n) = F(n) * (F(n) + 2*F(n-1))
    F(2n-1) = F(n)^2 + F(n-1)^2

    …depending on whether the number is even or odd. We can use these formulas along with an algorithm that does O(log n) exponentiation to come up with the answer. Take mod m after every addition and multiplication to keep the numbers small, and use longs because you may need to square numbers as large as 2^20, and 2^40 won’t fit in an int.

  2. Bjarki Ágúst says:

    Glad you liked the article, and thank you for sharing with us how you solved it!

  3. Ami Ekhono Sopno Dekhi says:

    If f(0) = a and f(1) = b then what will the solution ?

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.