Creating invariant floating-point accumulators
solidpixel.github.io
Creating invariant floating-point accumulators
1–10 of 31 posts
Re: Creating invariant floating-point accumulators
#2I'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 efficient on modern machines, but could it be preventing us from applying other important high level optimizations to our programs due to its lack of associativity? A richer algebraic structure should always be amenable to a richer set of potential optimizations.
---
I've asked a question that is very much related to that topic on the programming language subreddit:
"Could numerical operations be optimized by using algebraic properties that are not present in floating point operations but in numbers that have infinite precision?"
https://www.reddit.com/r/ProgrammingLanguages/comments/145kp...
The responses there might be interesting to some people here.
Re: Creating invariant floating-point accumulators
#3I'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…
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.
Re: Creating invariant floating-point accumulators
#4I'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…
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.
Re: Creating invariant floating-point accumulators
#5I'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…
> Could numerical operations be optimized by using algebraic properties that are not present in floating point operations but in numbers that have infinite precision?
... are you not aware of -ffast-math? There are several fast-math optimizations that are basically "assume FP operations have this algebraic property, even though they don't" (chiefly, -fassociative-math assumes associative and distributive laws hold).
Re: Creating invariant floating-point accumulators
#6Earlier 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.
Really? That seems nuts. How do they index an array?
Re: Creating invariant floating-point accumulators
#7Seems crazy to try to paper over hardware implementation differences in software. Some org should be standardizing floating point intrinsics
Re: Creating invariant floating-point accumulators
#8I'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
Re: Creating invariant floating-point accumulators
#9Earlier 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?
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 javascript anymore.
Like many things in javascript it's a bit cursed but it does work.
Re: Creating invariant floating-point accumulators
#10Earlier 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?
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.