How do I translate an while loop to clojure code

Question

For example, the extended euclidean algorithm (quoted from wiki):

function extended_gcd(a, b)
    x := 0    lastx := 1
    y := 1    lasty := 0
    while b ≠ 0
        quotient := a div b
        (a, b) := (b, a mod b)
        (x, lastx) := (lastx - quotient*x, x)
        (y, lasty) := (lasty - quotient*y, y)       
    return (lastx, lasty)

which I tried and got:

 (defn extended-gcd 
  [a b]
  (loop [a a b b x 0 y 1 lx 1 ly 0]
     (if (zero? b)
      [lx ly]
      (recur b (mod a b)
             (- lx (* (int (/ a b)) x))
             (- ly (* (int (/ a b)) y))
             x y))))

I guess I could find a way to translate loops that deal with sequence. But how about this one? How do I write it in clojure way? something with map, reduce, etc. rather than loop recur.

tolitius · Accepted Answer · 2013-08-28 13:38:13Z

5

For the extended Euclidean algorithm you can use a simple recursion, which makes a function look quite elegant:

(defn extended-gcd [a b]
  (if (zero? b) [1 0]
    (let [[q r] [(quot a b) (rem a b)]
          [s t] (extended-gcd b r)] 
      [t (- s (* q t))])))

Let's try it:

user=> (extended-gcd 120 23)
[-9 47]

Not all problems need to be solved by using map/reduce/sequence. I would argue that the above is just as Clojure way as a "(reduce + [1 2 3 4 5])" type of an answer you are looking for.

edited Aug 28, 2013 at 13:38

answered Aug 28, 2013 at 12:55

tolitius

22.6k6 gold badges73 silver badges82 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Rimwolf · Accepted Answer · 2013-08-29 14:26:56Z

0

For this kind of problem iterate is often a good alternative to using loop. In this case it leads to a fairly transparent translation of the source algorithm:

(defn extended-gcd [a b]
  (->> {:a a, :b b, :x 0, :y 1, :lx 1, :ly 0}
    (iterate 
      (fn [{keys [a b x y lx ly]}]
        (let [q (quot a b)]
          {:a b, :b (mod a b), :x (- lx (* q x)), :lx x, :y (- ly (* q y)), :ly y})))
    (drop-while #(not= 0 (:b %)))
    first
    ((juxt :lx :ly))))

That said, using loop is a Clojure way too -- admonitions to avoid it, I believe, are meant to encourage use of higher-level constructs where they're more appropriate.

answered Aug 29, 2013 at 14:26

Rimwolf

12 bronze badges

Collectives™ on Stack Overflow

How do I translate an while loop to clojure code

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related