Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Reciprocal Approximation with 1 Subtraction

news.ycombinator.com

Post reply on HN
Print view View original

21–30 of 73 posts

Re: Reciprocal Approximation with 1 Subtraction

#21

Post by Conscat »

dahart wrote: post #12

This code is technically UB in C++, right? [1] Has anyone run into a case where it actually didn’t work? Just curious. I’ve often assumed that if C++ compilers didn’t compile this code, all hell would break loose. It might be nice to start sharing modern/safe versions of this snippet & the Quake thing. Is using memcpy the only option that is safe in both C and C++? That always felt really awkward to me. [1] https://t…

A few years ago with GCC 10, I had some strange UD2 instructions (I think) inserted around some inline assembly that was fixed by replaced my `reinterpret_cast`s with `bit_cast`.

Re: Reciprocal Approximation with 1 Subtraction

#22

Post by imtringued »

Asooka wrote: post #17
dahart wrote: post #12

This code is technically UB in C++, right? [1] Has anyone run into a case where it actually didn’t work? Just curious. I’ve often assumed that if C++ compilers didn’t compile this code, all hell would break loose. It might be nice to start sharing modern/safe versions of this snippet & the Quake thing. Is using memcpy the only option that is safe in both C and C++? That always felt really awkward to me. [1] https://t…

It would be better if compilers were fixed. Current treatment of UB is insane. The default should be no UB and a pragma that lets you turn it on for specific parts. That used to be the case and some of the world's most performant software was written for compilers that didn't assume no pointer aliasing nor no integer overflow (case in point: Quake). The big problem, apart from "memcpy is a bit tedious to write", is t…

There is no point in talking with the people that worship UB for the sake of UB.

They don't understand that one of the biggest barriers to developers writing and adopting more C in their projects is the random jankiness that you get from the compilers. Instead they make C this elite thing for the few people who have read every single line of C code they themselves compiled and ran on their Gentoo installation. Stuff like having no bounds checks is almost entirely irrelevant outside of compute kernels. It doesn't get you much performance, because the branches are perfectly predictable. It merely reduces code size.

There is also the problem that the C development culture is uttlery backwards compared even to the semiconductor industry. If you want to have these ultra optimized release builds, then your development builds must scream when they encounter UB and it also means that no C program or library without an extensive test suite should be allowed onto any Linux distribution's package repository. Suddenly the cost of C programming appears to be unaffordably high.

Re: Reciprocal Approximation with 1 Subtraction

#23

Post by AlotOfReading »

A better value is 0x7eb504f3. You can follow that up with Newton-raphson to refine the approximation, or approximate the Newton-raphson too by multiplying 1.385356f*x.

I did this a few days ago in the approximate division thread: https://news.ycombinator.com/item?id=42481612#42489596

In some cases, it can be faster than hardware division.

Re: Reciprocal Approximation with 1 Subtraction

#24

Post by stephencanon »

stephencanon wrote: post #10
torusle wrote: post #7

There are couple of tricks you can do if you fiddle with the bits of a floating point value using integer arithmetic and binary logic. That was a thing back in the 90th.. I wonder how hard the performance hit from moving values between integer and float pipeline is nowadays. Last time I looked into that was the Cortex-A8 (first I-Phone area). Doing that kind of trick costed around 26 cycles (back and forth) due to pi…

There are basic integer operations in the FP/SIMD units on most CPUs, so there’s no generally need to “move back and forth” unless you need to branch on the result of a comparison, use a value as an address, or do some more specialized arithmetic.

(For that matter, though, most modern FP/SIMD units have a direct approximate-reciprocal instruction that is single-cycle throughput or better and much more accurate--generally around 10-12 bits, so there's no need for this sort of thing. See, e.g. FRECPE on ARM NEON and [V]RCPP[S/D] on x86.)

Re: Reciprocal Approximation with 1 Subtraction

#25

Post by rjeli »

LegionMammal978 wrote: post #15
dahart wrote: post #12

This code is technically UB in C++, right? [1] Has anyone run into a case where it actually didn’t work? Just curious. I’ve often assumed that if C++ compilers didn’t compile this code, all hell would break loose. It might be nice to start sharing modern/safe versions of this snippet & the Quake thing. Is using memcpy the only option that is safe in both C and C++? That always felt really awkward to me. [1] https://t…

Yes, most casts via pointers are formally UB in both C and C++, and you can induce weird behavior by compilers if you transmit casted pointers through a function boundary (see [0] for a standard example: notice how the write to *pf vanishes into thin air). Since people like doing it in practice, GCC and Clang have an -fno-strict-aliasing flag to disable this optimization, and the MSVC compiler doesn't use it in the f…

For C++, `bit_cast(0.f)` should be Well Defined, right? I'm curious, in C, is union-casting float->uint32_t also Perfectly Legal And Well Defined?

(I am not a C or C++ expert.)

Re: Reciprocal Approximation with 1 Subtraction

#26

Post by stouset »

LegionMammal978 wrote: post #16
dahart wrote: post #14

Earlier quoted context omitted.

And it’s always reliably optimized out in release builds, I assume?

On platforms thar require aligned loads and stores (not x86 nor ARM), a direct pointer cast sometimes uses an aligned load/store where a memcpy uses multiple byte loads/stores, even on a good compiler, since memcpy() doesn't require that the pointers are aligned. This can be mitigated by going through a local variable, but it gets pretty verbose.

Sounds like a good place for a macro?

Re: Reciprocal Approximation with 1 Subtraction

#27

Post by quanto »

A quick intuition: magic number 7e ffffff is negating by two's complement both the mantissa and exponent.

1. 7e: the first sig bit has to be zero to preserve the sign of the overall number.

2. ffffff: due to Taylor series 1/(1 + X) = 1 - X ..., negating gives the multiplicative inverse.

Although an IEEE float has a sign bit (thus 2's complement does not work on the float itself) but mantissa and the exponent individually work with 2's complement for different reasons. The exponent has a biased range due to being chopped by half; where as the mantissa has a biased range due to its definition and constant offset. The exponent's 1 offset (7e instead of 7f) is a bit more difficult to see at first -- the devil is in the details, but 2's complement is the basic intuition.

Re: Reciprocal Approximation with 1 Subtraction

#28

Post by somat »

Whenever I see these tricks(see also: the quake 3 fast inverse sqrt) involving using, not casting, but using integers as floats directly and floats as integers, I wonder if there is a way to do it without the jank.

Because what do you really want? some sort of exponent or exponent math right, some variant of the log function should work. is the problem is all the log functions are gated behind the function call interface. where as the subtract function is less heavy being behind the operator interface. or are they trying to use a floating point accelerated log aka floating point subtract?

Re: Reciprocal Approximation with 1 Subtraction

#29

Post by brudgers »

somat wrote: post #28

Whenever I see these tricks(see also: the quake 3 fast inverse sqrt) involving using, not casting, but using integers as floats directly and floats as integers, I wonder if there is a way to do it without the jank. Because what do you really want? some sort of exponent or exponent math right, some variant of the log function should work. is the problem is all the log functions are gated behind the function call inter…

Engineering mathematical calculations always looks like "jank." Take a look at Plauger's The C Standard Library. It is full of "magic" numbers.

But then again, representing irrational numbers in binary is inherently janky.

Re: Reciprocal Approximation with 1 Subtraction

#30

Post by ack_complete »

LegionMammal978 wrote: post #16
dahart wrote: post #14

Earlier quoted context omitted.

And it’s always reliably optimized out in release builds, I assume?

On platforms thar require aligned loads and stores (not x86 nor ARM), a direct pointer cast sometimes uses an aligned load/store where a memcpy uses multiple byte loads/stores, even on a good compiler, since memcpy() doesn't require that the pointers are aligned. This can be mitigated by going through a local variable, but it gets pretty verbose.

Some ARM CPUs do require aligned loads and stores, such as the Cortex-M0+ in a Raspberry Pi Pico.
Post reply on HN