# The Zero One Puzzle Solution

There's lots of things that almost work, but it's hard to come up with an answer that uses just plain arithmetic functions. The closest I could figure was to use the SIGN function, which has the property:

sign ( A, B ) = | A | * sign of B.
If B is negative, the sign of B is -1, otherwise it is 1.

So now consider the fact that, if M = N, both M-N and N-M will be zero. Otherwise, one will be strictly positive and one strictly negative. Now consider the formula:

| M - N | + | N - M |
which almost gets us there. It's zero when M=N, but in the nonequal case, it's too many different values.

But suppose we take the difference in the values of the SIGN function for M-N and N-M. This will be 2 or -2 if the numbers are unequal, and 0 if they are equal. So take the absolute value, divide by 2, and you've got it!

K = 1 - int ( | sign ( 1, M - N ) - sign ( 1, N - M ) | ) / 2
While this solution works for all arguments M and N, it is complicated, non-intuitive, and uses the SIGN function, which is on the borderline between a true arithmetic function and a logical function. (Of course, then, the SIGN function can be derived from the absolute value function, and we don't want to give that up!)

As discussed in the problem proposal, another one-line function would be

K = int ( M == N )
except that this uses a LOGICAL expression and a conversion operator. Also, while this works on some versions of FORTRAN77, I could not get the FORTRAN90 compiler to accept the construction. It refuses to use the int conversion operator on anything but a numeric quantity.

A more interesting proposal is

K = (M/N) * (N/M)
which has some great merits on number theoretic grounds. Because M and N are integers, the divisions will return only the whole number of the result. In particular, if we can guarantee that both M and N are positive, then
• if M is less than N, then N/M is 0, so K is 0;
• if N is less than M, then M/N is 0, so K is 0;
• if M is equal to N, then both N/M and M/N are 1, so K is 1.
This proposal breaks down if either argument is zero; FORTRAN will not compute an integer fraction with zero denominator. Moreover, the computation will not work for negative numbers. Notice that it will return a value of 1 for arguments of 4 and -4. This solution was devised by David Levine of St Bonaventure University.

David Faden of Iowa State University submitted the following function, which works properly for all arguments and has a clean form:

K(M,N) = 1 / ( 1 + ( M - N ) * ( M - N ) )

A few weeks later, David Faden, after consulting with his father, Arnold Faden, submitted the function:

K = 1 - min ( abs ( M - N ), 1 )
and the related function:
K = 1 - ( abs ( M - N ) + 1 - abs ( abs ( M - N ) - 1 ) ) / 2
which is actually just a variation of the previous function, eliminating the MIN function by using the idea that the minimum function can be defined in terms of the absolute value function:
min ( x, y ) = ( x + y - abs ( x - y ) ) / 2

Li Wang of Washington State University submitted the following function, which works properly for all arguments, and essentially "regularizes" the function x/x so that, after rounding, it is the same as the constant function 1 except at 0:

K(M,N) = 1 - ( M - N ) / ( M - N + 0.1 )
Note that we are relying on the appropriate conversion and rounding for this formula to work properly! In particular, the result on the right hand side needs to be rounded towards zero, regardless of its sign. The FORTRAN rules for conversion from real to integer follow this rule.

If you'd like, you can copy a sample implementation of the functions: ZERO_ONE.F90 or the output of a run in ZERO_ONE.OUT.

Back to The Zero One Puzzle.

Last revised on 28 April 2007.