芯有所想
精益求精
Extended Euclid Algorithm
扩展欧几里德算法用来计算在模a乘法域下b的倒数。 算法描述尽可能用利于数字设计的方式，而不是程序设计的角度。
a，b为两个互素的正整数，不妨设 a>b, 如果不满足此条件，则交换a、b顺序
方法1
初始化：
r(−1)=a;r(0)=bc(−1)=1;c(0)=0d(−1)=0;d(0)=1flag=1迭代过程：从 n=1 开始
flag=−flagq=r(n−2)/r(n−1)r(n)=r(n−2) mod r(n−1)c(n)=c(n−2)+q∗c(n−1)d(n)=d(n−2)+q∗d(n−1)x=flag∗c(n−1)y=−flag∗d(n−1)结束条件： r(n)==0
输出： r(n−1),x,y 输出满足条件：
gcd(a,b)=r(n−1)x(n−1)∗a+y(n−1)∗b=r(n−1)方法2
原始算法
初始化：x(−1)=1;y(−1)=0u(−1)=0;v(−1)=1r(−1)=b;r(−2)=a从0开始迭代：q=r(n−2)/r(n−1)r(n)=r(n−2) mod r(n−1)x(n)=u(n−1)y(n)=v(n−1)u(n)=x(n−1)−q∗u(n−1)v(n)=y(n−1)−q∗v(n−1)结束条件：r(n)==0输出：r(n−1),x(n),y(n)输出满足条件：gcd(a,b)=r(n−1)x(n)∗a+y(n)∗b=r(n−1)迭代算法改进：去掉 x,y
初始化：u[n],u[n+1]=1,0v[n],v[n+1]=0,1r[n],r[n+1]=a,bq=a/b迭代:u[n],u[n+1]=u[n+1],u[n]−q∗u[n+1]v[n],v[n+1]=v[n+1],v[n]−q∗v[n+1]r[n],r[n+1]=r[n+1],r[n] mod r[n+1]q=r[n]/r[n−1]结束条件：r[n+1]==0输出:r[n],u[n],v[n]输出满足条件：gcd(a,b)=r[n]u[n]∗a+v[n]∗b=r[n]方法2的结构图如下：
python源代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def ext_euclid(a, b):
if a < b:
a, b = b, a
# 初始化条件：
r_n2, r_n1 = a, b
u_n2, u_n1 = 1, 0
v_n2, v_n1 = 0, 1
while True:
# combinational calculcation
q = r_n2/r_n1
u_n = u_n2 - q*u_n1
v_n = v_n2 - q*v_n1
r_n = r_n2 % r_n1
if r_n == 0 : break
# update clocked data into DFF
r_n1, r_n2 = r_n, r_n1
u_n1, u_n2 = u_n, u_n1
v_n1, v_n2 = v_n, v_n1
return a, b, r_n1, u_n1, v_n1
Gitalking ...