3
\$\begingroup\$

I'm currently working with a branchless language which does not have native Less-Than, Greater-Than or Equal-To functions. I do however have min, max and abs functions and standard arithmetic (+, -, / and *) available to me.

I'd like to create these three functions (as L(a, b), G(a, b) and E(a, b) respectively, which will output 0 for false and 1 for true. So, for example, L(3, 7) would return 1 for true whereas G(3, 7) would return 0 for false, and E(3, 7) would also return 0, etc.

The min and max functions only allow you to pass two parameters, a and b, and then spits out the respective minimum or maximum of the two parameters. The abs function takes the one parameter and returns the absolute value.

I've postulated that given that the min(a, b) is equivalent to:

L(a,b) * a + (1 - L(a,b)) * b

It would stand to reason that:

L(a,b) = (min(a,b) - b) / (a - b)

and similarly:

max(a,b) = G(a,b) * a + (1 - G(a,b)) * b

therefore:

G(a,b) = (max(a,b) - b) / (a - b)

But this is where I get stumped because, I'm not sure how to account for the possibility of a-b equalling 0 in both instances, which as a result stumps me on how to approach the E(a, b) function.

So my question is this... Given that I only currently have access to basic arithmetic functions as well as min(a,b), max(a,b) and abs(a), and because of the language being branchless (therefore no loops), is there a way to programmatically account for the a-b divide-by-zero issue such that if I do have a scenario where a == b that these functions can return zero for either L() or G(), otherwise output the original equations I have derived, and also be able to provide code for E(a, b)?

Given that this is fairly generic (hey, I've written it in psuedocode!) I'd appreciate some insight on how to proceed. In this case, the solution needs to work with both integers as well as floats.

Context: This is research for a personal project I'm working on relating to binary registers, thus the need for 1's and 0's for output and I'm kinda stuck at this point.

Improve this question
\$\endgroup\$
23
  • 1
    \$\begingroup\$ Can you clarify if you're going for least number of tokens or something in addition to restricted source? \$\endgroup\$ Commented May 24, 2021 at 23:17
  • 1
    \$\begingroup\$ Also, are these numbers integers, doubles, or something else? \$\endgroup\$ Commented May 24, 2021 at 23:21
  • 1
    \$\begingroup\$ How is / defined exactly? If the numbers are integers, is it floored division or round-towards-zero? \$\endgroup\$ Commented May 24, 2021 at 23:25
  • 2
    \$\begingroup\$ @WheatWizard how do boolean values different from single bit integers? \$\endgroup\$ Commented May 25, 2021 at 12:10
  • 2
    \$\begingroup\$ @WheatWizard number is just a few more bytes than boolean. Also in most computer languages, a boolean costs 1 bytes (8 bits) instead of 1 bit. I don’t see it may be unclear that how to convert between boolean concepts and integers, and integers and reals. You just need to padding many 0s. Also I would consider false=0, true=1 as default mapping. It should only be clarified if it not follow such convenience. \$\endgroup\$ Commented May 25, 2021 at 12:32

3 Answers 3

Reset to default
7
\$\begingroup\$

Integers and round-to-zero integer division

// 1 if x >= y, 0 otherwise GE(x, y) = (x - y + 1) / (abs(x - y) + 1) LE(x, y) = GE(y, x) E(x, y) = GE(x, y) * LE(x, y) L(x, y) = LE(x, y) - E(x, y) = 1 - GE(x, y) G(x, y) = GE(x, y) - E(x, y) = 1 - LE(x, y)

If x - y is negative, x - y + 1 has smaller magnitude than abs(x - y) + 1, so the division rounds to 0.

If x - y is zero or higher, x - y + 1 is the same as abs(x - y) + 1, so the result is 1.

Integers and floored integer division

GE(x, y) = (x - y + abs(x - y) + 1) / (abs(x - y) * 2 + 1)

If x - y is negative, the numerator is fixed at 1, but the denominator is at least 3. Therefore the result is zero.

If x - y is zero or positive, the numerator and the denominator are the same, so the result is 1.

Floating-point numbers

MarcMush pointed out a possible use of eps, the smallest representable number greater than 0. GE can be implemented for floating-point numbers using it:

GE(x, y) = (max(x - y, -eps) + eps)/(abs(x - y) + eps)

I haven't found any way without eps or the floor function. (If floor is available, flooring the second solution works for floats.) tsh pointed out that we can't get a (true) discontinuous function from a bunch of continuous functions, so I'm pretty sure it is impossible without eps or an additional built-in that provides discontinuity.

Assuming an IEEE floating-point representation, the solution above is expected to give exact results (exactly 0 or exactly 1) for all non-NaN, non-infinite floating-point values of x and y.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Given that I’m after integers and floats, this fits the bill nicely… thanks \$\endgroup\$ Commented May 25, 2021 at 8:42
  • \$\begingroup\$ L(x,y)==LE(x,y)-E(x,y)==LE(x,y)(1-GE(x,y)) but surely the LE(x,y) becomes redundant so you can just write L(x,y)==1-GE(x,y)? \$\endgroup\$ Commented May 25, 2021 at 9:01
  • \$\begingroup\$ @Neil Yeah, of course. \$\endgroup\$ Commented May 25, 2021 at 10:05
4
\$\begingroup\$

This answer only works on integer values :)

Test Zero

We all know that

$$ (t+1)(t-1)=t^2-1 $$ $$ t\cdot t-(t+1)(t-1)=1 $$

As long as \$t\$ is integer.

$$ t\cdot t-|t+1|\cdot|t-1| = \begin{cases} 1 & t\ne 0 \\ -1 & t = 0\\ \end{cases} $$

So we have:

isZero(t) = (t*t-abs(t+1)*abs(t-1)+1)/2

Build others

And then, you can have

GreaterThanOrEqual(a, b) = isZero(max(b-a, 0)) LessThanOrEqual(a, b) = GreaterThanOrEqual(b, a) Equal(a, b) = GreaterThanOrEqual(a, b) * LessThanOrEqual(a, b) GreaterThan(a, b) = GreaterThanOrEqual(a, b) - Equal(a, b) LessThan(a, b) = LessThanOrEqual(a, b) - Equal(a, b)
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ In fact isZero really detects whether a 1>t>-1, so it will also work for non-integers, if you interpret it that way. \$\endgroup\$ Commented May 25, 2021 at 11:59
  • \$\begingroup\$ @SeanD for \$ t \in (-1,1) \$, \$ t^2-|t+1|\cdot |t-1|=2t^2-1 \$ \$\endgroup\$ Commented May 25, 2021 at 13:36
-2
\$\begingroup\$

Assuming floor division: E(x,y) = (1 - abs(x-y)) / (1 + abs(x-y)) L(a,b) = E(min(a,b), a) - E(a,b) G(a,b) = E(max(a,b), a) - E(a,b)

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.