扩展欧几里得算法

hbghlyj

在标准的欧几里得算法中，我们记欲求最大公约数的两个数为$ a,b $，第$ i $步带余除法得到的商为$ q_{i} $，余数为$ r_{i+1} $，则欧几里得算法可以写成如下形式：
\begin{aligned}r_{0}&=a\\r_{1}&=b\\&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}\quad {\text{且}}\quad 0\leq r_{i+1}<|r_{i}|\\&\,\,\,\vdots \end{aligned}当某步得到的$ r_{i+1}=0 $时，计算结束。上一步得到的$ r_{i} $即为$ a,b $的最大公约数。

扩展欧几里得算法，常用于求 $ax+by=\gcd(a,b)$ 的一组可行解。
扩展欧几里得算法在$ q_{i} $，$ r_{i} $的基础上增加了两组序列，记作$ s_{i} $和$ t_{i} $，并令$ s_{0}=1 $，$ s_{1}=0 $，$ t_{0}=0 $，$ t_{1}=1 $，在欧几里得算法每步计算$ r_{i+1}=r_{i-1}-q_{i}r_{i} $之外额外计算$ s_{i+1}=s_{i-1}-q_{i}s_{i} $和$ t_{i+1}=t_{i-1}-q_{i}t_{i} $，亦即：
\begin{aligned}r_{0}&=a&r_{1}&=b\\s_{0}&=1&s_{1}&=0\\t_{0}&=0&t_{1}&=1\\&\,\,\,\vdots &&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}&{\text{且}}0&\leq r_{i+1}<|r_{i}|\\s_{i+1}&=s_{i-1}-q_{i}s_{i}\\t_{i+1}&=t_{i-1}-q_{i}t_{i}\\&\,\,\,\vdots \end{aligned}算法结束条件与欧几里得算法一致，也是$ r_{i+1}=0 $，此时所得的$ s_{i} $和$ t_{i} $即满足等式$ \gcd(a,b)=r_{i}=as_{i}+bt_{i} $。

oi-wiki.org/math/number-theory/gcd/#扩展欧几里得算法
沈淵源，數論輕鬆遊，數學傳播第二十九卷第四期（116），94 年12 月，第45 ∼ 71 頁。網頁版
扩展欧几里得算法 - 维基百科

Euclidean algorithm需要回代,所以需要存储每次的商和余数.
extended Euclidean algorithm只循环一次,不用存储每次的商和余数了.

Init $r_0=a,r_1=b,s_0=1,s_1=0,t_0=0,t_1=1$
Loop while $r_i\ne0$
$r_{i+1}=r_{i-1}-q_ir_i,s_{i+1}=s_{i-1}-q_is_i,t_{i+1}=t_{i-1}-q_it_i$
$as_i+bt_i=r_i$ for all iterations

Proof.
For $i=0$ and $i=1$, $a=a$, $b=b$.
Proof by induction, check for $i+1$:
\begin{aligned}r_{i+1}&=r_{i-1}-q_ir_i\\
&=as_{i-1}+bt_{i-1}-q_i(as_i+bt_i)\\
&=(as_{i-1}-aq_is_i)+(bt_{i-1}-bq_it_i)\\
&=a(s_{i-1}-q_is_i)+b(t_{i-1}-q_it_i)\\
&=as_{i+1}+bt_{i+1}\end{aligned}

hbghlyj

https://www.geeksforgeeks.org/time-complexity-of-euclidean-algorithm/

1. unsigned gcd_recursive(unsigned a, unsigned b)
2. {
3. if (b)
4. return gcd_recursive(b, a % b);
5. else
6. return a;
7. }

复制代码

Let’s assume, the number of steps required to reduce b to 0 using this algorithm is N.

gcd(a, b) ⟶ N steps

Now, if the Euclidean Algorithm for two numbers a and b reduces in N steps then, a should be at least f(N + 2) and b should be at least f(N + 1).

gcd(a, b) ⟶ N steps
Then, a ≥ f(N + 2) and b ≥ f(N + 1)
where, fN is the Nth term in the Fibonacci series(0, 1, 1, 2, 3, …) and N ≥ 0.

hbghlyj

Stein's Algorithm for finding GCD
Algorithm to find GCD using Stein’s algorithm gcd(a, b)

• If both $a$ and $b$ are 0, gcd is zero: $\gcd(0, 0) = 0$.
• $\gcd(a, 0) = a$ and $\gcd(0, b) = b$ because everything divides 0.
• If $a$ and $b$ are both even, $\gcd(a, b) = 2 \gcd(\frac{a}2,\frac{b}2)$ because 2 is a common divisor.
• If $a$ is even and $b$ is odd, $\gcd(a, b) = \gcd(\frac{a}2, b)$ because 2 is not a common divisor.
  Similarly, if $a$ is odd and $b$ is even, then $\gcd(a, b) = \gcd(a,\frac{b}2)$.
• If both $a$ and $b$ are odd, then $\gcd(a, b) = \gcd(a-b, b)= \gcd(\frac{a-b}2, b)$. Note that difference of two odd numbers is even.
• Repeat steps 3–5 until $a = b$, or until $a = 0$. In either case, the GCD is $2^k \cdot b$, where $2^k$ is 2 raised to the power of $k$ and $k$ is the number of common factors of 2 found in step 3.
  

hbghlyj

GCD: Euclid vs. Stein on the JVM



Steins algorithm can be significantly faster than the Euclidean Algorithm for calculating the GCD