Почему эта реализация двоичного алгоритма GCD Джозефа Стейна работает только в определенных случаях?

Question

Используя схему, я построил итеративную реализацию двоичного алгоритма GCD (он же алгоритм Стейна) для вычисления наибольшего общего знаменателя чисел u и v.Шаги к этому алгоритму следующие:

1. gcd (0, v) = v, потому что все делит ноль, и v является наибольшим числом, которое делит v. Аналогично, gcd (u, 0)= ты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

5. Повторяйте шаги 2–4 до тех пор, пока u = v, или (еще один шаг) до тех пор, пока u = 0В любом случае GCD равен 2 кВ, где 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))))