6 ms·

Why aaaaaa cannot be optimized to (aaa)(aaa)?

153 points by ciupicri 15y ago

pkulak 15y ago
Because it brings down Stack Overflow?
nbpoole 15y ago
Google Cache version: http://webcache.googleusercontent.com/search?q=cache%3Ahttp%3A%2F%2Fstackoverflow.com%2Fquestions%2F6430448%2Fwhy-aaaaaa-cannot-be-optimized-to-aaaaaa http://webcache.googleusercontent.com/search?q=cache%3Ahttp%...
pixelbath 15y ago
The short answer: Because floating point math is not associative. http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems http://en.wikipedia.org/wiki/Floating_point#Accuracy_problem...
dougws 15y ago
When I first read the headline, I definitely thought that was a regular expression which could be "optimized" to a+. I guess I'm more inclined to read "*" as the Kleene operator than as multiplication...
- rjh29 15y ago
  Me too, but that's probably because of all those regular expressions like 'aa* b*' I had to read at uni :)
- Natsu 15y ago
  I'm glad to know that I'm not alone in doing this.
- leif 15y ago
  I think you need a font where asterisk is not superscripted. Try Inconsolata.
zheng 15y ago
As a user of Stack Overflow only when google brings me there, I'm curious as to why the answer received so many upvotes? It is certainly a good answer, but the score seems disproportional to the utility.
- cruise02 15y ago
  Because it's on the front page of both Hacker News and reddit/r/programming.
- retube 15y ago
  I just feel sorry for the guy that answered. He's got +685 upvotes at time of writing and no dvs so he should have ~ 7,000 points from this, but apparently SO imposes a daily cap of 200.
  - davweb 15y ago
    I think the Daily Cap is intended for situations just like this. So if you see someone with 5k+ reputation it's a good sign they've given good answers to a fair few questions (or asked good questions) over a period of time rather than just got lucky with a question that found its way on to Twitter. Because reputation entitles you do certain things like close questions SO is careful about how you can earn it.
    - retube 15y ago
      Yeah makes sense. Still, I'd be a bit gutted :)
kaiwetzel 15y ago
In numerical analysis class numerical stability was a major theme[1]. It was very definitely eye-opening how quickly rounding/truncation errors can bite you in seemingly trivial situations! On the other hand, if I have a function that works on parameters in a specified range (say, 0.0 to 1.0) and returns results which is supposed to be correct to a specified accuracy I would love to have the compiler do all the possible optimizations without having to specify a compiler flag (doing so for, say, just a single function can be quite annoying!). Maybe approaches like Haskell's type inference will, eventually, produce significantly faster code because they can do things like this? In a somewhat related case, it would be awesome if the compiler recognized properties like associativeness, distributiveness, commutitiveness of composite functions and rearange things optimally for performance. It's really nice to see so much development in languages and compilers at the moment (llvm, javascript, functional languages like Haskell, etc.) :°) [1] http://en.wikipedia.org/wiki/Numerical_stability http://en.wikipedia.org/wiki/Numerical_stability
- pnathan 15y ago
  David Buehler's mixed-point computations can do that, I believe.
- ori_b 15y ago
  So you want something like GCC's -funsafe-math flag.
deleted 15y ago
[deleted]
dspillett 15y ago
It can. But only for integer data types. As already pointed out, for floating point data types the two versions could (and probably will) result in slightly different answers due to rounding issues.
- Dylan16807 15y ago
  Why does it being different matter? Compilers can do all kinds of things that change answers.
  - ori_b 15y ago
    They can't do it on code that doesn't invoke undefined behavior. This is not undefined behavior.
    - Dylan16807 15y ago
      Obviously they can't do whatever they want but they can decide if they want to store variables in registers or main memory, they can change the order of a variety of operations, etc. Does C specify order of evaluation with multiplication? If so I wasn't aware of that. But you'll still have some compilers giving you 32 bit precision on intermediate results and some giving you 80 bits.
      - ori_b 15y ago
        > they can decide if they want to store variables in registers or main memory, they can change the order of a variety of operations, etc. As long as they follow the "as if rule", which states that any transformations that is done to code that does not invoke undefined behavior will produce the same final result as if the transformations were not done. Reordering floating point multiplications does not follow this rule. (Watching stuff in a debugger doesn't count for this rule)
        Dylan16807 15y ago
        1. Are you saying that multiplications have a specified order? I asked that but didn't get a response. 2. The compiler is allowed to either leave the float inside the FPU or store it back to main memory after each operation, is it not? These give different results. Somewhere around here I have a chart of the differences in floating point outputs of different GCC versions. And no, fastmath is not on.
kleiba 15y ago
Is this on the front page of HN because of the many upvotes it got, or did it get the many upvotes because it is on the front page of HN?
- Wilduck 15y ago
  Almost certainly the latter.
- sorbus 15y ago
  It got many upvotes (or a small number of upvotes directly after being posted) which pushed it to the front page of HN, where it gets greatly increased visibility and hence more upvotes.
hunterp 15y ago
Wow....the boundary between mathematics and assembly code.
bxc 15y ago
There are other ways of dealing with "fake real numbers" (which is what doubles are) One example is interval arithmetic. http://en.wikipedia.org/wiki/Interval_arithmetic http://en.wikipedia.org/wiki/Interval_arithmetic None of them seem very mainstream: the predominant thinking is that floats are "the right way" to badly approximate real numbers, that works well enough except when you're working with pounds and pence, when "everyone" knows the right way is to use fixed point... That's not going to help the above associativity problem, but it fits in the theme of "LAAAA LAAAA LAAAA lets gloss over the bits of floating point that don't follow the rules"

Why a*a*a*a*a*a cannot be optimized to (a*a*a)*(a*a*a)?

153 points by ciupicri 15y ago

Because it brings down Stack Overflow?

Google Cache version: http://webcache.googleusercontent.com/search?q=cache%3Ahttp%3A%2F%2Fstackoverflow.com%2Fquestions%2F6430448%2Fwhy-aaaaaa-cannot-be-optimized-to-aaaaaa http://webcache.googleusercontent.com/search?q=cache%3Ahttp%...

pixelbath 15y ago

The short answer: Because floating point math is not associative. http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems http://en.wikipedia.org/wiki/Floating_point#Accuracy_problem...

dougws 15y ago

When I first read the headline, I definitely thought that was a regular expression which could be "optimized" to a+. I guess I'm more inclined to read "*" as the Kleene operator than as multiplication...

rjh29 15y ago
Me too, but that's probably because of all those regular expressions like 'aa* b*' I had to read at uni :)
Natsu 15y ago
I'm glad to know that I'm not alone in doing this.
leif 15y ago
I think you need a font where asterisk is not superscripted. Try Inconsolata.

zheng 15y ago

As a user of Stack Overflow only when google brings me there, I'm curious as to why the answer received so many upvotes? It is certainly a good answer, but the score seems disproportional to the utility.

cruise02 15y ago
Because it's on the front page of both Hacker News and reddit/r/programming.
retube 15y ago
I just feel sorry for the guy that answered. He's got +685 upvotes at time of writing and no dvs so he should have ~ 7,000 points from this, but apparently SO imposes a daily cap of 200.
- davweb 15y ago
  I think the Daily Cap is intended for situations just like this. So if you see someone with 5k+ reputation it's a good sign they've given good answers to a fair few questions (or asked good questions) over a period of time rather than just got lucky with a question that found its way on to Twitter. Because reputation entitles you do certain things like close questions SO is careful about how you can earn it.
  - retube 15y ago
    Yeah makes sense. Still, I'd be a bit gutted :)

kaiwetzel 15y ago

In numerical analysis class numerical stability was a major theme[1]. It was very definitely eye-opening how quickly rounding/truncation errors can bite you in seemingly trivial situations! On the other hand, if I have a function that works on parameters in a specified range (say, 0.0 to 1.0) and returns results which is supposed to be correct to a specified accuracy I would love to have the compiler do all the possible optimizations without having to specify a compiler flag (doing so for, say, just a single function can be quite annoying!). Maybe approaches like Haskell's type inference will, eventually, produce significantly faster code because they can do things like this? In a somewhat related case, it would be awesome if the compiler recognized properties like associativeness, distributiveness, commutitiveness of composite functions and rearange things optimally for performance. It's really nice to see so much development in languages and compilers at the moment (llvm, javascript, functional languages like Haskell, etc.) :°) [1] http://en.wikipedia.org/wiki/Numerical_stability http://en.wikipedia.org/wiki/Numerical_stability

pnathan 15y ago
David Buehler's mixed-point computations can do that, I believe.
ori_b 15y ago
So you want something like GCC's -funsafe-math flag.

deleted 15y ago

[deleted]

dspillett 15y ago

It can. But only for integer data types. As already pointed out, for floating point data types the two versions could (and probably will) result in slightly different answers due to rounding issues.

Dylan16807 15y ago
Why does it being different matter? Compilers can do all kinds of things that change answers.
- ori_b 15y ago
  They can't do it on code that doesn't invoke undefined behavior. This is not undefined behavior.
  - Dylan16807 15y ago
    Obviously they can't do whatever they want but they can decide if they want to store variables in registers or main memory, they can change the order of a variety of operations, etc. Does C specify order of evaluation with multiplication? If so I wasn't aware of that. But you'll still have some compilers giving you 32 bit precision on intermediate results and some giving you 80 bits.
    - ori_b 15y ago
      > they can decide if they want to store variables in registers or main memory, they can change the order of a variety of operations, etc. As long as they follow the "as if rule", which states that any transformations that is done to code that does not invoke undefined behavior will produce the same final result as if the transformations were not done. Reordering floating point multiplications does not follow this rule. (Watching stuff in a debugger doesn't count for this rule)
      - Dylan16807 15y ago
        1. Are you saying that multiplications have a specified order? I asked that but didn't get a response. 2. The compiler is allowed to either leave the float inside the FPU or store it back to main memory after each operation, is it not? These give different results. Somewhere around here I have a chart of the differences in floating point outputs of different GCC versions. And no, fastmath is not on.

kleiba 15y ago

Is this on the front page of HN because of the many upvotes it got, or did it get the many upvotes because it is on the front page of HN?

Wilduck 15y ago
Almost certainly the latter.
sorbus 15y ago
It got many upvotes (or a small number of upvotes directly after being posted) which pushed it to the front page of HN, where it gets greatly increased visibility and hence more upvotes.

hunterp 15y ago

Wow....the boundary between mathematics and assembly code.

bxc 15y ago

There are other ways of dealing with "fake real numbers" (which is what doubles are) One example is interval arithmetic. http://en.wikipedia.org/wiki/Interval_arithmetic http://en.wikipedia.org/wiki/Interval_arithmetic None of them seem very mainstream: the predominant thinking is that floats are "the right way" to badly approximate real numbers, that works well enough except when you're working with pounds and pence, when "everyone" knows the right way is to use fixed point... That's not going to help the above associativity problem, but it fits in the theme of "LAAAA LAAAA LAAAA lets gloss over the bits of floating point that don't follow the rules"