2
\$\begingroup\$

I wrote a function in Clojure to solve quadratic equations using the quadratic formula

The function

(defn solvequadeq [a b c]
 (let [D (- (* b b) (* 4 a c))]
      (if (< D 0) #{}
        (let [sqrtD (Math/sqrt D)
              x1 (/ (+ (- b) sqrtD) (* 2 a))
              x2 (/ (- (- b) sqrtD) (* 2 a))]
              (set [x1 x2])))))

Unit tests

(defn assertFuzzyEquals [act exp]    ;; From codewars.com
  (do (println "asserting equality over " act exp)
  (let [inrange (<= (Math/abs (- act exp)) 1e-2)]
    (if (= inrange false)
      (println "abs(actual - expected) must be <= 1e-2. Expected was " exp " but got: " act))
    (is (= inrange true))))
)

(defn assertSetsFuzzyEqual [act exp]
  (and (is (= (count act) (count exp)))
  (doall (map assertFuzzyEquals (sort (vec act)) (sort (vec exp))))))   ; (1)


(deftest a-test5
  (testing "Solve quadratic equations"
          (assertSetsFuzzyEqual (solvequadeq 1 0 0) #{0})
          (assertSetsFuzzyEqual (solvequadeq 1 -6 9) #{3})
          (assertSetsFuzzyEqual (solvequadeq 1 -4 3) #{1 3})
          (assertSetsFuzzyEqual (solvequadeq 1 -4 14) #{})
))

N.B.: assertFuzzyEquals is borrowed from a task of codewars.com, all the rest is my code.

While any remark, and suggestion is welcome, I would be interested most particularly in the following questions:

  • Is using a set a good solution for avoiding having the same return value twice, if the two solutions are equal? (I am worrying that they might not be always exactly equal, due to imprecision in calculation.)
  • If not, than what would be a better approach, to elegantly handle the case of one vs two solutions?
  • Independently whether sets should be used for this particular problem or not, is there a better way to compare two sets for equality, with a custom function between the elements? (C.f., line (1))

EDIT: Clarification of this last point, as per the answer of Josh. The question is: what is the best practice, in Clojure, for checking the equality of two sets of floating point numbers?

Let's say, that we have a set with values #{1.0, 2.0}, and want to compare it against the set #{1, 2}.

Attempted solutions:

(= #{1.0, 2.0} #{1, 2})

; result false, since 1.0 != 1

(reduce #(and %1 %2) (map #(> 0.01 (Math/abs (- %1 %2))) #{1.0,2.0} #{2,1}))

; returns false, since ordering of elements in the set is not guaranteed

(reduce #(and %1 %2) (map #(> 0.01 (Math/abs (- %1 %2))) (sort (vec #{1.0,2.0})) (sort (vec #{2,1}))))

; returns true, because fixes the ordering, but is very complicated...

So, I am asking if there is a better way, to compare two sets, providing a custom function for equality checking (in this particular case, this custom function would be #(> 0.01 (Math/abs (- %1 %2)))).

I am thinking of something like this (pseudo-code only): (sets-equal #(> 0.01 (Math/abs (- %1 %2))) #{1.0,2.0} #{2,1}

\$\endgroup\$
1
\$\begingroup\$

Is using a set a good solution for avoiding having the same return value twice, if the two solutions are equal? (I am worrying that they might not be always exactly equal, due to imprecision in calculation.)

Instead of a set, IMO a vector would be a better structure. It is essentially a "list of solutions." Instead of your (set [x1 x2... simply wrap it in a vector:

(vec (hash-set x1 x2))

There's nothing wrong with using a set, but vectors are more common. Sets tend to be used more for utility in computation, rather than as a way to convey expression results. There are always exceptions, and you could very well make one here if you chose to do so.

Independently whether sets should be used for this particular problem or not, is there a better way to compare two sets for equality, with a custom function between the elements? (C.f., line (1))

I'm not the expert on floating-point comparisons, but I wonder if the following would work, or if it's too naive:

(def s1 #{1.0 2.0})
(def s2 #{1 2})
(= (set (map double s1)) (set (map double s2)))  ; true
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ thanks for your feedback. I have updated my original post to better clarify the third question. \$\endgroup\$ – Attilio Oct 11 '16 at 18:57
  • \$\begingroup\$ @Attilio added a comment on set equality, maybe it will work for you \$\endgroup\$ – Josh Oct 11 '16 at 19:44
  • \$\begingroup\$ thanks for the update. While it most certainly works for this concrete case, in general it is bad practice to compare floats directly for equality (see e.g. stackoverflow.com/questions/1088216/…), I would need something that checks the absolute difference of the two numbers. \$\endgroup\$ – Attilio Oct 11 '16 at 20:39
1
\$\begingroup\$

What if your solver return different number of roots but some are within your error range? For example:

Solution 1: [1.0   1.01  4.01]
Solution 2: [1.02        4.02]

If your error range is 0.05, then I would say these two solutions are equal. Given:

epsilon=0.05 => [[1.0 1.01 1.02] [4.01 4.02]]

And both solutions have root(s) in both range.

So all we need is a function to group your roots by their proximity:

(defn group-num
  "xs - list of solutions
  f - function to retrieve the root"
  [epsilon f & xs]
  (let [[m & r] (sort-by f xs)
        res     (reduce (fn [{:keys [m g ans] :as s} e]
                          (let [ev (f e)
                                mv (f m)]
                            (if (> epsilon (- ev mv))
                              (update s :g conj e)
                              (-> (update s :ans conj g)
                                  (assoc :m e)
                                  (assoc :g [e])))))
                        {:m   m
                         :g   [m]
                         :ans []}
                        r)]
    (conj (:ans res) (:g res))))

And using above example (k=1 is solution 1, k=2 is solution 2):

(group-num 0.05 :v {:k 1 :v 1} {:k 1 :v 1.01} {:k 1 :v 4.01} {:k 2 :v 1.02} {:k 2 :v 4.02})
=>
[[{:k 1, :v 1} {:k 1, :v 1.01} {:k 2, :v 1.02}]
[{:k 1, :v 4.01} {:k 2, :v 4.02}]]

The final thing is just to make sure your have samples from both solutions in each group.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the hint: your group-num function is very clever, although I admin I do not understand it 100%. One question: how could we have three roots for the quadratic equation. Or are you speaking about the generic case? \$\endgroup\$ – Attilio Oct 18 '16 at 17:21
  • \$\begingroup\$ Yes, that is more for higher order function. It also depends on the root finding algorithm. E.g. some approximation algorithm can return two roots (albeit very close) for a quadratic function while there is only one. \$\endgroup\$ – rmcv Oct 19 '16 at 16:13
0
\$\begingroup\$

In theory, the roots are the same if and only if D and hence sqrtD are zero. In practice, sqrtD might be so small compared with b that adding it to or subtracting it from b might make no difference.

I'd return two roots in any event, equal or not. So you want them in a vector or a list, not a set.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.