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

通过使用方案，我构建了二进制GCD算法(又称斯坦因算法)的迭代实现，以计算数字u和v的最大公共(public)分母。此算法的步骤如下:

gcd(0，v)= v，因为一切都除零，并且v是除v的最大数。类似地，gcd(u，0)= u。通常不定义gcd(0，0)，但是将gcd(0，0)设置为0很方便。

如果u和v均为偶数，则gcd(u，v)= 2·gcd(u/2，v/2)，因为2是一个常见的除数。

如果u为偶数且v为奇数，则gcd(u，v)= gcd(u/2，v)，因为2不是一个常见的除数。同样，如果u为奇数，v为偶数，则gcd(u，v)= gcd(u，v/2)。

如果u和v均为奇数，且u≥v，则gcd(u，v)= gcd((u − v)/2，v)。如果两个都是奇数且u

重复步骤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, *]
有人可以解释为什么会这样以及如何解决吗？

谢谢!

最佳答案

两行中有一个错误:

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