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?

21. Jul 4, 2010

A lot more.

That's not the point at all. I was just trying to show how the implementation of such a function doesn't involve decision blocks.

The branches are very short but it's still branching.

That's not the point. The point is ideological. Can a sign function be defined or is a piecewise hack all there can be?

It turns out, one can.

That's not it. I was pointing out the hardware implementation of numeral systems so ppl. would see where I'm coming from when I say you don't need decision blocks to get the absolute value of an integer or the integer part of a real. It's the same with any proper implementation of a numeral system.

These operations are defining, fundamental to functioning numeral systems.

For instance, obtaining the absolute value of an integer (signed natural) number without having to evaluate expressions is one of the defining features of a signed number system. You just set the sign to plus regardless whether it was - or + originally.

What is the point of Z if you can't get the absolute value without thinking about it? Might as well define an arbitrary natural number as reference point and stop using the positive/negative number paradigm.

Then you would, of course, first have to evaluate whether a given natural number is smaller or greater than the reference number and then subtract it from the reference or vice versa, as appropriate. And remember separately, on your own, whether it was to the left or to the right of the reference number because the numeral system you use doesn't provide any useful feature to that end.

What's the point of R if you can't get the integer and fractional parts without thinking about it?

Might as well count in millimetres to express the length of a Peugeot: 3835 mm.

I really don't know how I can be any clearer.

Again, that's not the point.

You don't get the sign of the number. The sign should be 0 for 0.

I never raised performance as an issue.

That is of no concern. This is a purely mathematical exercise. I brought up the hardware representation of various number sets only to show things I wanted to show.

Again, implementing abs() doesn't require decision blocks. Because all you do is turn the sign bit to 0.

The same with trunc. In a fixed point implementation of real numbers you set all the bits in the fractional part to 0. On paper you only need to discard what's after the decimal point.

How is that in any way a black box function?

A black box function is a piecewise function.

The point was to devise a sign function.

Last edited: Jul 4, 2010
22. Jul 4, 2010

Hurkyl

Staff Emeritus
"Setting a bit to zero" is very much a computer-specific operation, rather than having anything to do with mathematics of real numbers.

The very specific reason I asked you to precisely clarify what you meant by "solve" and by "decisional block" was to prevent exactly what this happened in this thread. You are the only one who has any idea what you actually mean, everyone else posts an answer according to other reasonable interpretations of those words, and then you get persnickety because nobody was psychic and played the game in exactly the way you had in mind.

Anyways, I can prove that you cannot construct the sign function as a composition of elementary arithmetic operations (+,-,*,/) and the absolute value function: each of those functions is continuous, and the composite of continuous functions is continuous, so I am curious what else you had in mind as permissible.

No it's not. On most (all?) microprocessors these days, conditional assign is a single machine instruction. There is no branching involved; flow always moves onto the next instruction no matter what the result of the test is.

Last edited: Jul 4, 2010
23. Jul 4, 2010

D H

Staff Emeritus
Well, gee, you never mentioned fixed point arithmetic until this post. How were we to know that? We can't read your mind. You need to spell things out. What exactly are you trying to do here, and what is the point of this silliness?

24. Jul 4, 2010

Is putting a plus in front of a number also a computer specific operation? I mentioned that as well.

Also, discarding everything after the decimal point as a definition for trunc(). The computer specific analogy being setting the fractional byte(s) to 0000 0000.

Of course this doesn't work neatly for the floating point representation of reals. Because it's ugly. Possible values are not dispersed uniformly in the range. There's an inverse relationship between accuracy and the size of the stored value.

I'm not being "persnickety"(had to look that up). Jarle gave the closest thing to an answer early on and I acknowledged it.

I concur. That's why I also used the trunc() function.

As I said, abs(), trunc(), +, -, ยท, /, etc. Are allowed. No piece wise functions or anything that requires evaluation of an expression.

abs() and trunc() do not require that.

Conditional assignment doesn't work for a sign() function, which can return either of three values: -1, 0, 1. At least not in one go.

Furthermore, how is conditional assignment not a piecewise function? Or a decision block?

You're using hardware technicalities (the fact that the decision block is implemented as a single machine instruction) to skirt around the fact I did not allow it.

I'm talking about things at the conceptual level.

That's not true. I did mention it:

25. Jul 4, 2010

Hurkyl

Staff Emeritus
I don't know; you haven't precisely specified what you mean by those. The closest thing you gave is that it's to be implemented via a straight-line computer program.