1.20
下面用 % 表示過程 remainder，那么正則序的過程如下：
(gcd 206 40)
(if (= 40 0) 206 (gcd 40 (% 206 40)))
(gcd 40 (% 206 40))
(if (= (% 206 40) 0) ;<## 1> [6]
40
(gcd (% 206 40) (% 40 (% 206 40))
(gcd (% 206 40) (% 40 (% 206 40)))
(if (= (% 40 (% 206 40)) 0) ;<## 2> [4]
(% 206 40)
(gcd (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))))
(gcd (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))
(if (= (% (% 206 40) (% 40 (% 206 40))) 0) ;<## 4>[2]
(% 40 (% 206 40))
(gcd (% (% 206 40) (% 40 (% 206 40)))
(% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))))
(gcd (% (% 206 40) (% 40 (% 206 40)))
(% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))))
(if (= (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))) 0) ;<## 7>[0]
(% (% 206 40) (% 40 (% 206 40)))
(gcd ...)
(% (% 206 40) (% 40 (% 206 40))) ;<## 4>[2]
可以看出需要調(diào)用 remainder 共 1+2+4+7+4 = 18 次。
應(yīng)用序計算過程如下：
(gcd 206 40)
(if (= 40 0) 206 (gcd 40 (% 206 40))) ;<##>
(gcd 40 6)
(if (= 6 0) 40 (gcd 6 (% 40 6))) ;<##>
(gcd 6 4)
(if (= 4 0) 6 (gcd 4 (% 6 4))) ;<##>
(gcd 4 2)
(if (= 2 0) 4 (gcd 2 (% 4 2))) ;<##>
(gcd 2 0)
(if (= 0 0) 2 (gcd 0 (% 2 0)))
2
可以看出共需 4 次。