My solution, posted in comments, to the following problem needs some explanation. First of all, the task is to take three numbers as arguments and return the sum of the squares of the two larger numbers. E.g. 3, 4, 5 -> 4*4 + 5*5. It is trivial of course to do it with two comparisons to determine the dominant integers. If you have sort(), min() or max() functions available, they save you invoking the “if-then-else” construct in your favorite programming language. It is IMHO more elegant without branching. However I thought that min() would still require using conditionals in its implementation. Or would it? Can you write a solution in a language close to the metal, like C, that will not have any conditional operators?

Let’s start with min() implementation. The standard way is (x<y)?x:y. I’d like to replace this conditional operator by some arithmetical ones. The reasoning is as follows: first, compute the average (x+y)/2. Now you just need to add half of the distance between x and y to the average to get the larger or subtract the same value to get the smaller number. And the distance between x and y is obviously abs(x-y). Therefore min(x,y) is simply (x+y-abs(x-y))/2.

Solving the exercise without branching is now very easy. Compute the sum of squares of all three numbers and subtract the square of the smallest one. Use min() defined above. The defines are just for readability, you can make a one-liner out of the code below.

 

#define m(x,y) (((x)+(y)-abs(x-y))/2)
#define S(x) ((x)*(x))

int f(int a, int b, int c) 
{
  return S(a)+S(b)+S(c)-S(m(a,m(b,c)));
}

 

Alternatively you can compute the maximal and median numbers of the three and return the sum of the squares of just those two. This is left as an exercise to the reader.

About these ads