algorithm - 为什么 Josef Stein 的二进制 GCD 算法的这种实现只适用于某些情况？

Question

使用方案，我构建了二进制 GCD 算法（又名 Stein 算法）的迭代实现来计算数字的最大公分母u和v. 该算法的步骤如下：

1. gcd(0, v) = v，因为一切都除以零，而 v 是除 v 的最大数。类似地，gcd(u, 0) = u。gcd(0, 0) 通常没有定义，但设置 gcd(0, 0) = 0 很方便。
2. 如果 u 和 v 都是偶数，则 gcd(u, v) = 2·gcd(u/2, v/2)，因为 2 是公约数。
3. 如果 u 是偶数而 v 是奇数，则 gcd(u, v) = gcd(u/2, v)，因为 2 不是公约数。类似地，如果 u 是奇数而 v 是偶数，则 gcd(u, v) = gcd(u, v/2)。

4. 如果 u 和 v 都是奇数，并且 u ≥ v，则 gcd(u, v) = gcd((u − v)/2, v)。如果两者都是奇数且 u < v，则 gcd(u, v) = gcd((v − u)/2, u)。这些是简单欧几里得算法的一个步骤的组合，该算法在每一步都使用减法，以及上述步骤 3 的应用。除以 2 得到一个整数，因为两个奇数的差是偶数。

5. 重复步骤 2-4 直到 u = v，或（再走一步）直到 u = 0。在任何一种情况下，GCD 都是 2kv，其中 k 是在步骤 2 中找到的 2 的公因子数。

我做的算法是这样的：

(define (stein u v)
  (cond
    ((or (= u 0)(= u v))
      v)
    ((and (even? u) (even? v))
      (* 2 (stein (/ u 2)(/ v 2))))
    ((and (even? u) (odd? v))
      (stein (/ u 2) v))
    ((and (odd? u) (even? v))
      (stein u (/ v 2)))
    ((and (and (odd? u) (odd? v))(>= u v))
      (stein (/ 2 (- u v)) v))
    ((and (and (odd? u)(odd? v))(< u v))
      (stein (/ 2 (- v u)) u))))

我的问题是，每当我遇到一个数字是奇数而另一个数字是偶数的情况（输入是这种方式或过程最终以这种方式调用自身）时，输出要么是空白，要么返回错误：Error: *: number required, but got #<undef> [stein, stein, stein, *]

有人可以解释为什么会发生这种情况以及如何解决吗？

谢谢！

标签： algorithmrecursionruntime-errorschemelisp

Answer 1

两行有错误：

(stein (/ 2 (- u v)) v))

和

(stein (/ 2 (- v u)) u))))

您应该将差值除以 2，反之亦然。那是：

(stein (/ (- u v) 2) v))

和

(stein (/ (- v u) 2) u))))

最后，请注意，需要测试来检查第二个参数是否等于 0，否则在某些情况下函数会永远循环。

像这样的东西：

(define (stein u v)
  (cond
    ((or (= u 0)(= u v))
      v)
    ((= v 0) u)
    ((and (even? u) (even? v))
      (* 2 (stein (/ u 2)(/ v 2))))
    ((and (even? u) (odd? v))
      (stein (/ u 2) v))
    ((and (odd? u) (even? v))
      (stein u (/ v 2)))
    ((and (and (odd? u) (odd? v))(>= u v))
      (stein (/ (- u v) 2) v))
    ((and (and (odd? u)(odd? v))(< u v))
      (stein (/ (- v u) 2) u))))