在 Java 中实现斐波那契矩阵算法

Question

我需要使用 BigInteger 打印出斐波那契数列的第 n 个数，使用矩阵乘法和重复平方。我的导师建议我们使用对象而不是数组，但我无法按照他的示例中的说明进行操作。这是我目前所拥有的。

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

当我运行程序时，它只输出1，但我不确定它哪里出错了。我能得到正确方向的推动吗？

Answer 1

我想我解决了部分问题。在我的 matrixPower 方法中，我应该只获取传入的对象并在 for 循环中将其设置为等于 matrixMultiply(fmA)，而不是创建一个新对象。从该方法中删除 fmB 现在会将正确的数字返回给我的主调用。令我惊讶的是，因为我认为我的解决方案还差得远。

编辑：剩下的问题是我没有使用重复平方。

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

上面的内容很简单，因为我们只需要为我们的赋值检查 2 的幂，但程序现在运行得尽可能快，即使值更大也是如此。

我的矩阵乘法公式也有一点小错误。其中一行乘以错误的值。清理完所有内容后，我能够从 class 中完全删除 fmB。

奇怪的是，我设置矩阵乘法的方式工作得很好，即使它同时读取和覆盖值。无论如何，为了安全起见，我将其更改为首先将值存储在变量中。

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

在 Java 中实现斐波那契矩阵算法

Implementing a Fibonacci Matrix algorithm in Java

java

fibonacci

matrix-multiplication