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

Creating invariant floating-point accumulators

solidpixel.github.io

Post reply on HN
Print view View original

11–20 of 31 posts

Re: Creating invariant floating-point accumulators

#11

Post by tialaramex »

zokier wrote: post #8
modulovalue wrote: post #2

I'm still wondering if there could exist an alternative world where efficient addition over decimal numbers that we developers use on a day to day basis is associative. Is that even possible or is there perhaps some fundamental limit that forces us to trade associativity for performance? It seems to me that non associative floating point operations force us into a local maximum. The operation itself might be efficien…

Herbie, a fp optimizer, might be of interest to you https://herbie.uwplse.org/

There's a link in there to future directions for Herbie which talks about the intriguing idea of out-sourcing the translation of a high level "I want to do this real number math" to the lower level "Here's some floating point arithmetic" via Herbie.

That is, the physicist writes the two line equation they want for electromagnetic force into their program, the same way they'd write a for-each style loop in the program if that's what they needed.

Obviously the CPU doesn't understand how to compute the appropriate approximation for this electromagnetic force equation, but nor does it understand how to iterate over each item in a container. Tools convert the for-each loop into machine code, why shouldn't other, smart, tools convert the physicist's equation into the FP instructions ?

Today the for-each loop thing just works, loads of programming languages do that, if a language can't do it (e.g. C) that's because it is old or only intended for experts or both.

But every popular language insists that physicist should laboriously convert the equation into the code to compute an approximation, which isn't really their skill set, so why not automate that problem?

Re: Creating invariant floating-point accumulators

#12

Post by cryptonector »

bee_rider wrote: post #6
daemin wrote: post #4

Earlier quoted context omitted.

It could also be that a lot of languages don't actually have integer types and just use a 64bit floating point number instead - ala JavaScript etc.

Really? That seems nuts. How do they index an array?

floor() enters the chat

Re: Creating invariant floating-point accumulators

#13

Post by cryptonector »

eigenket wrote: post #9
bee_rider wrote: post #6

Earlier quoted context omitted.

Really? That seems nuts. How do they index an array?

They index them with doubles, they do the same with loop variables. As long as your integer is less (in absolute value) than about 2^53 (because they have 53 bit mantisas) you can represent it exactly with a double. 2^53 is 2^(10*5+3) so even if you're indexing individual bytes that many indexes works until you need to index into an array with 8 petabytes of data in it, at which point you're probably not using javasc…

Plus 53-bit indices exceed the amount of memory that many 64-bit architectures can address (x86_64 is 48 bits, ARM is either 48 or 52 bits).

Re: Creating invariant floating-point accumulators

#15

Post by recursive »

jcranmer wrote: post #10
bee_rider wrote: post #6

Earlier quoted context omitted.

Really? That seems nuts. How do they index an array?

In practice, JavaScript has 32-bit signed integers and 64-bit floating-point numbers as distinct types (look into any JS engine, and you'll see a distinction between the two being made), even if they both surface as a single "number" type. You can also see the distinction in the way that bitwise operators coerce numbers to integers, even though the arithmetic operators coerce to floats in theory.

The spec describes the behavior of converting to and from 32-bit signed for the purposes of the bitwise operators. https://tc39.es/ecma262/#sec-toint32

Re: Creating invariant floating-point accumulators

#16

Post by waynecochran »

Invariance w floating point arithmetic seems like a fool's errand. If the numbers one is working with are roughly on the same order of magnitude than I would consider integer / fixed point instead. You get the same results in this case (as long as you are careful).

Re: Creating invariant floating-point accumulators

#17

Post by boulos »

This seems to keep coming up, and I see confusion in the comments. There is a standard: IEEE 754-2008. There are additional things people add like approximate reciprocals and approximate sqrt. But if you don't use those, and you don't make an association error, you get consistent results.

The question here with association for summation is what you want to match. OP chose to match the scalar for-loop equivalent. You can just as easily make an 8-wide or 16-wide "virtual vector" and use that instead.

I suspect that an 8-wide virtual vector is the right default for people currently, since systems since Haswell support it, all recent AMD, and if you're using vectorization, you can afford to pay some overhead on Arm with a double-width virtual vector. You don't often gain enough from AVX512 to make the default 16-wide, but if you wanted to focus on Skylake+ (really Cascadelake+) or Genoa+ systems, it would be a fine choice.

Re: Creating invariant floating-point accumulators

#18

Post by baq »

daemin wrote: post #4
bee_rider wrote: post #3

Earlier quoted context omitted.

I’m not 100% clear on what you are asking, but integer addition is associative, right? (With quibbles about over/underflow of course). If you have some limited range of decimal numbers that you care about, you can always just use integers and account for the shifted decimal places as needed. Floats are mostly for when you need that dynamic range.

It could also be that a lot of languages don't actually have integer types and just use a 64bit floating point number instead - ala JavaScript etc.

worth mentioning - js has had a built-in bigint type for quite a while now:

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

the problem is it's marginally useful, since everyone expects number

Re: Creating invariant floating-point accumulators

#20

Post by zokier »

cryptonector wrote: post #13
eigenket wrote: post #9

Earlier quoted context omitted.

They index them with doubles, they do the same with loop variables. As long as your integer is less (in absolute value) than about 2^53 (because they have 53 bit mantisas) you can represent it exactly with a double. 2^53 is 2^(10*5+3) so even if you're indexing individual bytes that many indexes works until you need to index into an array with 8 petabytes of data in it, at which point you're probably not using javasc…

Plus 53-bit indices exceed the amount of memory that many 64-bit architectures can address (x86_64 is 48 bits, ARM is either 48 or 52 bits).

x86-64 is 57 bits these days https://en.wikipedia.org/wiki/Intel_5-level_paging
Post reply on HN