俄国农民指数算法

方法一：正向快速幂

1
2
3
4
5
6
7
8
9
10
11
12
long long FastPow(long long g,long long e,const long long m) //求g的e次方模m的值
{
    long long ans=1;
        while(e)
        {
        if(e&1)
        ans=(ans*g)%m;
        g=(g*g)%m;
        e>>=1;
        }
    return ans;
}

方法二：逆向快速幂

1
2
3
4
5
6
7
8
9
10
11
12
long long FastPow(long long g,long long e,const long long m) //求g的e次方模m的值
{
    long long ans=1;
        while(e)  //e采用反向存储
        {
        ans=(ans*ans)%m;
        if(e&1)
        ans=(ans*g)%m;
        e>>=1;
        }
    return ans;
}

相同点

两种算法都需要平均1.5∗(n −1) 次乘法。

不同点

第二种是用固定的g值作乘法，第一种的g值是变化的，因此在硬件实现时，需要增加一个寄存器。

第一种算法中，平方和模乘是独立的，可以并行运算。但在第二种算法中不能。

俄国农民乘法算法

1
2
3
4
5
6
7
8
9
10
11
int f(int a,int b){  //当a是2的倍数时，加上b的2次幂；否则不加
    int ans=b;
    while(a!=0){
    b=b*2;
    if(a%2==0){
    ans+=b;
    }
    a=a/2;
    }
return ans;
}

笔纸算法

1
2
3
4
5
6
7
8
9
10
11
multiply(u, v) //快速计算uv；
Input: 正整数 u、 v, in binary
Output: uv
n = max(size of u, size of v)
if n = 1  return xy
U1=u的高n/2位， U0 =  u的低 n/2 位
V1 =v的高n/2位, V0= v的低 n/2 位
P1 = multiply(U1, V1)
P2 = multiply(U0 , V0)
P3 = multiply(U1-U0, V0-V1)
return =(2^n+2^n/2)P1+2^n/2*P2+(2^n/2+1)P3

复数乘法

1
2
3
4
5
复数乘法(a+bi)*(c+di): //四次乘法改三次乘法
A=a*d
B=b*c
C=(a+b)*(c-d)
(a+bi)*(c+di)=(C-A+B)+(A+B)i