21 ms·

One does not simply calculate the absolute value

• kurthr 5y ago
  And don't forget complex numbers or higher dimensionality.
  • Koshkin 5y ago
    The complex numbers and quaternions are still represented using floating point numbers.
    • kurthr 5y ago
      Yeah, I'm aware, but you need to accurately compute abs/magnitude, which presents its own complexities. Including exponentials, it's highly related to the non-trivial accurate computation of trigonometric functions of floats.
• da_chicken 5y ago
  > For example, if you divide 1.0 by +0.0 and -0.0, you get completely different answers: +Infinity and -Infinity. This must be a Java-ism. In most languages I've used you get a division by zero error or NaN.
  • titzer 5y ago
    It's IEEE-754.
    • magicalhippo 5y ago
      And there are algorithms that rely on this, like this[1] branchless axis-aligned bounding box intersection test. It exploits the division by zero sign logic of IEEE-754, so that the min/max operations used also handles the edge cases where the ray is parallel to an axis. [1]: https://tavianator.com/2011/ray_box.html https://tavianator.com/2011/ray_box.html
  • ketzu 5y ago
    +/- Infinity seems to be correct according to IEEE754. IEEE754 section 7.3: The divideByZero exception shall be signaled if and only if an exact infinite result is defined for an operation on finite operands. The default result of divideByZero shall be an ∞ correctly signed according to the operation: ― For division, when the divisor is zero and the dividend is a finite non-zero number, the sign of the infinity is the exclusive OR of the operands’ signs (see 6.3). ― For logB(0) when logBFormat is a floating-point format, the sign of the infinity is minus (−∞).
  • Agentlien 5y ago
    This is what you get according to IEE 754. You'd get NaN from 0.0/0.0 or division by zero if you did 1/0 as integer division.
  • titzer 5y ago
    Haha, -0. After spending literal years of my life dealing with that little encoding nuisance, in everything from the V8 TurboFan JIT, to WebAssembly, to adding floating point to Virgil, I just gotta say, that little turd is so not worth it. I've read a lot of different justifications for it (it's a limit, it represents approaching 0 from the negatives, some algorithms need it, etc), I have to admit, I just don't buy it. It's an encoding artifact that's produced so much accidental complexity that, in my book, has been far more trouble than it's been worth. Change my mind.
    • darig 5y ago
      -mind
    • nimish 5y ago
      How else would you represent a branch cut or even a jump at 0? https://people.freebsd.org/~das/kahan86branch.pdf https://people.freebsd.org/~das/kahan86branch.pdf from the father of ieee-754 is illuminating.
      • croes 5y ago
        So for programming convenience we ignore correct math?
        • FabHK 5y ago
          We cannot represent "correct math" on a computer, because the set of reals is uncountable, but in 64 bits we can only represent finitely many numbers, not infinitely many, let alone uncountably many. And given that we have to implement some sort of approximation to the usual math on a closed subset of the reals (rationals, even), why not extend it with some "numbers" (negative zero, plus/minus infinity, NaNs) that, yes, enable programming convenience?
          • croes 5y ago
            There is a difference between 2.4987665678 as 2.5 and undefined as ±infinity especially because 1.0/+0.0 is +infinity and 1/0 is just an exception in Java. Shouldn't it be the same result?
  • kmm 5y ago
    Which languages did you try? I found that dividing 1.0 by 0.0 gives Infinity in Java, C, Julia, JavaScript, Ruby, Clojure, Haskell and Rust. I get division errors in Python and Perl. Curiously, Go gives me a compiler error if I divide constant literals, but assigning 0.0 to a variable and dividing by it does work. On top of that, assigning -0.0 to a float variable leads to it having the value +0.0, which I would call a borderline compiler bug. Both are probably a consequence of Go constant literals not being IEEE-754 floats but some arbitrary precision number types, but it's very unexpected behavior.
    • da_chicken 5y ago
      > Which languages did you try? Python and C#.
      • Kranar 5y ago
        Python does throw an exception but C# does not.
      • kmm 5y ago
        Dividing 1.0 by 0.0 gives ∞ in C# as well when I try it.
        • da_chicken 5y ago
          You're right. I must've divided 0 by 0 and -0. That's the only way C# gives me NaN. I thought I'd specifically avoided doing that.
  • wodenokoto 5y ago
    While parent isn’t correct in their assumption, this was also my first thought after reading the article and I appreciate the ensuing discussion. I hope others will take the entire thread into consideration before downvoting.
  • FabHK 5y ago
    > In most languages I've used you get a division by zero error or NaN Or it raises an exception, which once disabled a navy warship for hours: > Now decommissioned, the USS Yorktown was among the first warhips extensively computerized to reduce crew (by 10% to 374) and costs (by $2.8 million per year). > On 21 Sept. 1997, the Yorktown was maneuvering off the coast of Cape Charles, VA, when a crewman accidentally ENTERed a blank field into a data base. The blank was treated as a zero and caused a Divide-by-Zero Exception which the data-base program could not handle. It aborted to the operating system, Microsoft Windows NT 4.0, which crashed, bringing down all the ship’s LAN consoles and miniature remote terminals. > The Yorktown was paralyzed for 2 3/4 hours, unable to control steering, engines or weapons, until the operating system had been re-booted. Fortunately the Yorktown was not in combat nor in crowded shipping lanes. > If IEEE 754’s default had been in force, the division by zero would have insinuated into the data-base an ∞ and/or NaN, which would have been detected afterwards without a crash. http://people.eecs.berkeley.edu/~wkahan/Boulder.pdf http://people.eecs.berkeley.edu/~wkahan/Boulder.pdf https://www.wired.com/1998/07/sunk-by-windows-nt/ https://www.wired.com/1998/07/sunk-by-windows-nt/ EDIT: It was 2 3/4 hours, not 23 hours. I copied/pasted carelessly from the PDF.
    • da_chicken 5y ago
      Eh, there's like six separate issues that led to this. 1. Interface accepted blank value for a form when a numeric value is required. 2. Application and database permitted a null or coerced a zero when the value is required and cannot be zero. You've got to sanitize your input. 3. Application did not check for or gracefully handle something as common as a division by zero exception. Instead it proceeded to a buffer overrun and crashed. 4. Application crashing apparently caused an OS crash? Yes, okay, it's NT 4.0 and a buffer overrun, but that still should not happen. Protected mode is a thing. 5. There is no redundancy in a system that manages the steering, weapons, and engines of a warship. 6. A warship was unable to restore the single CNC system to working order for 23 hours. Furthermore... there's no evidence that the software would have behaved more sensibly or more controllably if it had a value of infinity instead of an error. It shouldn't have had a zero in the first place.
• beervirus 5y ago
  Does this correctly handle all the different NaN values, weird corner cases, etc. properly?
  • JadeNB 5y ago
    > Does this correctly handle all the different NaN values, weird corner cases, etc. properly? Of course the answer to "have you covered all weird corner cases" is always 'no', but the article addresses the issue of different NaNs: > […] However, it turns out that doubleToLongBits is also not entirely trivial, because it canonicalizes NaNs. There are many ways to encode a not-a-number as a double, but only one of them is canonical. These different NaNs are even more similar twins, they can be distinguished neither via Double.compare, nor via any operation. Even string representation is the same. But they look different in computer memory. To avoid surprises, doubleToLongBits converts any NaN to the canonical form, which is encoded in long as 0x7ff8000000000000L. Of course, this procedure adds more conditions, which we do not need here. > What can we do? It appears that there's another method doubleToRawLongBits. It doesn't do any smart conversion of NaN and just returns exactly the same bit representation: […]
    • sp332 5y ago
      The question is whether that last technique, of just flipping the sign bit, handles NaNs and infinities.
      • MontyCarloHall 5y ago
        Yes. The sign bit is totally independent of the value being encoded, whether that’s a number, q/sNaN, or infinity. Nitpick: we are not flipping the sign bit, but rather setting it to 0.
      • pm215 5y ago
        It's the required semantics of the IEEE floating point spec's absolute-value operation. This does mean that abs() doesn't behave like eg addition in that it won't set fp exception flags for signaling NaNs, or canonicalize NaNs, or set a flag to note that this was a denormal number. But at the language level "follows IEEE semantics" is probably overall less surprising. chs() ("flip the sign bit") is the other operation that's defined as effectively just an operation on the representation rather than a "do a real floating point computation".
• athrowaway3z 5y ago
  Wouldn't max( x,-x ) cover everything ?
  • Kranar 5y ago
    That will not handle -0.0 unfortunately since 0 == -0.
    • alisonkisk 5y ago
      That doesn't matter because Math.max() knows the difference between +0.0 and -0.0. Try it and you'll see.
      • bordercases 5y ago
        It does that because of the way they implement arithmetic, not about an inherent property of the mathematical function `max`. The problem has to be solved once.
  • alisonkisk 5y ago
    The article's (dubious, as mentioned at the end) goal is finding the most efficient way in CPU time.
  • kmm 5y ago
    Naively, max(a, b) would be implemented as return a >= b ? a : b; But if x is -0.0, you're back to the same problem that -0.0 >= +0.0 actually turns out to be true and not false, hence the return value will be -0.0. Looking at the actual implementation[0], doubleToRawLongBits is used again here to take care of this edge case. So it would work, but a lot slower than the version given in the article. 0: https://github.com/openjdk/jdk/blob/36e2ddad4d2ef3ce27475af6244d0246a8315c0c/src/java.base/share/classes/java/lang/Math.java#L1681 https://github.com/openjdk/jdk/blob/36e2ddad4d2ef3ce27475af6...
    • andi999 5y ago
      Couldn't you also implement max as return a>b? a:b; (changing greater equal to just greater). Would the problem then still persist?
• m4r35n357 5y ago
  Bah! Just square & take the square root!
• im3w1l 5y ago
  > return Double.longBitsToDouble( > Double.doubleToRawLongBits(value) & 0x7fffffffffffffffL); Technically, this will change NaN values into different ones.
  • ectopod 5y ago
    Why do you say that? It extracts the bits using doubleToRawLongBits which does not do NaN canonicalization by design. And it gets back to a double with longBitsToDouble which "returns the double floating-point value with the same bit pattern". So it doesn't change anything either.
    • im3w1l 5y ago
      NaN values can have sign bit set. This will unset it.
      • toxik 5y ago
        So we defined abs(NaN), sounds like a feature to me ;-)
      • gene91 5y ago
        You made a good point. But one might argue that -nan should become nan after an abs operation. I don't know enough about this topic to determine whether such an argument has merit though.
        • HWR_14 5y ago
          It's not -NaN vs NaN. There are a bunch of NaN types, which are not related like that. It could (according to the spec) change "NaN: Attempt to arcsin value greater than 1" to "NaN: Zero divided by Zero operation"
      • im3w1l 5y ago
        Too late to edit now, but the floating point standard actually specifies that this is what abs should do.
• MontyCarloHall 5y ago
  It’s interesting how fairly complex bit twiddling hacks are well-known for integers, but even very simple but useful bit twiddles for floats (like this one) are obscure enough to warrant their own article. Of course, the most famous bit manipulation of floats is the fast inverse square root trick [0]. The bits of a float as an integer literal are proportional to its log2 value (plus a constant), which is handy for computing a reciprocal square root in logspace, which when converted back to a float gets exponentiated, yielding the answer (after a couple more refinement steps). If you actually take the time to manually hammer out the bitwise manipulations, the fast inverse square root is quite simple, but it is nonetheless regarded as black magic, likely due to the totally non-explanatory comments in the Quake source code. Funnily enough, directly following the fast inverse square root in the Quake source code is a function to compute absolute values by zeroing the float sign bit [1], just as described in the article. [0] https://en.wikipedia.org/wiki/Fast_inverse_square_root#Aliasing_to_an_integer_as_an_approximate_logarithm https://en.wikipedia.org/wiki/Fast_inverse_square_root#Alias... [1] https://github.com/id-Software/Quake-III-Arena/blob/dbe4ddb10315479fc00086f08e25d968b4b43c49/code/game/q_math.c#L574-L578 https://github.com/id-Software/Quake-III-Arena/blob/dbe4ddb1...
  • Y_Y 5y ago
    What if the twiddle wasn't obscure and the article was unwarranted?
    • MontyCarloHall 5y ago
      Given the amount of discussion this article has sparked on HN, I’d argue that as obvious as it might be, the technique is nonetheless obscure. The amount of highly experienced and accomplished programmers I’ve encountered who have no idea how floating point numbers work is astoundingly high. If a similar article were written about how shifting an integer to the right by one bit is equivalent to dividing it by two, I highly suspect it would attract no attention on this site, aside from a couple dismissive comments grousing about why such a basic fact needs its own article.
      • 5y ago
• andi999 5y ago
  Does anybody know a good reference on the minus 0 thing? How do you end up with it? Is 4-4=+0.0 and -4 +4=-0.0? Or is it different?
  • aaaaaaaaaaab 5y ago
    Both are exactly 0.0. Regarding signed zero, read this paper from Kahan: https://homes.cs.washington.edu/~ztatlock/599z-17sp/papers/branch-cuts-kahan-87.pdf https://homes.cs.washington.edu/~ztatlock/599z-17sp/papers/b...
  • gvx 5y ago
    The easiest way to get a signed zero is with a unary minus operation. That is, the expression -x produces -0.0 when x is an unsigned zero (so 0.0)
  • MontyCarloHall 5y ago
    No, those both yield +0. 0/(-x) would return -0, for all x > 0 Likewise, underflows on negative numbers would also return -0.
    • thaumasiotes 5y ago
      > 0/(-x) would return -0, for all x > 0 I find this one a little weird, but it seems to be true. The more normal way to get -0 would be to divide a positive number by negative infinity, or a negative number by positive infinity.
  • 63 5y ago
    From some quick testing, -1.0 * 0.0 = -0.0 and the order doesn't matter.
    • andi999 5y ago
      Nice. So -1.0*(4 - 4)=-0.0 but -4 + 4=0.0
• literallyaduck 5y ago
  Just convert to string then replace the "-" char with empty, then you can convert to the type you want. Sure performance suffers, but it gets you home by quitting time. Don't actually do this.
  • prof-dr-ir 5y ago
    "1e-3"
    • toxik 5y ago
      It’s exp abs, and it’s a beautiful feature.
  • Koshkin 5y ago
    I’ve seen this done. The guy didn’t have time to quit on his own.
• amelius 5y ago
  > After such interviews, there will be rumors about your company. It makes no sense to bring this up in interview questions. Just about every programmer knows that IEEE 754 contains some quirks. If you want to know the boring details, just look them up in the manual.
  • robocat 5y ago
    If the company only needs cowboy programming, corner cases don't matter. For some industries, ensuring your code doesn't fail on corner cases is very important, and questions about quirks show whether a candidate cares about corner cases and their comprehension of them. Given that the limitations of IEEE754 are the same in in virtually all programming languages, I suspect it is actually really good to use floating point quirks to probe a candidate on how skillful they are at programming. I roll my eyes at some stack overflow answers for their complete failure to consider even common corner cases like NaN and Infinity. I have certainly been caught out by my own mistakes in my own code with with integer and floating point errors, and I think I am more careful than most.
    • sharikous 5y ago
      Yes. For working, say, with physical simulations an experienced worker should know IEEE754. It does not take more than half a day of learning the standard to know how to approach the problem of the post with confidence. The real quirks lie elsewhere, in the hardware implementations and rounding rules (e.g. does FMA have the same precision of multiply-then-add? why does the order of the elements of a sum make a difference? etc.). And once you know these you can treat floating points with familiarity and expect your operations to be predictable to their last bit. If I were hiring for a developer of FDTD simulations I would expect them to be familiar with things like -0.0, subnormal numbers and NaN types and to be able to learn if necessary how to go around the murky stuff like rounding. Floats shouldn't be mysterious, they are at the end 16/32/64/80/128 bit variables with deterministic operations defined on them.
    • Akronymus 5y ago
      Of course corner cases matter. But as they are corner cases, you are very unlikely to just know them all from memory, so you would need to look them up anyways.
• togaen 5y ago
  Easy solution: switch to C++, use std::copysign
  • DerekL 5y ago
    Yes, using an existing implementation is a good idea, but why not just use std::abs?
    • ChrisLomont 5y ago
      Because, as the article explains, it likely has the flaw the article is about.
• deleted 5y ago
  [deleted]
• Sharlin 5y ago
  Computing the absolute value of a signed (fixed-size, two's complement) integer is not trivial either, because there is no positive i such that `abs(INT_MIN) == i`. Some languages like Java just give you `abs(INT_MIN) == INT_MIN` because: -100…000 = ~100…000 + 1 = 011…111 + 1 = 100…000 where ~ is the bitwise complement. Even worse, in C and C++ specifically, because overflow of signed integers is undefined behavior, so is `abs(INT_MIN)`! To be able to represent the absolute value, you need to either return the corresponding unsigned type (if your language has them), promote to a wider type, or return a tuple `(carry_bit, result)`.
  • nightcracker 5y ago
    This is why Rust has `abs`, `checked_abs`, `wrapping_abs`, `overflowing_abs`, `saturating_abs` and `unsigned_abs`. Checked returns a Result enum that is an error on overflow, wrapping silently wraps (as in your answer), overflowing wraps but has a boolean indicator whether a wrap has occurred, saturating bounds at the types limits rather than wrapping and unsigned abs always gives the correct result albeit as a different type. The unqualified abs panics on overflow on debug but silently wraps on release mode, like all Rust arithmetic code does by default.
• deleted 5y ago
  [deleted]
• Koshkin 5y ago
  In programming, the result of a comparison of floating point numbers in general and a comparison with zero in particular is problem (and scale) dependent. Some values that are close to zero are actually zero, within a certain margin of error (the “epsilon”). I wish computers directly operated on intervals instead of single points.
• wly_cdgr 5y ago
  What is this insane person doing when you can just if (value < 0) return -value; else if (value > 0) return value; else return +0.0
  • deleted 5y ago
    [deleted]
  • aw1621107 5y ago
    That drops NaNs, for one.
    • wly_cdgr 5y ago
      Good point
• BlissWaves 5y ago
  Alterantively one can use Math.abs().
  • jonas21 5y ago
    Not if you're writing Math.abs(). The motivation for the article is this change in OpenJDK, where they got a 10% performance improvement by switching from the single-branch implementation to the branchless one: https://github.com/openjdk/jdk/pull/4711 https://github.com/openjdk/jdk/pull/4711
• teddyh 5y ago
  Does Java not have signbit()?
  • tempodox 5y ago
    Or fabs(), like C?
    • fanf2 5y ago
      The article is about how the Java standard library implements its equivalent of fabs() and why it changed from a careful and clever comparison to bit twiddling
• Const-me 5y ago
  PC processors have bitwise instructions processing floats. When I need absolute value, I usually do it like that in C++: return _mm_andnot_pd( _mm_set1_pd( -0.0 ), vec );