Massive Algorithms: UVa 10229: Modular Fibonacci

UVa 10229: Modular Fibonacci | MathBlog
e 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 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$

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;

}

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

}

}

https://github.com/sfmunera/uva/blob/master/UVa10229_ModularFibonacci.java


	static long[][] multiply(long[][] A, long[][] B, long mod) {
	long[][] C = new long[2][2];
	for (int i = 0; i < 2; ++i)
	for (int j = 0; j < 2; ++j)
	for (int k = 0; k < 2; ++k)
	C[i][j] = (C[i][j] + ((A[i][k] % mod) * (B[k][j] % mod)) % mod) % mod;

	return C;
	}

	static long[][] fastPow(long[][] base, long exp, long mod) {
	if (exp < 0)
	return new long[][]{{0, 0}, {0, 0}};
	if (exp == 0)
	return new long[][]{{1, 0}, {0, 1}};
	if (exp == 1)
	return base;

	if (exp % 2 == 0) {
	long[][] tmp = fastPow(base, exp / 2, mod);
	return multiply(tmp, tmp, mod);
	} else {
	long[][] tmp = fastPow(base, (exp - 1) / 2, mod);
	return multiply(base, multiply(tmp, tmp, mod), mod);
	}
	}

	public static void main(String[] args) throws IOException {
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

	String line;
	while ((line = in.readLine()) != null) {
	line = line.trim();
	String[] parts = line.split("[ ]+");
	long N = Long.parseLong(parts[0]);
	int M = Integer.parseInt(parts[1]);

	long MOD = (1L << M);

	long[][] base = {{0L, 1L}, {1L, 1L}};
	long[][] pow = fastPow(base, N - 1, MOD);

	long res = pow[1][1];
	System.out.println(res);
	}

	in.close();
	System.exit(0);
	}

https://f0rth3r3c0rd.wordpress.com/2011/10/19/uva-10229-modular-fibonacci/

    public static int[][] multiply(int[][] a, int[][] b) {

        int[][] res = new int[a.length][a.length];

        for (int i = 0; i < a.length; i++)

            for (int j = 0; j < a.length; j++)

                for (int k = 0; k < a.length; k++)

                    res[i][j] = ((res[i][j] + ((a[i][k] & mod) * (b[k][j] & mod))) & mod);

        return res;

}

    public static int[][] matPow(int[][] mat, int pow) {

        int[][] res = new int[mat.length][mat.length];

        for (int i = 0; i < res.length; i++)

            res[i][i] = 1;

        while (pow > 0) {

            if (pow % 2 == 1)

                res = multiply(res, mat);

            mat = multiply(mat, mat);

            pow >>= 1;

}

        return res;

}

Read full article from UVa 10229: Modular Fibonacci | MathBlog

UVa 10229: Modular Fibonacci | MathBlog

Labels

Popular Posts