菲波那契数列的快速幂矩阵求法

菲波那契数列的快速幂矩阵求法

先看整数的快速幂运算 正常情况下，假如你要计算X11， 则需要X11 = X * X * X * X * X * X * X * X * X * X * X

而快速幂运算则可以省去一些重复的过程 先将指数化成二进制形式。

11D = 1011B

X11 = X1 * X2 * X8

int res = 1; // 结果int m = x; // 输入int n; // 指数while(指数不等于0){ if(当前n的最低位为1){ 将当前res与当前x的指数阶相乘 } m *= m; // 对当前m进行平方处理,当x为2时,m 的取值为 x^2,x^4,x^8,x^16.... n右移一位，直到n等于0;}循环结束后输出res的值

​​完整代码​​

public class Test { public static void main(String[] args) { int res = f(2, 11); System.out.println(res); } public static int f(int x, int n){ int res = 1; while (n != 0){ if ((n & 1) == 1){ res = res * x; } x *= x; // 当x = 2, 此步 => x^2,x^4,x^8,x^16.... n = n >> 1; // 右移，相当于除二 } return res; }}

斐波那契矩阵求法是基于等式：

[ F(n) F(n - 1) ] = [1 1] * [ 1 1 ] (n - 2)

[ 0 0 ] [0 0] [ 1 0 ]

菲波那契数列的快速幂矩阵求法与整数的快速幂运算过程大体相似。

public class Test { public static void main(String[] args) { System.out.println(mPow(30)); } // 返回矩阵M*N的结果 public static int[][] mult(int[][] M, int[][] N){ int [][] R = new int[2][2]; R[0][0] = M[0][0] * N[0][0] + M[0][1] * N[1][0]; R[0][1] = M[0][0] * N[0][1] + M[0][1] * N[1][1]; R[1][0] = M[1][0] * N[0][0] + M[1][1] * N[1][0]; R[1][1] = M[1][0] * N[0][1] + M[1][1] * N[1][1]; return R; } public static int mPow(int n){ int[][] res = {{1,1},{0,0}}; int[][] m = {{1,1},{1,0}}; n = n - 2; while (n != 0){ if ((n & 1) == 1){ res = mult(res, m); } m = mult(m, m); n = n >> 1; // 右移，相当于除二 } return res[0][0]; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。