计算 2x2 矩阵幂的最快方法
quickest way to calculate powers of 2x2 matrix
我有一个 2x2 矩阵 M，它通常很复杂。将 M 乘以自身 n 次的最快方法是什么，即 M^n？我可以想到两种方法：
一个。将其对角化并相乘
乙。将 n 分组。例如，如果 n=15，那么我可以执行以下操作：
- A=M*M
- B=A*A=M^4
- C=B*B=A^8
- MAB*C=M^15
所以我总共需要做 6 次矩阵乘法。
我的问题是：
哪种方法更快？
还有其他方法吗？
我的第二种方法，如何实现任意n的算法？如果 n 是 2 的幂，这很容易，但是当它不是像我给出的示例中那样分解乘法和分组时？
- 我认为 A 更好，因为在 A 中，对角化矩阵后它是 O(1)，而在 B 中复杂度是 O(log(n))
2.Beside 微不足道的（将矩阵本身乘以 n 次），我不知道。
- 你应该将n表示为二进制数，并且只乘以“1”的位置。例如：15=1111 (bin) 所以你有：2^0,2^1,2^2,2^3，因此你需要将以上所有内容相乘才能得到答案。让我们再取一个 n，比如 n=23。
二进制表示是 10111，所以你需要直到 5 的幂 (2^0,2^1,2^2,2^3,2^4) - 你只取“1”的位置 - 所以你乘以2^0*2^1*2^2*2^4（因为第4个索引，指的是2^3是0你不相乘）。
我有一个 2x2 矩阵 M，它通常很复杂。将 M 乘以自身 n 次的最快方法是什么，即 M^n？我可以想到两种方法：
一个。将其对角化并相乘
乙。将 n 分组。例如，如果 n=15，那么我可以执行以下操作：
- A=M*M
- B=A*A=M^4
- C=B*B=A^8
- MAB*C=M^15
所以我总共需要做 6 次矩阵乘法。
我的问题是：
哪种方法更快？
还有其他方法吗？
我的第二种方法，如何实现任意
n的算法？如果n是 2 的幂，这很容易，但是当它不是像我给出的示例中那样分解乘法和分组时？
- 我认为 A 更好，因为在 A 中，对角化矩阵后它是 O(1)，而在 B 中复杂度是 O(log(n))
2.Beside 微不足道的（将矩阵本身乘以 n 次），我不知道。
- 你应该将n表示为二进制数，并且只乘以“1”的位置。例如：15=1111 (bin) 所以你有：2^0,2^1,2^2,2^3，因此你需要将以上所有内容相乘才能得到答案。让我们再取一个 n，比如 n=23。 二进制表示是 10111，所以你需要直到 5 的幂 (2^0,2^1,2^2,2^3,2^4) - 你只取“1”的位置 - 所以你乘以2^0*2^1*2^2*2^4（因为第4个索引，指的是2^3是0你不相乘）。