[modulovalue]

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 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.

[bee_rider]

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.

[daemin]

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.

[baq]

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

[bee_rider]

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

[eigenket]

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.

[cryptonector]

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).

[zokier]

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

[jcranmer]

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.

[recursive]

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

[cryptonector]

floor() enters the chat

[eigenket]

It would be quite funny if that was how it worked, but it just checks to see if the exponent is 0 and then uses the mantisa as the index if so.

[hansvm]

> 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?

You're always welcome to use a weaker notion of associativity than bitwise equality (e.g., -ffast-math pretends many operations are associative to reorder them for speed, and that only gives approximately correct results on well-conditioned problems).

In general though, yes, such a limit does exist. Imagine, for the sake of argument, an xxx.yyy fixed-point system. What's the result of 100 * 0.01 * 0.01? You either get 0.01 or 0, depending on where you place the parentheses.

The general problem is in throwing away information. Trashing bits doesn't necessarily mean your operations won't be associative (imagine as a counter-example the infix operator x+y==1 for all x,y). It doesn't take many extra conditions to violate associativity though, and trashed bits for addition and multiplication are going to fit that description.

How do you gain associativity then? At a minimum, you can't throw information away. Your fast machine operations use an unbounded amount of RAM and don't fit in registers. Being floating-point vs fixed-point only affects that conclusion in extremely specialized cases (like only doing addition without overflow -- which sometimes applies to the financial industry, but even then you need to think twice about the machine representation of what you're doing).

[modulovalue]

> How do you gain associativity then? At a minimum, you can't throw information away.

That's an interesting perspective that I haven't considered before, thank you.

Now I'm wondering, could we throw away some information in just the right way and still maintain associativity? That is, it doesn't seem like throwing information away is fundamentally what's preventing us from having an associative operation, since we can throw information away and still maintain associativity by, for example, converting each summand to a 0 and adding them, and that operation would be associative. However, we would have thrown all information away, which is not useful, but we would have an associative operation.

[zokier]

Herbie, a fp optimizer, might be of interest to you

https://herbie.uwplse.org/

[tialaramex]

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?

[jcranmer]

> 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).