CODEWITHSUNDEEP
rubyclojure
user3166747
user3166747

Reputation: 284

Ruby and Clojure: same algorith (?) but different results

I'm trying to decompose the square of a number into a sum of squares: In Ruby:

    def decompose(n)
      def decompose_aux(nb, rac)
        return [] if (nb == 0)
        i, l = rac, nil
        while (i >= Math.sqrt(nb / 2.0).to_i + 1) do
            diff = nb - i * i
            rac = Math.sqrt(diff).to_i
            l = decompose_aux(diff, rac);
            if l != nil then 
                l  << i; return l
            end
            i -= 1
        end
        l
    end  

    l = decompose_aux(n * n, Math.sqrt(n * n - 1).to_i);
    if l then return l else return nil end 
end

In Clojure:

(defn decompAux [nb rac]
  (if (= 0 nb)
    ()
    (loop [i rac l nil]
      (let [diff (- nb (* i i)) rac (int (Math/sqrt diff)) l (decompAux diff rac)]
        (if (not= l nil) 
          (conj l i)
          (if (>= i 1)
            (recur (dec i) nil)
            nil))))))
(defn decompose [n]
  (let [l (decompAux (* n n) (- n 1))]
    (if l
      (reverse l)
      nil)))

In Ruby I get

decompose(7654321) --> [6, 10, 69, 3912, 7654320].

In Clojure:

(decompose 7654321) --> (1 1 2 3 11 69 3912 7654320)

The Clojure one is a tracing of the Ruby one but the results are different. Where is the default?

Upvotes: 3

Views: 158

Answers (1)

Michał Marczyk
Michał Marczyk

Reputation: 84361

The two algorithms are not actually the same.

The difference is that in Clojure you have a different loop condition (as pointed out by Tassilo Horn in the comments) and you check it at a different point in your computation. Consequently, the Clojure version can basically add as many 1s as necessary on to any candidate result which is not "complete" (that is, where the squares of the numbers add up to a number less than your target).

Actually this phenomenon is not limited to 1s – decompose_aux(8, 2) returns nil, whereas (decompAux 8 2) returns (2 2) – but the fact that you can always count down to the point where i is 1 means that decompAux is guaranteed to return an answer for any positive nb and rac inputs (an answer which might involve many 1s).

Here's a fairly direct translation of your Ruby to Clojure:

(defn decompose [n]
  (letfn [(decompose-aux [nb rac]
            (if (zero? nb)
              []
              (loop [i rac l nil]
                (if (>= i (inc (int (Math/sqrt (/ nb 2.0)))))
                  (let [diff (- nb (* i i))
                        rac  (int (Math/sqrt diff))
                        l    (decompose-aux diff rac)]
                    (if (some? l)
                      (conj l i)
                      (recur (dec i) l)))
                  l))))]       ; unnecessary line
    (decomp-aux (* n n) (int (Math/sqrt (dec (* n n)))))))

It matches the Ruby version on your example:

(decompose 7654321)
;= [6 10 69 3912 7654320]

Upvotes: 5

Related Questions