CODEWITHSUNDEEP
matharithmetic-expressionsinteger-arithmetic
user2384183
user2384183

Reputation:

Implementing equality function with basic arithmetic operations

Given positive-integer inputs x and y, is there a mathematical formula that will return 1 if x==y and 0 otherwise? I am in the unfortunate position of having to use a tool that only allows me to use the following symbols: numerals 0-9; decimal point .; parentheses ( and ); and the four basic arithmetic operations +, -, /, and *.

Currently I am relying on the fact that the tool that evaluates division by zero to be zero. (I can't tell if this is a bug or a feature.) Because of this, I have been able to use ((x-y)/(y-x))+1. Obviously, this is ugly and unideal, especially in the case that it is a bug and they fix it in a future version.

Upvotes: 3

Views: 94

Answers (3)

rici
rici

Reputation: 241691

If division is truncating and the numbers are not too big, then:

((x - y) ^ 2 + 2) / ((x - y) ^ 2 + 1) - 1

The division has the value 2 if x = y and otherwise truncates to 1.

(Here x^2 is an abbreviation for x*x.)

This will fail if (x-y)^2 overflows. In that case, you need to independently check x/k = y/k and x%k = y%k where (k-1)*(k-1) doesn't overflow (which will work if k is ceil(sqrt(INT_MAX))). x%k can be computed as x-k*(x/k) and A&&B is simply A*B.

That will work for any x and y in the range [-k*k, k*k].

A slightly incorrect computation, using lots of intermediate values, which assumes that x - y won't overflow (or at least that the overflow won't produce a false 0).

  int delta = x - y;
  int delta_hi = delta / K;
  int delta_lo = delta - K * delta_hi;
  int equal_hi = (delta_hi * delta_hi + 2) / (delta_hi * delta_hi + 1) - 1;
  int equal_lo = (delta_lo * delta_lo + 2) / (delta_lo * delta_lo + 1) - 1;
  int equals = equal_hi * equal_lo;

or written out in full:

((((x-y)/K)*((x-y)/K)+2)/(((x-y)/K)*((x-y)/K)+1)-1)*
((((x-y)-K*((x-y)/K))*((x-y)-K*((x-y)/K))+2)/
 (((x-y)-K*((x-y)/K))*((x-y)-K*((x-y)/K))+1)-1)

(For signed 31-bit integers, use K=46341; for unsigned 32-bit integers, 65536.)

Checked with @chux's test harness, adding the 0 case: live on coliru and with negative values also on coliru.

On a platform where integer subtraction might produce something other than the 2s-complement wraparound, a similar technique could be used, but dividing the numbers into three parts instead of two.

Upvotes: 1

chux
chux

Reputation: 153348

Taking advantage of integer division in C truncates toward 0, the follows works well. No multiplication overflow. Well defined for all "positive-integer inputs x and y".

(x/y) * (y/x)

#include <stdio.h>
#include <limits.h>

void etest(unsigned x, unsigned y) {
  unsigned ref = x == y;
  unsigned z =  (x/y) * (y/x);
  if (ref != z) {
    printf("%u %u %u %u\n", x,y,z,ref);
  }
}

void etests(void) {
  unsigned list[] = { 1,2,3,4,5,6,7,8,9,10,100,1000, UINT_MAX/2 , UINT_MAX - 1, UINT_MAX };
  for (unsigned x = 0; x < sizeof list/sizeof list[0]; x++) {
    for (unsigned y = 0; y < sizeof list/sizeof list[0]; y++) {
      etest(list[x], list[y]);
    }
  }
}

int main(void) {
  etests();
  printf("Done\n");
  return 0;
}

Output (No difference from x == y)

Done

Upvotes: 1

Marcus M&#252;ller
Marcus M&#252;ller

Reputation: 36337

So the problem is that if they fix division by zero, it means that you cannot use any divisor that contains input variables anymore (you'd have to check that the divisor != 0, and implementing that check would solve the original x-y == 0 problem!); hence, division cannot be used at all.

Ergo, only +, -, * and the association operator () can be used. It's not hard to see that with only these operators, the desired behaviour cannot be implemented.

Upvotes: 0

Related Questions