快速幂算法

本文为关于YouTube上的一个视频笔记。

https://www.youtube.com/watch?v=GbDtCFhq20A

油管主 五点七边

定义

快速幂，二进制取幂（Binary Exponentiation，也称平方法），是一个在 $\Theta(\log n)$ 的时间内计算 $a^n$ 的小技巧，而暴力的计算需要 $\Theta(n)$ 的时间。

源起

为何我们不能直接用 $a^n$ 来计算？

先看$5^4$

对于我们来说，$5^4$跟$25^2$算起来似乎并没有什么区别

只不过$5^4$需要进行四次乘法，而$25^2$只需要一次乘法。

但对计算机来讲，则是完全不同的概念。

先问下豆包

豆包：
CPU 进行乘法运算主要有以下几种方式：

    1. 移位相加法

    对于二进制数的乘法，比如计算A * B：

    把乘数 B 看成是由一系列的 0 和 1 组成。
    如果某一位是 1，就将被乘数 A 左移相应的位数，然后把所有这些左移后的结果相加起来。
    例如计算5 * 3，二进制表示为101 * 11。
    首先判断乘数最低位为 1，将被乘数 5（二进制 101）左移 0 位，结果仍为 101。
    接着判断乘数第二位为 1，将被乘数 5 左移 1 位得到 1010。
    再判断乘数第三位为 1，将被乘数 5 左移 2 位得到 10100。
    最后将这三个结果相加：101 + 1010 + 10100 = 11111，即十进制的 15，与 5 * 3 的结果一致。


    2. 加法器和移位寄存器组合

    现代 CPU 中通常有专门的加法器和移位寄存器来执行乘法运算。

    首先，将被乘数和乘数加载到特定的寄存器中。
    然后，通过一系列的移位和加法操作来实现乘法。例如，每次将被乘数左移一位，同时根据乘数相应位的值决定是否将移位后的被乘数与一个中间结果相加。
    这个过程不断重复，直到处理完乘数的所有位。


    3. 使用乘法器硬件电路

    复杂的 CPU 可能包含专门的乘法器硬件电路。这些乘法器通常由大量的逻辑门组成，可以快速地执行乘法运算。
    乘法器电路通过对被乘数和乘数的各位进行组合逻辑运算，产生乘积的各个位。
    不同的 CPU 架构可能有不同设计的乘法器电路，但基本原理都是基于二进制的乘法规则。


    4. 微指令和流水线技术

    CPU 执行乘法运算还可以通过微指令来控制。微指令是一种低级的指令，用于控制 CPU 的各个硬件单元。
    当执行乘法指令时，CPU 会根据微指令序列逐步执行乘法运算的各个步骤。
    同时，现代 CPU 通常采用流水线技术，将乘法运算分成多个阶段，每个阶段由不同的硬件单元执行。这样可以提高乘法运算的效率，使得在每个时钟周期都能有一定的运算进展。

注意到上面，可知计算机靠于移位运算来进行乘法运算，而移位运算的效率是非常低的。因此我们要尽量减少乘法运算的次数。因此快速幂算法很能提升效率