Implementing a Fibonacci Matrix algorithm in Java

Question

I need to use BigInteger to print out the nth number of the Fibonacci sequence, using matrix multiplication and repeated squaring. My instructor recommended that we use an object instead of arrays, but I'm having trouble following the instructions in his example. This is what I have so far.

import java.math.BigInteger;

public class Fibonacci {
    public static void logarithmicEfficiency(int n) {
        MatrixObject fmA = new MatrixObject();
        System.out.println(MatrixObject.matrixPower(fmA, n).getTopRight());
    }

    public static void main(String[] args) {
        logarithmicEfficiency(10);
    }
}

public class MatrixObject {
    public static MatrixObject matrixMultiply(MatrixObject fmA) {
        MatrixObject fmB = new MatrixObject();

        fmB.setTopLeft((fmA.getTopLeft().multiply(fmB.getTopLeft())).add(fmA.getTopRight().multiply(fmB.getBottomLeft())));
        fmB.setTopRight((fmA.getTopLeft().multiply(fmB.getTopRight())).add(fmA.getTopRight().multiply(fmB.getBottomRight())));
        fmB.setBottomLeft((fmA.getBottomLeft().multiply(fmB.getTopLeft())).add(fmA.getBottomRight().multiply(fmB.getTopRight())));
        fmB.setBottomRight((fmA.getBottomLeft().multiply(fmB.getTopRight())).add(fmA.getBottomRight().multiply(fmB.getBottomRight())));

        return fmB;
    }

    public static MatrixObject matrixPower(MatrixObject fmA, int n) {
        MatrixObject fmB = new MatrixObject();
        for (int i = 2; i < n; i++){
            fmA = matrixMultiply(fmB);
        }

        return fmA;
    }

    private BigInteger topLeft = new BigInteger("0");
    private BigInteger topRight = new BigInteger("1");
    private BigInteger bottomLeft = new BigInteger("1");
    private BigInteger bottomRight = new BigInteger("1");

    //Getters and Setters

When I run the program, it just outputs 1, but I'm not sure where it's going wrong. Can I get a nudge in the right direction?

Answer 1

I think I figured out part of the problem. In my matrixPower method, I was supposed to just take the object I passed in and set it equal to matrixMultiply(fmA) in the for loop, instead of making a new object. Removing fmB from that method is now returning the correct number to my main call. Much to my surprise, since I thought my solution was further off.

Edit: The rest of the problem was that I wasn't using repeated squaring.

public static BigInteger matrixPower(MatrixObject fmA, double k) {
        if (k % 2 == 0) {
            return matrixPower(matrixMultiply(fmA), k / 2);
        } else {
            return fmA.getTopLeft();
        }
    }

The above is simplistic, since we only needed to check for powers of 2 for our assignment, but the program now runs as swiftly as it should even with bigger values.

There was also a small error in my matrix multiplication formula. One of the lines was multiplying by the wrong value. After cleaning everything up, I was able to remove fmB from the class entirely.

Oddly enough, the way I had my matrix multiplication set up worked just fine even though it was reading and overwriting values at the same time. I changed it to store the values in variables first, anyway, just to be safe.

public static MatrixObject matrixMultiply(MatrixObject fmA) {

        BigInteger a = (fmA.getTopLeft().multiply(fmA.getTopLeft())).add(fmA.getTopRight().multiply(fmA.getBottomLeft()));
        BigInteger b = (fmA.getTopLeft().multiply(fmA.getTopRight())).add(fmA.getTopRight().multiply(fmA.getBottomRight()));
        BigInteger c = (fmA.getBottomLeft().multiply(fmA.getTopLeft())).add(fmA.getBottomRight().multiply(fmA.getBottomLeft()));
        BigInteger d = (fmA.getBottomLeft().multiply(fmA.getTopRight())).add(fmA.getBottomRight().multiply(fmA.getBottomRight()));

        fmA.topLeft = a;
        fmA.topRight = b;
        fmA.bottomLeft = c;
        fmA.bottomRight = d;

        return fmA;
    }