为什么约瑟夫·斯坦的二进制GCD算法的这种实现只适用于某些情况？

Question

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

1. gcd（0，v）= 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/v/2）。

4. 如果u和v都是奇数，并且u≥V，则gcd（u，v）= gcd（（u -– v）/2，v）。如果两者都是奇怪的，u＆lt;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, *]

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

谢谢！

Answer 1

两个行中有一个错误：

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

和

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

您应该将差异除以2，而不是Viceversa。那就是：

(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))))