Naive sign function for real numbers - challenge

[SonyAD]

How would you solve this without using decisional blocks?

 

[Pere Callahan]

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

 

[Hurkyl]

How would you solve this without using decisional blocks?

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

 

[SonyAD]

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

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

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.

 

[Hurkyl]

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

 

[SonyAD]

So you give up?

 

[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.

 

[SonyAD]

No need to approximate. Even returns 0 for 0.

 

[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)$$ .

 

[Office_Shredder]

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

 

[SonyAD]

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.

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.

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

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().

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.

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.

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

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.

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

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.

 

[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}$$.

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

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

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

 

[SonyAD]

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

 

[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.

 

[SonyAD]

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.

 

[disregardthat]

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.

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

 

[Hurkyl]

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.

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.

 

[Office_Shredder]

wolfram alpha suggested this one

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

 

[Mark44]

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)$$

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.

 

[D H]

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)$$

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?

 

[SonyAD]

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

A lot more.

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:

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.

Incidentally, conditional assignment doesn't involve branching.

The branches are very short but it's still 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.

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.

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?

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.

In terms of computer arithmetic operations, the expression above seems very inefficient.

Again, that's not the point.

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.

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

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.

I never raised performance as an issue.

Then you have to do the same exact thing two more times. All of these operations takes 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.

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.

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?

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.

 

[Hurkyl]

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.

"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.

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

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.

 

[D H]

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.

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?

 

[SonyAD]

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

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.

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.

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

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.

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.

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.

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.

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?

That's not true. I did mention it:

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.
[...]
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.

 

[Hurkyl]

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

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.

 

[SonyAD]

Ok. Now that we have an actual sign function instead of a piecewise hack, here's Kronecker Delta:

δ( a, b ) = 1 - | sign( a - b ) |

And the heaviside function:

$$H( n ) = \frac{ sign( n ) + | sign(n) | }{ 2 } + \delta( sign( n ), 0 )$$

 

[Hurkyl]

P.S. "a method of computing a function" has nothing to do with the function itself, other than producing its values.


How do you plan on implementing trunc without decision blocks? e.g. if we are operating on strings representing numbers in decimal notation, we start looking at the leading symbol and then the most obvious truncation implementation is (doing the conversion in place)

1. If we are at the end, then stop.
2. If the symbol we are looking at is not '.'
   • Move to the next symbol
   • Goto 2
3. Move to the next symbol
4. If we are at the end, then stop
5. Overwrite the current symbol with '0'
6. Goto 4

 

[SonyAD]

P.S. "a method of computing a function" has nothing to do with the function itself, other than producing its values.

Then why do I have to point how trunc works all the time?

This is a false argument. You're asking me to deduce the thought processes that occur in your mind as you truncate the non standardised, alphanumeric string representation of a real number. A real is not some random string of variable length with a period (maybe) somewhere inside.

A particular real in your representation may not even contain the period. Or use a comma instead of a decimal point.

And even so, I devised a proof of concept, some time ago, whereby I implemented a simple z-buffer without if-thens or conditional assignments. I devised a function employing abs() to compute array offsets [0 or 1] which contained the new and the old value. Then I supplanted the z-value at the computed array offset into the z-buffer and changed the pixel colour (I also had a new and old pixel colour array of length 2). That's about all I remember. Can't find the source.

So I think a decisionless algorithm is probably possible for truncation of any real in a standardized representation system.

You know, at the most fundamental level, logic and boolean mathematics simply must derive from non-logic. Decision blocks and branching must derive from immutable processes or hardware.

This is what we toy with in thought experiments such as these.

And I think problems such as this can help shed light into the relationship between chaos and order.

 

[Dickfore]

I will use the Heaviside step function:

$$sgn(x) = 2 \, \theta(x) - 1$$

 

[D H]

Assuming that the comparison operators > and < are 0/1 operators (false/true), I'll use $\mathrm{sgn}(x) = (x>0) - (x<0)$

 

[The Chaz]

I will use the Lemmings suicide function. Then maybe this thread will truncate.

 

[Unit]

Given any number x you could guess the sign. You'd be right half the time.