1

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.

elias
  • 15
Mouvre
  • 193
  • This is true because $$(2(a-b)+1)\text{ mod }2=\begin{cases}1&a\ge b\-1&a\lt b\end{cases}$$using the operator $\text{mod}$ in a computing sense. – Peter Foreman May 09 '19 at 06:45
  • @Peter Foreman It's true, but is there strict evidence? I mean, how could someone just come up with formula? – Mouvre May 09 '19 at 06:53
  • It's because $x\text{ mod 2}$ is positive for positive $x$ and negative for negative $x$ and obviously $2(a-b)\equiv0\text{ mod }2$. So what is left is just $\pm1$ depending on the sign of the original number (which depends on whether $a\gt b$). – Peter Foreman May 09 '19 at 06:57

3 Answers3

3

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

heropup
  • 135,869
1

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
elias
  • 15
0

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.

Mouvre
  • 193