algorithm - 如何实现扩展欧几里得算法？

Question

我如何实现 Extended Euclidean algorithm ？这是我的第一次尝试:

(define ex-gcd a b 
 ; gcd(a,b) = a * x+ b * y 
 ; gcd(a,b)-> always will be 1
 output: (x.y) 
)

Answer 1

算法对here在维基百科中，你只需要调整它只返回 Bézout 系数，返回的 cons-cell 的 car 部分将是 x，并且cdr 将是 y:

(define (extended-gcd a b)
  (let loop ([s 0] [t 1] [r b]
             [old-s 1] [old-t 0] [old-r a])
    (if (zero? r)
        (cons old-s old-t)
        (let ((q (quotient old-r r)))
          (loop (- old-s (* q s))
                (- old-t (* q t))
                (- old-r (* q r))
                s t r)))))

使用Bézout's identity 很容易测试它，为 a 和 b 使用不同的值，并验证它是否像宣传的那样工作:

(define (test a b)
  (let* ((ans (extended-gcd a b))
         (x (car ans))
         (y (cdr ans)))
    (= (gcd a b) (+ (* a x) (* b y)))))

(test 384 256)
=> #t

请注意算法计算了其他值，通过更改您返回的内容您还可以获得以下内容:

Bézout coefficients:     old_s, old_t
Greatest common divisor: old_r
Quotients by the gcd:    t, s