9
$\begingroup$

Suppose two arbitrary integer numbers $a$ and $b$. I'm looking for some function $f(a,b)$ with the following properties:

  • $f(a,b)\in\mathbb{Z}$.
  • $f(a,a)=a$.
  • $f(a,b)=f(b,a)$.
  • $\min\{a,b\}< f(a,b)< \max\{a,b\}$, accepting "$\leq$" if $a$ and $b$ are consecutive ($a=b\pm 1$).

Any example of such a function?

Improvement: Any solution avoiding "floor/ceiling-like" functions?

$\endgroup$
  • 2
    $\begingroup$ What about $f(a,b)=\lfloor \frac{a+b}{2}\rfloor$? You know... the integer average :-) $\endgroup$ – Peter Košinár Dec 5 '14 at 23:55
  • $\begingroup$ The problem with the average function $f(x,y) = \dfrac {x+y}{2}$, is that sometimes your get an extra $\dfrac 12$. So you can round up or down to get an "integer average". These rounded functions would correspond to $f_{down}(x,y) = \left\lfloor \dfrac {x+y}{2} \right\rfloor$ & $f_{up}(x,y) = \left\lceil \dfrac {x+y}{2} \right\rceil$. You just need to choose the one that's most appropriate to what you're doing. $\endgroup$ – user137731 Dec 5 '14 at 23:58
  • $\begingroup$ Thanks for solutions! Any ideas avoiding floor/ceiling functions? $\endgroup$ – NessunDorma Dec 6 '14 at 0:25
  • 8
    $\begingroup$ I don't understand the resistance to floors and ceilings. We see that frequently. They are fine functions wen they do what you want. As Peter Košinár said, he just hid them. $\endgroup$ – Ross Millikan Dec 6 '14 at 2:20
  • 1
    $\begingroup$ @Henning Actually, this is irrelevant in the context of this question. Calculating floor of division (i.e. "integer quotient") is something that computers do without needing to invoke any floating-point arithmetics. Moreover, they are really happy about calculating $\lfloor \frac{x}{2}\rfloor$ since it corresponds to just shifting the number one bit to the right. $\endgroup$ – Peter Košinár Dec 7 '14 at 14:21
27
$\begingroup$

$$f(a,b)=\frac{a+b-\sin^2\left(\pi(a+b)/2\right)}{2}$$

Yes, it's just the floor function in disguise :-)

$\endgroup$
  • 4
    $\begingroup$ This makes me laugh for its cleverness! It also helped me see that floor/ceil functions don't add any more discontinuity than integers, really, already have. $\endgroup$ – david van brink Dec 7 '14 at 0:58
15
$\begingroup$

How about $f(a,b)=\lfloor \frac 12(a+b)\rfloor$?

$\endgroup$
14
$\begingroup$

\begin{equation} f(a,b) = \begin{cases} a & \text{ if } a=b \\ a+1 & \text{ if } a<b \\ b+1 & \text{ if } b<a \end{cases} \end{equation}

This does ignore the verbal connotation of “integer average”. Because nobody likes connotations.

$\endgroup$
13
$\begingroup$

Any solution avoiding "floor/ceiling-like" functions?

Maybe you were hoping for a polynomial? Sadly, that's impossible. If $f$ is a polynomial, then $g(a)=f(a,0)$ is also a polynomial. We need $|g(a)|\leq |a|$ for all $a$, so the degree of $g$ can't be greater than $1$. But if $g$ is linear and $g(0)=0$ and $g(2)=1$, then $g(1)=\frac12\not\in\mathbb Z$.

$\endgroup$
6
$\begingroup$

I would use "scientific rounding" (round to even) on the arithmetic mean. So if $(a+b)/2$ is an integer, use that, otherwise use the even integer out of $(a+b+1)/2$ and $(a+b-1)/2$. So that would likely be something like $$\left\lfloor a+b+1\over4\right\rfloor + \left\lceil a+b-1\over4\right\rceil$$ The advantage of this kind of rounding is that it is overall unbiased while preferredly rounding to points of greater stability, possibly reducing the amount of followup errors with repeated operations since averaging two values calculated using the "round to even" tie-breaking will have an exact result not needing another tie breaker.

$\endgroup$
6
$\begingroup$

How about

$$ \frac{a + b + ((a + b)\ \text{mod}\ 2)}{2} $$

This works because $a + b + ((a + b)\ \text{mod}\ 2)$ is guaranteed to be a multiple of 2. Note that you can also use $(a - b)\ \text{mod}\ 2$, if you prefer, with no change in behavior.

Both of the modulo expressions are more straight-forward descriptions (IMO) of what Peter was doing in his answer where he used $−sin^2(π(a+b)/2)$, except that he rounds down where I round up, and of course my solution remains completely in the integer domain. (I'm not familiar with any implementation of sine that is integer specific.)

A more complex answer avoiding floor and round that includes the concept of scientific rounding in user198082's answer is:

$$ \frac{a + b + ((a + b)\ \text{mod}\ 4)((a + b)\ \text{mod}\ 2) - 2((a + b)\ \text{mod}\ 2)}{2} $$

Examining the four cases:

  1. If a + b is a multiple of 4, this is just dividing their sum by 2, since all modulos are zero.
  2. If a + b is a multiple of 2, this is still just dividing their sum by 2, since modulo 2 we get zero and that is multiplied by the modulo 4 (which is 2).
  3. If a + b modulo 4 is 1 (e.g., a = 2, b = 3), then we want to round down to the even result (2), which happens because the product of the modulo 4 and modulo 2 test is just 1, and the product of 2 and the modulo 2 test is -2, resulting in a net of -1.
  4. If a + b modulo 4 is 3 (e.g., a = 1, b = 2), then we want to round up to the even result (again 2), which happens because the product of the module 4 and module 2 test is now 3, and the product of 2 and the modulo 2 test is still -2, resulting in a net of +1.
$\endgroup$
1
$\begingroup$

What you're looking for is the following:

(1) You want a binary operation on $\mathbb{Z}$. That is, you want a function $f: \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$. It's common to use multiplicative notation for any binary operation (even if the operation is not literally multiplication). Thus we could write $x * y = f(x,y)$.

(2) This operation should be idempotent: for all $a \in \mathbb{Z}$, we require $a * a = a$.

(3) This operation should be commutative: for all $a, b \in \mathbb{Z}$, we require $a *b = b*a$.

(4) This operation should satisfy $\textrm{min}\{ a, b \} < a * b < \textrm{max} \{a, b \}\ldots$except in the cases where it can't. For example, there is no integer $z$ that satisfies $6 < z < 7$, so you're forced to accept a value of either $6$ or $7$ for $(6 * 7)$. Similarly, you accept $a * a = a$ for all $a$, as in (2).

Condition (4) is a bit complicated. Things might get a little simpler if you're willing to RELAX condition (4) in favor of just always allowing non-strict inequalities. So, your question didn't ask about this, but you might be interested in what happens if we replace (4) with (4'):

(4') For all $a, b \in \mathbb{Z}$, we require $\textrm{min}\{ a, b \} \leq (a * b) \leq \textrm{max} \{a, b \}$.

Or equivalently:

(4'') If $a \leq b$, then $a \leq (a*b) \leq b$.

This allows for some new examples. To begin with, the operations $x * y = \textrm{min}(x, y)$ and $x * y = \textrm{max}(x, y)$ are obviously two functions that would satisfy properties (1-3) and (4''). Notice that $\textrm{min}$ and $\textrm{max}$ are the meet and join, respectively, of the partially ordered set $(\mathbb{Z}, \leq)$.

In general, we could replace $(\mathbb{Z}, \leq)$ with any lattice; the meet and join functions will always satisfy conditions (1-3). It should be clear that in any lattice, if $a \leq b$, then $\textrm{meet}(a, b) = a$ and $\textrm{join}(a, b) = b$. Therefore the meet and join operations in any lattice will always satisfy condition (4'') also.

http://en.wikipedia.org/wiki/Lattice_(order)

FYI, the meet and join will also always be associative. Notice that for example the arithmetic mean operation, $x*y = \frac{x+y}{2}$, does not have this property.

I understand that the $\textrm{min}$ and $\textrm{max}$ functions are not answers to your question; they do not satisfy your original condition (4). Still, I thought it was worth mentioning that $\textrm{min}$ and $\textrm{max}$ are sort of "degenerate averages", and that you can generalize this to any lattice (which includes any totally-ordered set).

$\endgroup$
0
$\begingroup$

How about:

$$ f(a,b) = min(a,b) + |sgn(b-a)| $$

Where $sgn$ is the sign function, returning $-1$, $0$ or $1$ in agreement with the sign of its argument?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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