21
$\begingroup$

A nice easy puzzle for the math lovers out there.

We're all familiar with the $\max$ function: $$\max \left( {x,y} \right) \triangleq \left\{ {\begin{array}{*{20}{l}} x&{{\text{if }}x \geq y} \\ y&{{\text{otherwise}}} \end{array}} \right.\,\,\,\forall\, x,y \in \mathbb{R}$$

Suppose we wish to implement this function using no conditional logic and only a basic set of operations:

  • multiplication, division, addition, and subtraction
  • real-valued numeric constants
  • the floor function, $\left\lfloor \cdot \right\rfloor$, which yields the greatest integer $\leq$ its argument (e.g. $\left\lfloor -1.5 \right\rfloor = -2$)

Question

Can you realize the $\max$ function for all real inputs using only these basic operations?

Improve this question
$\endgroup$
5
  • $\begingroup$ I understood everything you said except what do you mean 'realize the max function' $\endgroup$
    – CyanogenCX
    Jun 18, 2015 at 1:30
  • $\begingroup$ @CyanogenCX: I mean "Can you build the $\max$ function out of these more primitive functions?" The aim is to show how you can compute the maximum of $x$ and $y$ using only the set of operations listed. $\endgroup$
    – COTO
    Jun 18, 2015 at 1:34
  • $\begingroup$ Makes me wonder. is there a way to do this without the floor function? $\endgroup$
    – Ivo
    Jun 18, 2015 at 12:55
  • $\begingroup$ @IvoBeckers: You'd be limited to constructing rational functions (i.e. ratios of polynomials). I'm all but positive it wouldn't be possible to realize something as exotic as $\max$. If you (or any reader) figures out a way to do it, post it as an answer and I'll award it a 200 rep bounty out of being singularly impressed. ;) $\endgroup$
    – COTO
    Jun 18, 2015 at 15:01
  • $\begingroup$ @COTO it's easy to show mathematically $\max(x,y)$ is not a rational function, so it is indeed impossible without the floor. $\endgroup$
    – user63779
    May 5, 2020 at 14:28

2 Answers 2

Reset to default
27
$\begingroup$

The graph of $f(x):=x\cdot(1+x^2)^{-1}$ looks like:

enter image description here

This function satisfies $$ \big\lfloor f(x)\big\rfloor =\begin{cases}0:&x\geq 0,\\-1:&x<0. \end{cases} $$ Using this, we can check that the function $$ x-\left\lfloor\frac{x-y}{1+(x-y)^2}\right\rfloor(y-x)= x-\big\lfloor f(x-y)\big\rfloor(y-x) $$ takes the value $\max\{x,y\}$:

  • if $x\geq y$, then $\big\lfloor f(x-y)\big\rfloor =0$, so $x-\big\lfloor f(x-y)\big\rfloor(y-x)=x-0\cdot(y-x) =x$,

  • if $x<y$, then $\big\lfloor f(x-y)\big\rfloor =-1$, so $x-\big\lfloor f(x-y)\big\rfloor(y-x)=x-(-1)\cdot(y-x) =y$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ You got it. I used exactly the same $f\left( x\right)$ but your second step is simpler (I used $\left| x\right|$ as an intermediary). $\endgroup$
    – COTO
    Jun 18, 2015 at 2:29
  • $\begingroup$ Could you please explain the answer in a much simpler way? I can not understand this. Thank you. $\endgroup$
    – user41805
    Jun 18, 2015 at 9:49
  • 4
    $\begingroup$ LOL. I love it when people ( preferable with good mathematics background ) say "It is not hard to see..." Reminds me of the good old days at university. But no, for people with less mathematical background it is far less easy to see. It can't hurt to edit in one or two sentences... (But yes, I do see the solution.) $\endgroup$
    – BmyGuest
    Jun 18, 2015 at 11:38
  • 2
    $\begingroup$ @BmyGuest [How those without 'good' mathematical intuition see it] 1 + 1 = 2...From here, it's not hard to see how we get the answer x - floor[frac{x-y}{1+(x-y)^2}] * (y-x)= x - floor[ f(x-y)] * (y-x)... $\endgroup$
    – Mark N
    Jun 18, 2015 at 13:23
  • 1
    $\begingroup$ Sorry, I've acquired some bad habits through years of writing for other mathematicians. I added some more explanation. $\endgroup$
    – Julian Rosen
    Jun 18, 2015 at 14:39
7
$\begingroup$

I came up with this: $$ \frac{\big\lfloor\frac{x}{y}\big\rfloor\cdot x+\big\lfloor\frac{y}{x}\big\rfloor\cdot y}{\big\lfloor\frac{x}{y}\big\rfloor+\left\lfloor\frac{y}{x}\right\rfloor} $$ If $x$ is higher, then $\big\lfloor\frac{y}{x}\big\rfloor = 0$ and the fraction above equals $x$, same if $y$ is higher.

If $x=y$, then $\big\lfloor\frac{x}{y}\big\rfloor =\big\lfloor\frac{y}{x}\big\rfloor = 1$, and the fraction equals $\frac{x + y}{2}$, which is $\frac{2x}{2} = x$ (because $x = y$).

Improve this answer
$\endgroup$
3
  • 5
    $\begingroup$ Doesn't this fail if x or y are 0 because some of the fractions will be undefined? $\endgroup$
    – Beska
    Jun 18, 2015 at 13:44
  • 2
    $\begingroup$ It's a neat concept, but Beska is right: we run into division-by-zero problems in some instances. $\endgroup$
    – COTO
    Jun 18, 2015 at 14:52
  • $\begingroup$ True, I completely overlooked the division by zero problem that appears... back to the drawing board, I guess :) $\endgroup$
    – Sleku
    Jun 18, 2015 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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