13

I was given the assignment to compare a pair of 3 positive double variables, while ignoring their order, in Java. I did the following:

if ((a1 == a2 && b1 == b2 && c1 == c2) ||
    (a1 == a2 && b1 == c2 && c1 == b2) ||
    (a1 == b2 && b1 == a2 && c1 == c2) ||
    (a1 == b2 && b1 == c2 && c1 == a2) ||
    (a1 == c2 && b1 == a2 && c1 == b2) ||
    (a1 == c2 && b1 == b2 && c1 == a2))
    // if true

I've heard from the teacher that there is a mathematical way of comparing this pair of 3 numbers.

So far, I've tried to compare their addition, subtraction, the sum of their power by 2 but I always found a case where the pair were different and the statement was true.

Any ideas?

EDIT:

I already sent the assignment and the teacher said that my answer was true. I'm asking out of curiosity.

AceVentuRa
  • 133
  • 7
  • I'm voting to close this question I think answering this question is aiding the poster in cheating. If the teacher says there's an answer, surely he or she will reveal it in time. It's not are place to interfere – ControlAltDel Nov 18 '19 at 21:15
  • 1
    @ControlAltDel It's not cheating because I've already sent the assignment... I'm asking out of curiosity – AceVentuRa Nov 18 '19 at 21:16
  • 2
    Since when do we not help folks with their homework? – WJS Nov 18 '19 at 21:19
  • Can you add those cases __where the pair were different and the statement was true__? – Eritrean Nov 18 '19 at 21:21
  • 2
    @ControlAltDel It's not off-topic because the OP clearly indicates what code they tried and what their difficulty is in solving it. There's no categorical ban on questions on homework. See point #3 in the [on-topic guide](https://stackoverflow.com/help/on-topic). – EJoshuaS - Stand with Ukraine Nov 18 '19 at 21:28
  • @Eritrean e.g. 4*1*5 == 10*2*1 (true but not equal), 4+1+5 == 6+2+2 (same), and the comparison of the sum of the power by 2 of 3 double numbers is not accurate for cases where there are maximum digits after the dot – AceVentuRa Nov 18 '19 at 21:28
  • @xerx593 you are right! The full assignment is to compare the lengths of 2 triangles to see if they all match. I'm asking about this specific case – AceVentuRa Nov 18 '19 at 21:33
  • Maybe the margin was too small for the teacher to write the solution. – WJS Nov 18 '19 at 21:46
  • @WJS Lol she said it's something not too complicated and when I've told her about my sum of the power of 2 comparisons she said it was close but not it because it's not valid for doubles :( – AceVentuRa Nov 18 '19 at 21:49
  • @AceVentuRa I wasn't suggesting it, I was responding to a deleted comment. – WJS Nov 18 '19 at 21:50

2 Answers2

11

TL;DR

Compare the sum of each triplet, the product of each triplet, and the sum of the products of all possible combinations of each triplet.

The Nitty Gritty

By the Fundamental Theorem of Algebra, for a polynomial of degree N, we must have N roots.

Using this fact we let our zeros be a1, a2, and a3. Now, we find the coefficients of this polynomial.

(x - a1) * (x - a2) * (x - a3)
(x^2 - (a1 + a2) * x + a1a2) * (x - a3) 
x^3 - (a1 + a2) * x^2 + (a1a2) * x - a3 * x^2 + (a1a3 + a2a3) * x - a1a2a3

x^3 + (-1 * (a1 + a2 + a3)) * x^2 + (a1a2 + a1a3 + a2a3) * x + (-1 * a1a2a3)

If two polynomials are equivalent, they must have the same roots (again by the FTA). Thus all we need to do is compare the coefficients of the generated polynomials.

So, if,

(-1 * (a1 + a2 + a3) == (-1 * (b1 + b2 + b3))
      ---equivalently---
a1 + a2 + a3 == b1 + b2 + b3

And

(a1a2 + a1a3 + a2a3) == (b1b2 + b1b3 + b2b3)

And

-1 * a1a2a3 == -1 * b1b2b3
      ---equivalently---
a1a2a3 == b1b2b3

Then we can conclude the triplets a1, a2, a3 and b1, b2, b3 are equivalent.

Is it worth it?

From a practical standpoint, let's see if this is indeed more efficient than brute force checking as illustrated by the OP.

First check: Sum and Compare. This requires 4 total additions and 1 check for equality.

Check total = 5; Running total = 5

Second check: Product, Sum, and Compare. This requires 6 total multiplications, 4 total additions, and 1 check for equality.

Check total = 11; Running total = 16

Third check: Product and Compare. This requires 4 total multiplications and 1 check for equality.

Check total = 5; Running total = 21

Adding the two logical AND operations, the total number of binary operations for the "coefficients of the generated polynomial approach" only requires:

23 binary operations

The brute force check requires 18 total equality checks, 12 logical AND comparisons, and 5 logical OR comparisons for a total of:

35 binary operations

So, strictly speaking, the answer is yes, the "coefficients of the generated polynomial approach" is indeed more efficient. However, as @WJS points out, the brute force approach has many more opportunities for short circuiting and thus execute as/more efficiently than the mathematical approach.

For Complete Thoroughness

We cannot skip checking the sum of the products of all possible combinations of each triplet. If we leave this out, there are countless examples where this fails. Consider (23, 32, 45) and (24, 30, 46)*:

23 + 32 + 45 = 100
24 + 30 + 46 = 100

23 * 32 * 45 = 33120
24 * 30 * 46 = 33120

They are not equivalent but give the same sum and product. They don't however give the same sum of the products of all possible combinations:

23 * 32 + 23 * 45 + 32 * 45 = 3211
24 * 30 + 24 * 46 + 30 * 46 = 3204

*In case one is curious how to derive an example similar to the one above, first generate all integer partitions of an integer M of length 3, take their product, find the duplicates, and pick a pair.

Joseph Wood
  • 7,077
  • 2
  • 30
  • 65
  • 1
    I wish we could use LaTeX – Joseph Wood Nov 18 '19 at 23:08
  • 1
    But in your FTA method, all the tests must be done. In the brute force approach, some of the comparisons will be short circuited. So it isn't as bad as it seems. – WJS Nov 18 '19 at 23:57
  • 2
    @WJS, agreed. You can say the same thing about the this approach just not to the degree you can with the brute force approach. In fact, I bet that the brute force approach for the majority of cases would be as fast or faster because of the short circuiting. TBH, If I were to code this up, I would probably use the brute force approach as it is many times easier to understand. – Joseph Wood Nov 19 '19 at 00:01
-1

If you're allowed to sort (a1 <= b1 <= c1 and a2 <= b2 <= c2) then try comparing 2^a1*3^b1*5^c1 with 2^a2*3^b2*5^c2 (using prime numbers 2, 3, 5 as basis)

Bruno
  • 141
  • 9