2
$\begingroup$

Given two integers $a$ and $b$ with the relation $a<=b$, and a third number $x$ between them $a<=x<=b$, find the number which is closest to $x$, either $a$ or $b$, without using comparisons.

The permitted integer operations are : additions, multiplications, subtractions, exponentiation and any operation in a field or ring (not division). The purpose is to avoid using comparison operators like $<$ or $>$, but if they can be implemented using only the permitted operations is fine.

Basically, the puzzle consist in designing a function that :

$f(x,a,b)=\begin{cases} b, abs(x-a)\geq abs(x-b)\\ a, abs(x-a)\lt abs(x-b) \end{cases}$

where $abs(x-a)$ is the absolute value of the $x-a$, namely the distance between $x$ and $a$.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ Just to be clear: x here is required to be an integer? (If not, then unless I'm missing something the thing plainly can't be done because all the operations we have are continuous and the one being asked for is not.) $\endgroup$
    – Gareth McCaughan ♦
    Jun 13, 2016 at 11:48
  • $\begingroup$ Another clarification request: Are we allowed constants? I'm guessing not because if we're allowed either 1 or -1 then we can implement division. $\endgroup$
    – Gareth McCaughan ♦
    Jun 13, 2016 at 11:52
  • $\begingroup$ Oh, one further question. Is the situation (1) that you know this is possible and are challenging us to do it, (2) that you know whether it is possible and are challenging us to figure that out, or (3) that you don't know whether it is possible and are looking to see what we can do? $\endgroup$
    – Gareth McCaughan ♦
    Jun 13, 2016 at 11:55
  • $\begingroup$ Yes, you are allowed any constants you find useful. $\endgroup$
    – guglielmo london
    Jun 13, 2016 at 11:55
  • $\begingroup$ OK, so you needn't have specified no division because $a/b=ab^{-1}$. $\endgroup$
    – Gareth McCaughan ♦
    Jun 13, 2016 at 11:56

3 Answers 3

Reset to default
2
$\begingroup$

This fixes LoD's division by zero bug:

Use $X(x)=(x-a)-(b-x)$, and $\operatorname{sign}(y)=\dfrac{y}{|y|+0^{|y|}}$.
$\operatorname{sign}(X)$ returns $-1$ if $x$ is closer to $a$, $+1$ if $x$ is closer to $b$ and $0$ if $x$ is equidistant from $a$ and $b$.
Then $f(x,a,b)=0.5\times ((1-\operatorname{sign}(X(x)))a+(1+\operatorname{sign}(X(x)))b)$, which returns $\dfrac{a+b}{2}$ if this is $x$, and $a$ or $b$ as required otherwise.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice improvement :) $\endgroup$
    – Fabich
    Jun 13, 2016 at 14:06
1
$\begingroup$

This works if exponentiation is allowed with any real number (this allows division)

We can take absolute value of $x$ with $\sqrt{x²}$
Now we want to know the sign of $X=(x-a)-(b-x)$
We can find the sign with the absolute value and a division : $sign(X)=\frac{X}{|X|}$
if $sign(X)=1$ then the closest is b, if $sign(X)=-1$ the closest is a.
Your function can be $f(x,a,b) = \frac{(1-sign(X))*a}{2} + \frac{(1+sign(X))*b}{2}$

Improve this answer
$\endgroup$
0
$\begingroup$

My solution is based on the fact that I can use = as comparison and abs as operation.
If this is not allowed I will delete my answer.

Since $a \leq x \leq b$ we need to compare somehow, without using < or > these positive numbers.

$x - a$ and $b-x$.
To make it easier let's make this notation.
$n = x- a$ and $m = b-x$.
now let's take into consideration the result of...
$ (n-m) - |n-m| $.
If this result is exactly 0 it means $n\geq m$ which means $x-a \geq b-x$ which means b is closer.

now to summarize, the function can have this format (pseudo code involved here)

$f(x, a, b) = ((x - a - b + x) - | x -a -b +x| == 0) ? b : a$

or

$f(x, a, b) = ((2*x - (a + b)) - |2*x - (a + b)| == 0) ? b : a$

Improve this answer
$\endgroup$

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.