快速幂

布满荆棘的人生 2022-11-30 05:42 146阅读 0赞

### 快速幂 ###

*  问题引入
 *  快速幂
 *   *  为什么要用快速幂？
     *  什么是快速幂？
     *  快速幂的实现
 *  再谈快速幂
 *   *  还能再快吗？
 *  后记

# 问题引入 #

--------------------

在对循环的学习是，老师们通常会要求学生编写一个程序用于求取一个数的n次幂。  
实现也很简单，不过就一遍遍地乘底数以此来得到结果嘛。

long long ans = 1;
        for (long long  i = 0;i < power; i++){
        
            ans = ans * base % mod;
        }

**这里为了保证数据不会溢出，本文章的求幂过程将在模意义下进行。**

![在这里插入图片描述][20200823221952929.jpg_pic_center]

看到上面的结果，对于求取2的10次方，我们用时为8微秒，但如果指数更大呢？

![在这里插入图片描述][20200823221904495.jpg_pic_center]

**357955微秒！这已经是可以明显感觉到的时间了，如果指数更大，用时将会更加可怕！**

# 快速幂 #

--------------------

## 为什么要用快速幂？ ##

在现实使用时，我们常常要面对很大的数据，如果这时候还在用普通的循环，那我们将会浪费大量时间，这将是致命的。  
对于普通的运用循环的方式来求幂的算法来说，其时间复杂度为O(N)，在很大的数据下，这个效率仍然不能满足我们的需要，那么我们能不能换一个更高效的算法来求解问题呢？  
**当然可以！** 这就是这篇文章要介绍的算法： **快速幂！**

## 什么是快速幂？ ##

**举个例子:**

2 10 = 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 2^\{10\} = 2\\times2\\times2\\times2\\times2\\times2\\times2\\times2\\times2\\times2 210=2×2×2×2×2×2×2×2×2×2

如此操作，我们要进行9次乘法。  
根据小学二年级学过的乘法结合律进行一下变换看看：  
 2 10 = ( 2 × 2 ) × ( 2 × 2 ) × ( 2 × 2 ) × ( 2 × 2 ) × ( 2 × 2 ) ＝ 4 × 4 × 4 × 4 × 4 2^\{10\} = (2\\times2)\\times(2\\times2)\\times(2\\times2)\\times(2\\times2)\\times(2\\times2)＝4\\times4\\times4\\times4\\times4 210=(2×2)×(2×2)×(2×2)×(2×2)×(2×2)＝4×4×4×4×4

如此一来，我们只用进行5次乘法，相比于原来的9次乘法来说，已经减少了将近一半了。  
接下来，继续变换：  
 2 10 = 4 × 4 × 4 × 4 × 4 = 16 × 16 × 4 = 256 × 4 = 1024 2^\{10\}=4\\times4\\times4\\times4\\times4=16\\times16\\times4=256\\times4=1024 210=4×4×4×4×4=16×16×4=256×4=1024

可以看到，通过不断的变换底数的方式，我们从9次乘法，一步步简化到了只需要4次乘法（包括了每次变换底数时的一次乘法）就可以求得2的10次方。  
现在，把这个变换过程整理一下：  
 2 10 = 2 2 5 = 2 2 2 2 × 2 2 = 2 8 × 2 2 2^\{10\}=2^\{2^\{5\}\}=2^\{2^\{2^\{2\}\}\}\\times2^2=2^8\\times2^2 210=225=2222×22=28×22

在这个过程中，我们将2的10次方拆分成了2的8次方与2的2次方的乘积的形式。

**咦，8次方，2次方，10的2进制表示是1010啊，两个1对应的位置刚好是8和2，这是巧合吗？**  
这当然不是巧合，而是必然。

因为任何数都可以通过二进制表示，所以任何一个数都可以通过多个2的整数次方相加表示。这句话看似一句废话，但正是这句话，才有了快速幂算法。

## 快速幂的实现 ##

通过上面的例子，我们可以看出，当我们把指数通过多个2的整数次方相加的方式来表示时，可以大幅减少乘法的次数。

**因此，我们最重要的一件事，就是实现对指数的拆分工作。**

这样，我们可以先不断对底数进行乘方操作，同时将指数减半，当指数是奇数时，把当前的底数乘给当前结果，如果是指数偶数不乘便是了。

根据这个逻辑，我们可以轻易写出核心代码：

long long quickPow(long long base, long long power, long long mod){
        
    	long long ans = 1;
        while (power > 0){
        
            if (power % 2 == 1){
        
                ans = (ans * base) % mod;
            }
    
            power /= 2;
            base = (base * base) % mod;
        }
        return ans % mod;
    }

现在我们来对比一下快速幂与循环求幂的运行效率：  
![在这里插入图片描述][20200823231632699.jpg_pic_center]  
可以看出，快速幂算法的效率比循环求幂的方式快了一大截！

# 再谈快速幂 #

--------------------

## 还能再快吗？ ##

对于当前的快速幂来说，我们的时间效率已经很高了，但是还能更快吗？  
当然可以再快！

现在再看一下我们的快速幂代码，在判断当前指数是否为奇数时使用的取模的方式来判断奇偶，在将指数减半的时候使用的除法运算，这将是我们将效率再一次提高的突破点。

**位运算：**  
对于一个奇数，其二进制最后一位一定为“1”，也就是说，我们只用关心这个数在计算机中存储时的最后一位，至于前面是什么，我们不需要关心。

因此在快速幂运算中我们可以：

*  通过位运算中的“&”运算符来判断当前指数是否为奇数；
    
     *  比如4&1为false，而5&1为true。
 *  通过“>>”（右移）的方式来抛弃掉最后一位（即将原数字减半），将原倒数第二位作为最后一位。
    
     *  比如4的二进制为100，右移一位后变为10，即十进制下的2；5的二进制为101，右移一位后变为10，即十进制下的2。

这样我们可以得到极限效率下的快速幂：

long long quickPow(long long base, long long power, long long mod){
        
        long long ans = 1;
        while (power > 0){
        
            if (power & 1){
        
                ans = (ans * base) % mod;
            }
    
            power >>= 1;
            base = (base * base) % mod;
        }
        return ans % mod;
    }

我们再来测试一下时间效率：  
![在这里插入图片描述][20200823233436987.jpg_pic_center]  
可以发现，相对于原来的快速幂算法，我们又进一步节省下了7微秒的时间！

# 后记 #

*  关于模意义，有： ( a × b ) % p = ( a % p × b % p ) % p (a\\times b) \\% p = (a\\%p\\times b\\%p)\\%p (a×b)%p=(a%p×b%p)%p因此不断地对底数、指数、当前的结果进行取模，并不会使得这样操作后的结果与整体算完再取模的结果不同。
 *  快速幂算法的时间效率为O(logN)，在数据很小的情况下，快速幂的效率其实是低于循环求幂的，但是由于数据很小，也慢不到那里去。毕竟快速幂算法生来是为了解决较大规模的数据的问题的。
 *  在追求最极致效率的情况下，可以不在模意义下进行，但这样无法保证数据的有效性（毕竟可能会溢出）。

[20200823221952929.jpg_pic_center]: /images/20221124/9751fbd416404994945d0ee3c0e6c1bf.png
[20200823221904495.jpg_pic_center]: /images/20221124/761e69a0291e47c2867ee105aa3d11aa.png
[20200823231632699.jpg_pic_center]: /images/20221124/752d31c92d404009af5d0a17d0f1df7d.png
[20200823233436987.jpg_pic_center]: /images/20221124/1de13f00eee44ab3b09c3bdd7c42f3f6.png