Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Naive sign function for real numbers - challenge

  1. Jul 1, 2010 #1
    How would you solve this without using decisional blocks?
     
  2. jcsd
  3. Jul 1, 2010 #2
    How would I solve what? What about
    [tex]
    \operatorname{sgn} x = x/|x| ?
    [/tex]
     
  4. Jul 1, 2010 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    What precisely do you mean by "solve", and by "decisional block"?
     
  5. Jul 1, 2010 #4
    xxlelouchxx-albums-random-stuff-picture81260-divide-zero.jpg

    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
  6. Jul 1, 2010 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Okay, then I use the function sgn(x). :wink:
     
  7. Jul 1, 2010 #6
    So you give up? :wink:
     
  8. Jul 1, 2010 #7
    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.
     
  9. Jul 1, 2010 #8
    No need to approximate. Even returns 0 for 0.
     
  10. Jul 1, 2010 #9

    disregardthat

    User Avatar
    Science Advisor

    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 [tex]f(x) = lim_{n \to \infty} \frac{2}{\pi} \arctan(xn)[/tex] :smile: .
     
    Last edited: Jul 1, 2010
  11. Jul 1, 2010 #10

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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 [tex] - \epsilon[/tex] is, you're probably doing it wrong
     
  12. Jul 2, 2010 #11
    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.
     
  13. Jul 2, 2010 #12
    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

    [tex]|x|\approx \sqrt{\epsilon + x^2}[/tex].

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

    [tex]
    \lim_{\epsilon \to 0^+} \frac{x}{\sqrt{\epsilon + x^2}}
    [/tex]
     
  14. Jul 2, 2010 #13
    Ok. Here's how I did it.

    [tex]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)[/tex]

    http://img204.imageshack.us/img204/2855/sign0.png [Broken]
     
    Last edited by a moderator: May 4, 2017
  15. Jul 2, 2010 #14

    HallsofIvy

    User Avatar
    Science Advisor

    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.
     
  16. Jul 3, 2010 #15
    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.
     
  17. Jul 3, 2010 #16

    disregardthat

    User Avatar
    Science Advisor

    How much more decision is turning a positive sign to 1 and a negative sign to 0, compared to removing the fractional part?
     
  18. Jul 3, 2010 #17

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  19. Jul 3, 2010 #18

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    wolfram alpha suggested this one

    [tex]e^{iarg(x)}[/tex]
     
  20. Jul 3, 2010 #19

    Mark44

    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
  21. Jul 3, 2010 #20

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook