# UVa 10229: Modular Fibonacci

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

$\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)^n\times \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)$

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:

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.

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

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.

### Posted by Bjarki Ágúst

Sultan

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.

Bjarki Ágúst

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

Ami Ekhono Sopno Dekhi

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