快速幂模的两种实现

虽然这个算法已经滥大街了，但我们离散数学课里讲的al-kachi算法与常见的二进制幂略有不同, 所以写篇笔记记录一下。伪代码通俗易懂，但具体实现比较让人不爽。

这里把两种算法的代码都写出来，另外附加一个脑袋被驴踢了的SB代码。

ALGORITHM 1.

常见的快速幂模求解形如 Result = a^e mod b, 将e转化为2进制，然后按二进制位从右到左:

INPUT: a, e, b;
INIT: Res = 1, a = a mod b

LOOP (e IS NOT 0):             
    IF e % 2 == 1:
        Res = (Res * a) mod b
    END IF 

    a = a * a
    e = e / 2
ENDLOOP
    
OUTPUT: Res = a^e mod b

ALGORITHM 2.

我们老师说这叫Al-Kachi算法,同样将e转化为2进制,但按二进制位从左到右.

INPUT: a, e, b;
INIT: Res = 1, a = a mod b

LOOP (digit d in binary e, from left to right):
    IF d == 1:
        Res = Res * Res * a mod b
    ELSE:
        Res = Res * Res mod b
    ENDIF
ENDLOOP

OUTPUT: Res = a^e mod b

CODE:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96


#include <stdio.h>
#include <stdint.h>
#include <stddef.h>

int alkltr(int a, int e, int b);
int alkrtl(int a, int e, int b);

int main(){
    // To calculate : (a^e) mod b
    int a,b,e;
    while(1){
        scanf("%d %d %d",&a,&e,&b);
        printf("left to right: %d^%d mod %d = %d\n", a,e,b,alkltr(a,e,b));
        printf("right to left: %d^%d mod %d = %d\n", a,e,b,alkrtl(a,e,b));
    }
    return 0;
}

int alkrtl(int a, int e, int b){
    // 这是脑子正常的快速幂模
    // e&1 即取 e 二进制末位
    // e>>1 右移一位对应 e=e/2

    int res = 1;
    a %= b;

    while (e){
        if(e&1){
            res = (res * a) % b;
        }
        a = (a*a) %b;
        e = e >> 1;
    }
    printf("\n");
    return res;
}


int aikltr(int a, int e, int b){
    // 这是脑子不太正常的快速幂模
    int res = 1;
    a %= b;
    int len=0;

    int e2 = e;
    while(e2){
        len++;
        e2 = e2>>1;
    }

    while(len){
        len --;
        if((e&(1<<len))){
            res = ((res * res) *a) %b;
        }else{
            res = (res * res) %b;
        }
    }
    return res;
}


int alkltr_wtf( int a, int e, int b ){
    // 跟上面原理一样，但是脑子被驴踢了的快速幂模
    // (BUT IT WORKS)
    // 另外int的最高位为符号位,容易弄混

    size_t n = sizeof(int) * 8;
    int test = 1 << (n-2);
    // 假设int 为 8 bit，那么 test=0100 0000

    int res = 1;
    a %= b;

    int cal = 0;

    // 对齐e的二进制位
    while (!( (test&e) == test)){
        e = e<<1;
        cal ++;
    }

    int len = n-1-cal;
    // len 即为 e 的二进制位数
    res = 1;
    while (len){
        if( (e & test ) == test){
            res = ((res * res) *a) %b;
        }else{
            res = (res * res) %b;
        }
        e = e << 1;
        len --;
    }
    return res;
}