俄国农民指数算法

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;
}

原理：

ans∗ans=gen−1en−2en−1...e2e1[0],如果e0=1,则再乘以g，否则不变。

相同点

两种算法都需要平均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&(a%2);
    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
12
13
void mul(int a[], int b[], int c[]) { //OI WIKI
  clear(c);
  for (int i = 0; i < LEN - 1; ++i) {
    // 这里直接计算结果中的从低到高第 i 位，且一并处理了进位
    // 第 i 次循环为 c[i] 加上了所有满足 p + q = i 的 a[p] 与 b[q] 的乘积之和
    // 这样做的效果和直接进行上图的运算最后求和是一样的，只是更加简短的一种实现方式
    for (int j = 0; j <= i; ++j) c[i] += a[j] * b[i - j];
    if (c[i] >= 10) {
      c[i + 1] += c[i] / 10;
      c[i] %= 10;
    }
  }
}

比笔纸算法更快的算法

用递归的方式优化乘法。

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

递归表达式：T(2n)≤3T(n)+cn
最终，算法复杂度约为n的1.5次方。

复数乘法

两个复数相乘时，减少乘法的次数为3次。

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