Naive sign function for real numbers - challenge

1. Jul 1, 2010

How would you solve this without using decisional blocks?

2. Jul 1, 2010

Pere Callahan

How would I solve what? What about
$$\operatorname{sgn} x = x/|x| ?$$

3. Jul 1, 2010

Hurkyl

Staff Emeritus
What precisely do you mean by "solve", and by "decisional block"?

4. Jul 1, 2010

I mean find a sign function within the restrictions.

Restrictions are:

You aren't allowed the use of if ... thens.
You aren't allowed the use of piecewise functions.

I think that's all.

Oh, and you aren't allowed to use floor or ceil funcs unless you show yours don't use decision(al) blocks.

Last edited: Jul 1, 2010
5. Jul 1, 2010

Hurkyl

Staff Emeritus
Okay, then I use the function sgn(x).

6. Jul 1, 2010

So you give up?

7. Jul 1, 2010

Pere Callahan

You can probably approximate the sgn function with a smooth function which gives the same result within machine precision if you use round off errors to your advantage.

8. Jul 1, 2010

No need to approximate. Even returns 0 for 0.

9. Jul 1, 2010

disregardthat

Algorithms like;
|x| = x if x positive; else -x
are not essentially different from ordinary functions like f(x) = 2x, or qualitatively different you might say.

Both, given an argument, have an explicit way of producing a specific output. That is what functions are all about.

The function sgn(x) is not so to say a 'cop-out' for not being able to define an explicit function for the purpose you have, but a completely natural way of producing an element given an argument. I can though remember I felt the same at some point.. As a side note; one would not accept 'piecewise' functions at some point a few hundred years ago.

Nevertheless, within the boundaries of the question i propose $$f(x) = lim_{n \to \infty} \frac{2}{\pi} \arctan(xn)$$ .

Last edited: Jul 1, 2010
10. Jul 1, 2010

Office_Shredder

Staff Emeritus
If you're afraid of dividing by zero, add machine epsilon to x first. This cannot change the sign, and if you are legitimately trying to find what sign $$- \epsilon$$ is, you're probably doing it wrong

11. Jul 2, 2010

abs() is not a piece wise function. It only requires you to turn one particular bit to one particular value each and every single time.

Or to write a plus over the minus in front of a number regardless if there was a minus sign to begin with.

The process is the same each time and there is nothing that involves decision making in it. And yet abs() is surjective with more than one possible value. That's why abs() can be used to implement decision blocks in mathematics. And so can trunc(), which only requires you to dispose of the fractional part of a number. This is easy enough in fixed point arithmetic. Just set the least significant half/part to 0 every time. Truncating a float is not straight forward, though. But that's because of the ugly implementation.

Piecewise functions need decision making. When coding them, in the form of using decision(al) blocks. When plotting them by hand, in the form of choosing between the various branches.

Yeah. But what functions in mathematics produce exactly three possible values or a steps without being piecewise?

Those functions can be used to implement sign().

There's an important distinction distinction to be made. When plotting the function by hand you have to actively decide which branch to apply according to which interval the current value of x is in. Because piecewise functions are not functions but sets of two or more functions defined for different domains. Unless the function itself had a logic gate of some sort to do that task itself.

Abs() is to mathematics what NAND and NOR are to computer science. Logic arising out of nonlogic.

You can write entire programs without using decision blocks.
You can also write piecewise functions without using branching.

That's a not what I would consider a beautiful solution, if you don't mind me saying. It's also clearly not an exact solution for practical applications. But it's certainly thinking outside the box.

I don't need to do that. I already have a picture perfect sign function. I'm just curious to see other approaches to the problem.

12. Jul 2, 2010

jostpuur

This is dumb "guess what I'm thinking"-riddle, and not an interesting mathematical problem. Anyway, I thought I could mention that my favourite regularisation of the absolute value is

$$|x|\approx \sqrt{\epsilon + x^2}$$.

Regularised absolute values can be used to produce the sign function too:

$$\lim_{\epsilon \to 0^+} \frac{x}{\sqrt{\epsilon + x^2}}$$

13. Jul 2, 2010

Ok. Here's how I did it.

$$trunc\left( \frac{ | x + 1 | - | x - 1 | }{2} - 1 \right) + trunc\left( \frac{ | x + 1 | - | x - 1 | }{2} + 1\right)-trunc\left( \frac{ | x + 1 | - | x - 1 | }{2} \right)$$

http://img204.imageshack.us/img204/2855/sign0.png [Broken]

Last edited by a moderator: May 4, 2017
14. Jul 2, 2010

HallsofIvy

What's wrong with -1+ 2H(x) where H(x) is the Heaviside step function? That's much simpler.

Yes, that involves a "decision" but so does "trunc". I wonder if you really understand exactly what you are saying.

15. Jul 3, 2010

I don't see how the Heaviside function is any simpler. Or elegant.

Trunc() doesn't involve branching/decision blocks because all you ever do is clear some bits, set them to 0. Or discard what's after the decimal point. Just like abs() only changes the sign or sign bit one way.

16. Jul 3, 2010

disregardthat

How much more decision is turning a positive sign to 1 and a negative sign to 0, compared to removing the fractional part?

17. Jul 3, 2010

Hurkyl

Staff Emeritus
Hrm. If you were interested in computer programs that manipulate binary representations of numeric data, then why the heck didn't you say so, when I asked you what you meant by "solve"? :grumpy:

Incidentally, conditional assignment doesn't involve branching. I'm having trouble thinking of any situation where hacking together a decisional block via floating-point operations is both preferable to branching that I wouldn't expect to work even better with conditional assigns.

P.S. I suspect trying to bit twiddle floating-point data in registers to be inefficient.

18. Jul 3, 2010

Office_Shredder

Staff Emeritus
wolfram alpha suggested this one

$$e^{iarg(x)}$$

19. Jul 3, 2010

Staff: Mentor

I'm with Hurkyl on this - if your question was in the context of a computer implementation, why didn't you say so up front?

In terms of computer arithmetic operations, the expression above seems very inefficient. If you have a system that adheres to IEEE Standard for Floating Point Operations (IEEE 754), it's a simple matter of looking at the highest-order bit to determine the sign of the number. In the first term above you have two floating point additions, two calls to fabs, a floating point subtraction, a floating point division, and then a truncation. Then you have to do the same exact thing two more times. All of these operations take a number of clock cycles to complete. It might be the case that calculating the sign of a number via the expression above is slower than if-else logic, even considering cases where the else branch is taken, and the FP unit pipeline has to be restarted.

Last edited: Jul 4, 2010
20. Jul 3, 2010

D H

Staff Emeritus
You've just hidden the decision blocks inside this black box function trunc (which is loaded with decision blocks). In a very inefficient way, I might add.

What exactly is the point of this exercise? Is it homework?