Prove a formula that gives the maximum of two numbers and uses only integer operations.

Question

Recently I received a programming task: There are 2 numbers, you need to output the greatest, without using conditional and bit operators, without using branching and functions. Only integer operations are allowed. After some thought, I derived the formula: $$ \forall a,b \in\mathbb{Z}\mathop{\bullet} \max(a,b)= \frac{(a+b)+(a-b)\times\Big(\big(2\times(a-b)+1\big)\mod 2\Big)}{2}$$ i.e. it behaves as follows for any integers $a$ and $b$: $$ \max(a,b)=\left\{\begin{matrix}a,& a\gt b\\b,&a\lt b\\a,&a=b\end{matrix}\right.$$

My question is: how can we strictly proof it? I mean in this formula I replaced absolute value with an expression that uses only integer operations, but I'm not pretty sure about severity.

Answer 1

We can represent $$\left| n \right| = \sqrt{n^2}$$, which mean, that $$n((2n+1) mod 2) = \sqrt{n^2}$$, so $$(2n+1) mod 2 = 1$$, it's true by definition. And after that, we can represent expression $$\frac{\left|a - b\right| + \left|a+b\right|}{2}$$ without absolute values.

Answer 2

$$\max(a,b) = \frac{|a-b|+|a+b|}{2}.$$

Answer 3

If you were able to derive it, you know how to prove it.

First you just need to write more clearly your formulas.

And write the proof step by step, not massaging it, by stateing the departing formula at the top and the goal of the proof at the bottom of you page.

To fill At each step, you need to state which rule was used to rewrite the formula. Avoid to massage the formulas.

As Peter Foreman told you, the key resides in the $\Big(\big(2\times(a-b)+1\big)\mod 2\Big)$ part. To prove it, you have to analyze three cases $a<b,\ a>b$ and $a=b$.

The "proof" that you wrote above, comparing with $|n|=\sqrt{n^2}$, is not clear, it seems wrong. There is no clear connection form premises to conclusion.

You could try to analyze what is going on with the modulo operation. Isn't $\quad m\mod n=m-n\times (m\div n)$ with $m$ and $n$ integers?

You can start rewriting the formula in terms of the definition of modulus and arrive to 1,1,-1 for the $m>n$, $m=n$ and $m<n$ cases.

m>n:((2*(a-b)+1) mod 2)
    ...
    1
m=n:((2*(a-b)+1) mod 2)
    ...
    1
m<n:((2*(a-b)+1) mod 2)
    ...
    -1