Branchless sign function?

[Alex]

Mike, could you consider adding a math.sign function to LuaJIT?

I've come across a few places in my projects where I need a sign function,
that is, a function that returns 1 for positive values, -1 for negative
values, and 0 for zero.

A naive function goes like this:

local function sign(x)
if x < 0 then
return -1
elseif x > 0 then
return 1
else
return 0
end
end

However, that's three branches for a relatively simple operation. Granted,
the zero branch is probably not going to be taken a whole lot, but still.

I've seen other ways of doing it, but they either rely on the number being
an integer or have some other limitation (ex. `abs(x) / x` is branchless
and simple, but fails for 0.) It seems like the SSE instruction set should
have something for this, but I'm not familiar with it.

Is it possible and feasible to implement this, and if so, could you?

[Coda Highland]

Post by Alex
I've seen other ways of doing it, but they either rely on the number being
an integer or have some other limitation (ex. `abs(x) / x` is branchless and
simple, but fails for 0.)

Could use x && (abs(x) / x). That way if x is 0, it short-circuits.

/s/ Adam

[Coda Highland]

Post by Coda Highland

Post by Alex
I've seen other ways of doing it, but they either rely on the number being
an integer or have some other limitation (ex. `abs(x) / x` is branchless and
simple, but fails for 0.)

Could use x && (abs(x) / x). That way if x is 0, it short-circuits.
/s/ Adam

Er. I've been writing JS code today. That's spelled "and" in Lua. :P

/s/ Adam

[Mike Pall]

Post by Alex
I've come across a few places in my projects where I need a sign function,
that is, a function that returns 1 for positive values, -1 for negative
values, and 0 for zero.

local bor, shr, sar = bit.bor, bit.rshift, bit.arshift
local function sign(x) return bor(shr(-x, 31), sar(x, 31)) end

--Mike

[Alex]

Post by Mike Pall
local bor, shr, sar = bit.bor, bit.rshift, bit.arshift
local function sign(x) return bor(shr(-x, 31), sar(x, 31)) end

That only works for integers though; it incorrectly returns zero for
numbers in the (-0.5, 0.5) range.

[Scott Condit]

Something like the below should work for -0.5,0.5 also.

Perhaps C99 copysign could be implemented in LuaJIT without dropping to FFI (since it's just doing a bitmask)?


Regards

Scott Condit


local ffi=require'ffi';
ffi.cdef[[double copysign (double x, double y);]]

local function posneg(x) -- x<0?-1:1
return ffi.C.copysign (1, x)
end;

local function signum(x) -- x<0?-1:(x>0?1:0)
return ffi.C.copysign (bit.band (x/x,1), x)
end;

Post by Mike Pall
local bor, shr, sar = bit.bor, bit.rshift, bit.arshift
local function sign(x) return bor(shr(-x, 31), sar(x, 31)) end

That only works for integers though; it incorrectly returns zero for numbers in the (-0.5, 0.5) range.
--
Sincerely,
Alex Parrill

[Coda Highland]

Post by Scott Condit
local function signum(x) -- x<0?-1:(x>0?1:0)
return ffi.C.copysign (bit.band (x/x,1), x)
end;

That looks suspiciously like a division by zero if you ask me.

/s/ Adam

[Shmuel Zeigerman]

Post by Alex
I've come across a few places in my projects where I need a sign function,
that is, a function that returns 1 for positive values, -1 for negative
values, and 0 for zero.

I wonder about the use cases of that function. Could you give an example?

[Coda Highland]

Post by Shmuel Zeigerman

Post by Alex
I've come across a few places in my projects where I need a sign function,
that is, a function that returns 1 for positive values, -1 for negative
values, and 0 for zero.

I wonder about the use cases of that function. Could you give an example?

Consider, for example, delta encoding -- sure, you can implement delta
encoding with conditionals, but the sign function makes it a simple
expression inside the loop. This is the case with most uses of the
sign function; it's an optimization for a case when you would
otherwise be using conditionals.

/s/ Adam

[Alex]

For example, AABB vs AABB collision detection using SAT. The sign function
is used to calculate the sign of the resulting overlap vector, depending on
which side the box is colliding from.

(Not my best code, but still illustrates the usage)


--- Does an AABB vs AABB collision test.
-- @return Overlap vector
-- @return Collision face bits
function Collision.aabb_vs_aabb(box1, box2)
local minoverlap = math.huge
local bits = nil
local minax = nil

for i=1,3 do
local ax = axis[i]
local d = box2.center[ax]-box1.center[ax]
local ad = abs(d)
local hws = box1.halfwidth[ax]+box2.halfwidth[ax]
if ad > hws then return nil end
local sgn = sign(d)
local o = (hws-ad)*sgn
if abs(o) < abs(minoverlap) and o ~= 0 then
minoverlap = o
bits = faces[ax][sgn == 0 and 1 or 2]
minax = ax
end
end

if minax then
local v = vector()
v[minax] = minoverlap
return v, bits
else
return nil
end
end

Post by Shmuel Zeigerman

Post by Alex
I've come across a few places in my projects where I need a sign function,
that is, a function that returns 1 for positive values, -1 for negative
values, and 0 for zero.

I wonder about the use cases of that function. Could you give an example?
--
Shmuel