二分法的常见应用

时间:2022-12-23 22:12:04

1. 计算 an (数的幂)

2. 计算 An (矩阵的幂)

由于矩阵乘法具有结合律,因此
A4=AAAA=(AA)(AA)=A2A2
我们可以得到这样的结论:

  • 当n为偶数时, An=An/2An/2
  • 当n为奇数时, An=An/2An/2A (其中n/2取整)。

这就告诉我们,计算A^n也可以使用二分快速求幂的方法。例如,为了算出A^25的值,我们只需要递归地计算出A^12、A^6、A^3的值即可。

根据这里的一些结果,我们可以在计算过程中不断取模,避免高精度运算。