time complexity: running time w.r.t. input size
算到bit级别
f(x)=O(g(x)) f(x)以g(x)为上界, 差个常数倍
f(x)=Omega(g(x)) f(x)以g(x)为下界, 查个常数倍
f(x)=Theta(g(x)) f(x)与g(x)同阶, 即g(x)限住了f(x)的上下界
Remark:
tildeO(关于n的函数)=O(关于n的函数本身×关于logn的函数)
家用PC可以跑2^60的input size
整数上的基本运算时间复杂度
input: a, b
input size: len(a)+len(b)
let n = max(len(a), len(b))
addition/subtraction
O(len(a)+len(b))
multiplication
O(len(a)*len(b))=O(n^2)
可以提高到O(nlogn)
division
a = bq + r
O(len(除数)*len(商))=O(n^2)
gcd
property: gcd(a,b)=min{ abs(ax+by) : ax+by!=0 }
说的是最大公因子=bezout式子的最小绝对值
三种初等变换不改变gcd的值
设r0=a, r1=b, rk=gcd.
由k往前倒i次的值r_k-i>=fai^i, 这里fai=0.5*(1+根号五) ≈ 1.62
证明: induction on i.
往前倒0次, 就是gcd本身, 这个值大于等于1=fai^0
往前倒1次, r_k-1 > rk, 所以这个值>=2
假设往前倒2,3,...,i-1次都有这个不等式成立
倒i次 = 倒i-1次 商(i-1次)+倒i-2次>= 倒i-1次 + 倒i-2次>=fai(i-1)+fai(i-2)=fai^i
现在我们可以估计k是多少
因为r0=倒k次>=fai^k, 故可以推出有k<=log_fai(r0)=O(logr0)
ri=r_i+1*q_i+1+r_i+2这一步的复杂度是O(log^2 r0)
这样共作了k步, ∴O(log^3 r0)
实际上, 辗转相除法要更快
ri=ri+1qi+1+ri+2
复杂度=O(len(ri+1)len(qi+1))
注意到对于a=bq+r, 有len(商)<=len(被除数)-len(除数)+1
另外的方法:
a=2的次幂部分*奇数部分
b=2的次幂部分*奇数部分
除以2是数整体向右移位1
求a,b的gcd就变成求奇数部分的gcd
对于奇数, gcd(奇数,奇数)=gcd(奇数,奇数-奇数)-对于后面那个shift得到新的奇数->gcd(奇数, 奇数)
如此循环往复
粗略估计所需步数是O(奇数bit维数)
对于bezout等式, ax+by里的x和y可以用扩展的欧几里得算法求出/
Z_n上的基本运算时间复杂度
- a+b mod n
a, b在Z_n中取, 此时算a+b-n即可, 所以复杂度为O(模数的位数) - a-b mod n O(模数的位数)
- ab mod n O(模数位数的平方)
ab=nq+r, ab用时O(模数位数的平方), nq用时O(模数位数的平方) - a/b mod n O(模数位数的平方)
用扩展的欧几里得算法gcd(n,b)得到1/b mod n, 用时O(模数位数的平方), 再算模下的乘法, 也用时O(模数位数的平方) - power a^b mod n O(模数位数的平方*上标位数)
把b写成2进制的形式,
take a look at a simple example
a(系数23+系数2^2+系数2+系数)=
a系数*a(系数23+系数22+系数2)=
a系数*square(a(系数22+系数21+系数))
power n results in scaling the superscript by n
square results in doubling the superscript
Z中算乘法的加速
(re1+im1 I)*(re2+im2 I)
originally, we need performance 4 times multiplication
actually, we just perform 3 times multiplication
A=(re1+im1)(re2+im2)
B=re1re2
C=im1im2
(re1+im1 I)*(re2+im2 I)=(B-C)+(A-B-C)I
We can borrow this idea to calculate the mul in Z
assume len(a)=len(b)=2n,
a=高位1 2^(n) + 低位1
b=高位2 2^(n) + 低位2
ab=高位1高位2 2^(2n) + (高位1低位2+高位2低位1) 2^n +低位1低位2
A=(高位1+低位1)(高位2+低位2)
B=高位1高位2
C=低位1低位2
ab=B2^(2n) + (A-B-C)2^n + C
