当前位置: 动力学知识库 > 问答 > 编程问答 >

function - How do I implement Extended Euclidean algorithm?

问题描述:

How can I implement the Extended Euclidean algorithm? Here's my first attempt:

(define ex-gcd a b

; gcd(a,b) = a * x+ b * y

; gcd(a,b)-> always will be 1

output: (x.y)

)

网友答案:

The algorithm is right here in Wikipedia, you just have to adapt it to only return Bézout coefficients, the car part of the returned cons-cell will be x, and the cdr will be 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)))))

It's easy to test it using Bézout's identity, use different values for a and b and verify that it works as advertised:

(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

Notice that the algorithm calculated other values, by changing what you return you can also obtain the following:

Bézout coefficients:     old_s, old_t
Greatest common divisor: old_r
Quotients by the gcd:    t, s
分享给朋友:
您可能感兴趣的文章:
随机阅读: