快速幂取模算法证明及实现

2019-04-13 12:41发布生成海报

站内文章 / 模拟电子

11885 0

快速幂取模

快速幂取模就是使用更快的方式计算幂式的模，例如当

a

和

b

很大时，用传统的方法计算

a^{b} % c

会发生溢出，这时我们就需要使用快速幂取模算法。

传统算法计算 $a^{b} % c$

int ans = 1;
for(int i = 0; i < b; i++)
    ans = ans * a;
ans = ans % c;

这个算法不仅复杂度是

O (b)

，而且一旦

a

或者

b

的值过大，就会发生溢出。下面，我们来看一个新的算法：

基于 $a^{b} % c = (a % c)^{b} % c$ 的算法

我们来证明

a^{b} % c = (a % c)^{b} % c

设

a = k \times c + e

，带入上式得

(k \times c + e)^{b} % c = e^{b} % c = (a % c)^{b} % c

证毕。利用这个公式，我们可以改进刚才的算法

int ans = 1;
a = a % c;
for(int i = 0; i < b; i++)
    ans = ans * a;
ans = ans % c;

这个算法的时间复杂度仍然是

O (b)

，还是会在

b

很大的时候发生溢出。我们还需要继续改进算法。

继续改进

我们的最终算法依赖下面这两个公式：
1. 当

b

是偶数时，

a^{b} % c = ((a^{2})^{b / 2}) % c

2. 当

b

是奇数时，

a^{b} % c = ((a^{2})^{b / 2} \times a) % c

这两个公式是很容易证明的，我们不在赘述。根据这两个公式，我们有：
1. 当

b

是偶数时，

a^{b} % c = (a^{2})^{b / 2} % c = (a^{2} % c)^{b / 2} % c

2. 当

b

是奇数时，

a^{b} % c = ((a^{2})^{b / 2} \times a) % c = [(a^{2} % c)^{b / 2} % c \times (a % c)] % c

这样就可以写出快速幂取模的递归算法了

#include 

int PowerMod(int a, int b, int c){
    if(b == 1)
        return a % c;
    else{
        if(b % 2 == 0)
            return PowerMod(a * a % c, b / 2, c);
        else
            return PowerMod(a * a % c, b / 2, c) * (a % c) % c;
    }
}

int main()
{
    printf("%d
", PowerMod(2, 8, 3));
    return 0;
}

这时我们的算法不但不会溢出，而且时间复杂度也降到了

\log_{2} (b)

快速幂取模算法证明及实现

快速幂取模

传统算法计算 $a^{b} % c$

基于 $a^{b} % c = (a % c)^{b} % c$ 的算法

继续改进

Ta的文章更多 >>

热门文章

快速幂取模算法证明及实现

快速幂取模

传统算法计算ab%c" role="presentation">ab%cab%c

基于ab%c=(a%c)b%c" role="presentation">ab%c=(a%c)b%cab%c=(a%c)b%c的算法

继续改进

Ta的文章 更多 >>

热门文章

举报内容

检举类型

检举原因

检举说明(必填)

打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮

传统算法计算 $a^{b} % c$

基于 $a^{b} % c = (a % c)^{b} % c$ 的算法

Ta的文章更多 >>