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

41–50 of 73 posts

Re: Reciprocal Approximation with 1 Subtraction

#41

Post by gpderetta »

ryao wrote: post #40
LegionMammal978 wrote: post #15

Earlier quoted context omitted.

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…

There are two additional ways of making this work. The first is to allocate the memory using char a[sizeof(float)]. In C, char pointers may alias anything, so then you can do pointer conversions that would normally be undefined behavior and it should work. The other option is to use the non-standard __attribute__((__may_alias__)) on the pointer. By the way, using union types for this is technically undefined behavior…

The union trick is actually defined in C.

And note that while char can alias anything, the reverse is not true: i.e. you can't generally cast a char array to anything else and expect sensible behaviour. There are ways to make this work (placement new in C++ for example), but it is not a way to escape TBAA: if you store a float in char array you can't then cast it to int with impunity.

Re: Reciprocal Approximation with 1 Subtraction

#42

Post by atiedebee »

gpderetta wrote: post #41
ryao wrote: post #40

Earlier quoted context omitted.

There are two additional ways of making this work. The first is to allocate the memory using char a[sizeof(float)]. In C, char pointers may alias anything, so then you can do pointer conversions that would normally be undefined behavior and it should work. The other option is to use the non-standard __attribute__((__may_alias__)) on the pointer. By the way, using union types for this is technically undefined behavior…

The union trick is actually defined in C. And note that while char can alias anything, the reverse is not true: i.e. you can't generally cast a char array to anything else and expect sensible behaviour. There are ways to make this work (placement new in C++ for example), but it is not a way to escape TBAA: if you store a float in char array you can't then cast it to int with impunity.

To be more precise, it is defined since c99[0]. In c89 it was undefined, but type punning is the most used/sensible behaviour, so they changed it in c99.

[0]: https://en.cppreference.com/w/c/language/union

Re: Reciprocal Approximation with 1 Subtraction

#43

Post by gpderetta »

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.

On x86 there is sometimes (depending on the specific microarchitecture) an extra cycle additional latency when using an integer operation on a xmm register last used with a float operation.

I have seen it explained as the integer and foat ALUs's being physically distant and the forwarding network needing an extra cycle to transport the operands.

Re: Reciprocal Approximation with 1 Subtraction

#44

Post by gpderetta »

atiedebee wrote: post #42
gpderetta wrote: post #41

Earlier quoted context omitted.

The union trick is actually defined in C. And note that while char can alias anything, the reverse is not true: i.e. you can't generally cast a char array to anything else and expect sensible behaviour. There are ways to make this work (placement new in C++ for example), but it is not a way to escape TBAA: if you store a float in char array you can't then cast it to int with impunity.

To be more precise, it is defined since c99[0]. In c89 it was undefined, but type punning is the most used/sensible behaviour, so they changed it in c99. [0]: https://en.cppreference.com/w/c/language/union

Yes, it 2025, I thought that we could at least imply C99 when talking about plain C :).

I'm probably an optimist.

Re: Reciprocal Approximation with 1 Subtraction

#45

Post by dahart »

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…

Yes of course there’s a more graceful approach. You can use an actual divide instruction or routine instead of the bit-casting subtraction trick.

It’s not about interfaces. The point is that a single subtract is simpler math, and (probably) faster than a divide, and it gets you surprisingly close to the right answer. The reason it works is subtracting two exponents is a subtraction in log space which is equivalent to a divide in linear space.

People don’t use this trick in practice that much if at all, especially these days with GPUs that do reciprocals and square roots in hardware, it’s just an interesting thing to know about that helps solidify our understanding of floating point numbers and logarithms.

Re: Reciprocal Approximation with 1 Subtraction

#46

Post by ryao »

atiedebee wrote: post #42
gpderetta wrote: post #41

Earlier quoted context omitted.

The union trick is actually defined in C. And note that while char can alias anything, the reverse is not true: i.e. you can't generally cast a char array to anything else and expect sensible behaviour. There are ways to make this work (placement new in C++ for example), but it is not a way to escape TBAA: if you store a float in char array you can't then cast it to int with impunity.

To be more precise, it is defined since c99[0]. In c89 it was undefined, but type punning is the most used/sensible behaviour, so they changed it in c99. [0]: https://en.cppreference.com/w/c/language/union

That is a common misconception. DR 283 is a suggestion for an amendment that was filed 3 years after C99 was published:

https://open-std.org/jtc1/sc22/wg14/www/docs/dr_283.htm

It is not part of C99. It also is not part of the C standard since no subsequent C standard adopted it according to the GCC developers:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118141#c13

A read of the C11 standard draft, which would have this amendment if it were accepted by the C standards committee, shows that this has not been added:

https://open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf

Type punning via union types is therefore undefined behavior unless your compiler implements an extension to define it like GCC and Clang do.

Re: Reciprocal Approximation with 1 Subtraction

#47

Post by ryao »

gpderetta wrote: post #44
atiedebee wrote: post #42

Earlier quoted context omitted.

To be more precise, it is defined since c99[0]. In c89 it was undefined, but type punning is the most used/sensible behaviour, so they changed it in c99. [0]: https://en.cppreference.com/w/c/language/union

Yes, it 2025, I thought that we could at least imply C99 when talking about plain C :). I'm probably an optimist.

It does not matter. The C99 standard does not define this behavior:

https://news.ycombinator.com/item?id=42568271m

Re: Reciprocal Approximation with 1 Subtraction

#48

Post by mbitsnbites »

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…

The proper solution is to use std::bit_cast in modern C++ or otherwise use memcpy, and of course know what you're doing.

Some things that could mess with you:

* Floating-point endianity is not the same as integer endianity.

* Floating-point alignment requirements differ from integer alignment requirements.

* The compuler is configured to use something else than 32-bit binary32 IEEE 754 for the type "float".

* The computer does not use two's complement arithmetic for integers.

In practice, these are not real problems.

Re: Reciprocal Approximation with 1 Subtraction

#49

Post by mbitsnbites »

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 is also the case with machines that lack FP support, like some ARM Cortex M variants.

Re: Reciprocal Approximation with 1 Subtraction

#50

Post by mbitsnbites »

ncruces wrote: post #39

I collected this, and a few others here: https://github.com/ncruces/fastmath/blob/main/fast.go It's in Go, but ports easily to other languages. See also: https://stackoverflow.com/questions/32042673/optimized-low-a...

Excellent! Will have a look.
Post reply on HN