为什么约瑟夫·斯坦因的二进制GCD算法的这种实现仅在某些情况下有效？

Question

使用方案，我构建了二进制GCD算法（又称斯坦因算法）的迭代实现，以计算数字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, *]

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

谢谢！

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