gcd :: Integral a => a -> a -> a
gcd x y
    | mod x y ==0 = y
    | otherwise = gcd y (mod x y)

在离散数学上已经了解过，gcd的运行次数不超过 \( 2\log_2{(n+1)}\)，其中\(n\)是待求两数中的较小的那个数。拉梅定理也告诉我们,\( gcd(x,y) \)的运行次数，不超过\(x,y\)较小数\(n \)十进制位数的5倍。这都说明了gcd的时间复杂度是 \( O(\log(n)) \)的。

接下来给出其证明：

对于x,y的最大公约数\( \gcd(a,b) \)，不妨设\( a > b \)，
记\( r_0 = a, r_1 = b \)，则有：

\[ r_0 = q_1r_1+r_2 \\
r_1 = q_2r_2+r_3 \\
r_2 = q_3r_3+r_4 \\
… \\
r_{n-2} = q_{n-1}r_{n-1} +r_{n} \\
r_{n-1} = q_{n}r_{n}+0\\
\]

由除数和余数的关系知，\( r_{n-1} > r_{n} \)，即

\[ r_1 > r_2 > … > r_{n-1} > r_{n} \]

则 \[ q_i =\lfloor \frac{r_i}{r_{i+1} } \rfloor \geq 1\]

而最后的\( r_{n-1} = q_{n}r_{n}+0 \)要有\(r_{n-1}>r{n} \)，必有\( q_n >=2 \)。

可得

\[ r_0 \geq r_1+r_2 \\
r_1 \geq r_2+r_3\\
… \\
r_{n-2} \geq r_{n-1}+r_{n} \\
r_{n-1} \gt r_n \\
\]

这与Fibonacci数列非常相似。可以将\(r_i \)的初始条件与Fibonacci数列建立联系： \[ r_n \geq1 = F_2 \\ r_{n-1} \geq 2 =F_3\]

利用数学归纳法，推出：\[ \begin{align}
r_{n-k} &= q_{n-k+1}r_{n-k+1} + r_{n-k+2} \\
&\geq r_{n-k+1} + r_{n-k+2} \\
&\geq F_{k+1}+F{k}\\
&=F_{k+2}
\end{align}\]

从而在\( k=n-1 \)时，\(r_1 \geq F_{n+1} \)

由Fibonacci数的性质可知，\( F_{n+1} \geq \varphi^{n-1} \)，其中\(\varphi=\frac{\sqrt{5}+1}{2}\)是Fibonacci数列特征方程的大于1的根。

这样，就得到 \[ r_1 \geq \varphi^{n-1} \]

两边取常用对数，则得 \[ n-1 \leq \frac{\lg{r_1}}{\lg{\varphi}}\]

其中\( \lg{\varphi} \)是可以直接计算的，其值为 \( 0.208987640…\) ，所以
\[ n-1 \leq \frac{\lg{r_1}}{0.208987640} \lt 5 \lg{r_1} \lt 5 \lceil \lg{r_1} +1 \rceil \] 而 \( \lceil \lg{r_1} +1 \rceil \) 就是数\( r_1 \)的十进制位数

从而可得 \[ n \lt 5 \lceil \lg{r_1} +1 \rceil -1 \leq 5 \lceil \lg{r_1} +1 \rceil \]

故证毕。