Pages: 1 [2] 3   Go Down
Author Topic: Very strange behavior from floor()  (Read 2542 times)
0 Members and 1 Guest are viewing this topic.
Offline Offline
Newbie
*
Karma: 0
Posts: 9
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset


But my main question is: how come the Arduino shows a result so absurd, when the same program, running on a very similar environment (ok, it's another CPU, but in both cases not only the compiler but *also* the C library comes from the nice GNU folks) shows a much more reasonable answer? Aren't both supposed to implement standard IEE-754 floating-point 32-bit arithmetic?


The Arduino gets it right, 8320 / 1000 give a binary mantissa of 1.00001010001111010111000 which represents the decimal value 8.3199996948, which should print out to 7dp as 8.3199997

I don't think you actually read (or understood) the post you are replying to...


Quote
Thanks for the very detailed response; I tried your program here on my Ubuntu desktop and got:

   floor  ((8.320000 * 1000)/1000) = 8.319000
   floorf ((8.320000 * 1000)/1000) = 8.320000

No you didn't, you perhaps tried:
Code:
  floor (8.320000 * 1000) / 1000.0
  floor (8.320000 * 1000) / 1000.0
Why not do the right thing and force using _single_ floats and then print enough digits:
Code:
  printf ("%2.10f\n", (float) floorf  (8.320000 * 1000) / 1000.0f) ; // = 8.319000
And you'll see C single floats are the same on both systems.

What you propose above is completely different than the issue at hand... again, I don't think you have really read (our understood) what I posted. I suggest you read the original posts (again, if need be).

BTW, we are *far* away from the original FP issues which seems to be the basis for your misunderstanding... Read the rest of the thread and you will see that it seems we actually found a bona fide avr-gcc bug, so your comments above are not only wrong, but also irrelevant...

But thanks for your attempt to help anyway.
Logged

0
Offline Offline
Shannon Member
****
Karma: 214
Posts: 12424
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

On the contrary I believe I've understood what's going on and there isn't any compiler bug or big issue with the Arduino and the Linux C implementations being different either.

A (non-ANSI) C implementation can choose whether the default float is single or double and can elect not to implement double floats.  The same goes for the size of integers, int can be 16 or 32 or 64 (or 93 if you want) bits.  AVR-GCC does not claim to be ANSI compliant - indeed it couldn't fit on the smaller chips if it was I suspect.

Show me which piece of code mentioned in this thread produces a different result when optimizations are switched on and off?  I can't see that there is any...

Also show me code that prints single float value 8320.0f/1000.0f differently on Linux and Arduino when the same number of decimal places are specified...

So if the hoo-hah is about the fact that AVR-GCC isn't ANSI compliant, its a valid gripe, but its not a bug.
Logged

[ I won't respond to messages, use the forum please ]

USA
Online Online
Sr. Member
****
Karma: 17
Posts: 382
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Much ado about nothing new.  The Wikipedia article on "floating point" describes a number of floating point calculation anomalies, and has this quote:
Quote
The fact that floating-point numbers cannot precisely represent all real numbers, and that floating-point operations cannot precisely represent true arithmetic operations, leads to many surprising situations.
Every computer science text I've ever seen has warned about expecting floating point calculations to be absolutely precise.  It may surprise you to know it, but you're not the first to uncover an issue like this one.

Speaking qualitatively, you're defining a value whose precision is beyond the capacity of 32-bit floating point to represent.  From http://arduino.cc/it/Reference/Float:
Quote
Floats have only 6-7 decimal digits of precision. That means the total number of digits, not the number to the right of the decimal point.
You're asking it to give you meaningful results to 8 decimal digits of precision.  This platform wasn't built for that, and its developers tell you so quite clearly.

Quantitatively, here's what happens:  8.3199996, as a 32-bit FP number, has sign bit 0, exponent 3, offset exponent 82H, mantissa 851EB8H - 051EB8H, with the MSB suppressed - and an FP representation of 41051EB8H.  That representation isn't exact, and every number between 8.3199993 and 8.3200001 has the same representation.   1000 has sign bit 0, exponent 9, offset exponent 88H, mantissa FA0000H - 7A0000H with sign bit suppressed - and an FP representation of 447A0000H.  Because 1000 is a reasonably-sized integer, the representation is exact.  Multiplying them yields sign bit 0, exponent 12, mantissa 103FFFFH with 011B following.  That multiplication overflows the 24-bit mantissa space, so the exponent bumps to 13, offset exponent 8EH, and the mantissa shifts to 81FFFFH with 1011B following.  That rounds up to 820000H, and results in an FP representation of 46020000H, which is the 32-bit FP representation of 8320, exactly.  floor(8320) is, well, 8320.  Dividing 8320 by 1000 yields 8.320, and its 32-bit FP representation is, as described above, 41051EB8H - identical to the representation of 8.3199996.  When you ask for that number with seven digits after the decimal, you get what you got, and it's correct within the well-known limits of floating point.

So, you got exactly the result that you could expect with a 32-bit floating point engine.  There are no optimization quirks, no bugs, no problems with the compiler, and everything is kosher.

I'm well aware of how computers do arithmetic ...
That's great, because it means that you can work out for yourself exactly how this result is calculated, and quantitatively demonstrate in this forum what, if anything, is wrong.

Now I don't know much AVR assembly language, but this *surely* doesn't look like floor() is being called... let's not even talk about the multiplication and division operations being performed!!!
We can't tell what code led to the *.s files you quoted, but, assuming that it's the code from your original post, there are some good reasons why the program wouldn't call floor(), or do any other arithmetic.  You define x, and never change it.  The optimizer might well decide, correctly, that x makes more sense as a constant.  That would make x*1000.0, float(x*1000.0), and float(x*1000.0)/1000.0 into constants as well.  It's likely that the compiler did the math itself, and just plugged the results - in 32-bit floating point - into the output code.  For this program, that's valid optimization, without fault.

Summarizing:  You gave the program a number - 8.3199996 - that it finds indistinguishable from 8.32, asked it to distinguish between them, and complained when it couldn't tell the difference.  If you need to reliably discern differences between numbers that differ in the eighth significant decimal digit, you've selected the wrong platform.  The Arduino does other things very well, but it doesn't claim to be a floating point calculation engine - in fact, it claims that it's not.  If you have to get exact results using floor() for every possible number, then floating point isn't your vehicle either - a 64-bit floating point engine will show the same kinds of anomalies, just less frequently and further downstream from the decimal point.  Maybe you can buy or program something to work in BCD.  The fault, dear Brutus, is not in your compiler, but in yourself.

Summarizing some of the histrionic statements that have been made in this thread:
Quote
Seriously now, this is one EGREGIOUS compiler error... HOW can one trust ANYTHING coming out of such a compiler? And more importantly, what is the solution? Working with the optimizer turned off all the time? If so, where can I purchase an additional 512KB of flash for my Arduino? ;-/
Full of sound and fury, signifying nothing.
                                                              


« Last Edit: August 18, 2012, 11:37:44 pm by tmd3 » Logged

Left Coast, CA (USA)
Offline Offline
Brattain Member
*****
Karma: 361
Posts: 17301
Measurement changes behavior
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
So, you got exactly the result that you could expect with a 32-bit floating point engine.  There are no optimization quirks, no bugs, no problems with the compiler, and everything is kosher.

 All kosher, except of course the OP's original expectations. Often when a one's expectations are not met one cries foul (or bug, or not fair, or whatever). Thanks for the detailed explanation. I've always avoided floating point math if at all possible when using microcontrollers. I usually find I can just use longs integers with a little scaling magic and don't have near the suprises one can have with FP variables and calculations.

NaN my ass.  smiley-wink

Lefty

Logged

Ayer, Massachusetts, USA
Offline Offline
Edison Member
*
Karma: 54
Posts: 1857
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Unless you are going to turn off all builtins (-fno-builtin), or just the floor builtin (-fno-builtin-floor), the compiler will always optimize the floor function if the argument is constant.  As I and others have mentioned, on Arduino, since doubles are hardwired to be the same as 32-bit, it will act like the floorf function on your workstation.
Logged

Rapa Nui
Offline Offline
Edison Member
*
Karma: 60
Posts: 2086
Pukao hats cleaning services
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

What Every Computer Scientist Should Know About Floating-Point Arithmetic
http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html

What Every Programmer Should Know About Floating-Point Arithmetic
http://floating-point-gui.de/


« Last Edit: August 20, 2012, 04:15:32 pm by pito » Logged

Dallas, Texas
Offline Offline
God Member
*****
Karma: 31
Posts: 887
Old, decrepit curmugeon
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

So, you got exactly the result that you could expect with a 32-bit floating point engine.  There are no optimization quirks, no bugs, no problems with the compiler, and everything is kosher.

I would suggest that you look at the optimized assembler produced from the code the OP posted...  It is clearly not calling the floor function.  The issue, in this case, isn't the accuracy or lack thereof, of the floating point calculation.  By optimizing away the details of the calculation, the results would remain identical--which is what the OP found and couldn't understand.

I personally don't think this quirk of the optimizer is a bug, but it did produce a counter-intuitive result in this case.  One of the drawbacks to using a high level compiler, rather than machine code...

Logged

New true random number library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version 1.0.1

Dallas, Texas
Offline Offline
God Member
*****
Karma: 31
Posts: 887
Old, decrepit curmugeon
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

I am not altogether convinced that it is an error.

Ouch! Really?  smiley-eek-blue

Quote
The problem with compiler optimizations is that to maximize effectiveness in 95% of the cases they end up having to make these kind of errors...  Typically the more you try to code the optimizer so that it eliminates these type of errors the more you reduce the optimizers efficiency in the majority of cases...

IMHO, a compiler's first responsibility is to produce *correct* code... to produce *fast* code is but a distant second.

Quote
So, in my opinion, this may be more of an undocumented 'feature', rather than a 'bug'

I'm sorry, but I do not agree with you... I think this could be defended *if* we were talking about some optional, *extreme* level of optimization like -O3 or somesuch. For gawds sake, we are talking here about a measly -Os, which basically means (or so I understood from reading the manpage) just -O2 with the potentially size-increazing optimizations disabled... -O2 is supposed to be mostly safe, if I'm understanding things correctly.

But you got the "undocumented" part right: I just checked cc.gnu.org/bugzilla and could not find anything similar to that.

Quote
The solution is really simple, leave optimizations on, but code in such a way that you verify assumptions (I like the assert macro).

Begging your pardon for my insolence, sir, but as you have already proved to be much more knowledgeable than me in this regard: I use asserts a lot, but I can't see how it would be possible to code an assert() for the above case... would you care to provide an example of how it could be done (again, for the above case)?

In the general case, let's not forget that the assert expression is code itself, and so is subject to be mangled by the compiler/optimizer right along with the code it's supposed to be verifying...

Quote
And then anytime a section doesn't appear to be working as expected look at the assembly output and see what the compiler is producing.

This is kinda impractical when we are working with a many thousands LOC long project that's being ported from another non-AVR processor in the first place...

Quote
Or you can just code in assembler directly is you are a masochist! smiley

Well, if I'm to check the compiler's generated assembly code all the time I suspect such chicanery, maybe it would be easier to dispense with it altogether and just code in assembler all the time... :-/

If you want the compiler to always produce 100% code, then you must code in assembler and make yourself the compiler...  If you want something close to 100% correct code, then simply choose to turn the optimizer off...  The optimizers are there for the same reason that compilers exist...  To make programmers more productive.  BTW, this is only undocumented because you are unfamiliar with the language.  One of the drawbacks that easy to use environments create is that by nature of their ease of use the folks working with them don't have the same level of understanding of the tools as do the ones who created those tools.

Quote
This is kinda impractical when we are working with a many thousands LOC long project that's being ported from another non-AVR processor in the first place...

It is not impractical...  It is the nature of the process of debugging, regardless of language.  If a computer isn't doing what you expect, then one of your assumptions is wrong.  In this case you were wrong about at least one of your assumptions.

As for an assert, one of your stated assumptions was that the two values should have been different, therefore an assert to test that assumption would have shown the assumption to be false.  As a programmer your job then would have been to determine why that assumption was false.

Further, as other have pointed out, your understanding of how floating point works on computers is lacking depth.  This is an unfortunately common problem with programmers, which is why folks who produce software designed to perform mathematical calculations require more training than is typical of programmers.  For instance, have you looked at the binary representation of the two numbers you were attempting to produce?  Are they different?
Logged

New true random number library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version 1.0.1

Grand Blanc, MI, USA
Offline Offline
Faraday Member
**
Karma: 95
Posts: 4089
CODE is a mass noun and should not be used in the plural or with an indefinite article.
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

8.3199996 may just be an (un)lucky choice. Consider the following. Does not yield the intended result in all cases, but looks to be working to me, allowing for typical floating point rounding errors.

Code:
void setup() {
  Serial.begin(9600);
  test(8.3199996);
  test(1.2345678);
  test(3.1415927);
  test(2.7182818);
}

void test(float x)
{
  Serial.println();
  Serial.print("x=");
  Serial.println(x, 7);

  Serial.print("x truncated to three decimal places=");
  Serial.println(floor(x*1000.)/1000., 7);
}
 
void loop() { }

Output:
Code:
x=8.3199996
x truncated to three decimal places=8.3199996

x=1.2345677
x truncated to three decimal places=1.2339999

x=3.1415927
x truncated to three decimal places=3.1410000

x=2.7182817
x truncated to three decimal places=2.7179999
Logged

MCP79411/12 RTC ... "One Million Ohms" ATtiny kit ... available at http://www.tindie.com/stores/JChristensen/

USA
Online Online
Sr. Member
****
Karma: 17
Posts: 382
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

I would suggest that you look at the optimized assembler produced from the code the OP posted...  It is clearly not calling the floor function.  ...  By optimizing away the details of the calculation, the results would remain identical ..."
Nobody's shown that the details of the calculation were "optimized away."  The only thing that's been shown is that the assembled program doesn't appear to call floor().  That's no error, bug, or quirk.  The program doesn't call floor() because the compiler called it at compile time, along with multiplication and division, and embedded the result in the output code.  There's no point in having the Arduino make those deterministic calculations every time it runs the program, when the compiler can make them once at compile time.  The fact that the output of the OP's floating point calculation is identical to its input is the result of the careful selection of the input value, and the limitations 32-bit floating point - not some stupid compiler or optimizer trick.

Referring to the OP's original program:  If the optimizer were replacing floor(x*1000.)/1000. with x, then that expression would give erroneous results with other values of x as well.  It turns out that it does a very nice job of getting correct answers with other values of x, within the limits of 32-bit floating point accuracy, as demonstrated in the Jack Christensen post above.  I'll claim that the compiler detected that the value of x never changes in the program, and optimized it into a constant.  Then, it detected that x*1000. is a constant multiplied by a constant, and is thus a constant as well; then, that floor(x*1000.) is also a constant, because it's a function - by definition a single valued mapping - with a constant argument; and finally, that floor(x*1000.)/1000. is a constant divided by a constant, and it's a constant, too.  No matter what else is happening in the universe when this program runs, the value of floor(x*1000.)/1000. is always the same.  It's a costly calculation, too, with a floating point multiplication, a floating point division, and a floating point function call.  If I were an optimizer, and wanted to get a good raise at my next performance review, I'd try pretty hard to eliminate those.

Here's a short program that should obviously print " 8.0000," if printf means anything to an AVR.  It has the appropriate includes, an assignment to x, the calculation that we're talking about, and some calls to generic output functions.  The output functions are in the code to make sure the compiler doesn't optimize the program away to nothing at all - without them, the program wouldn't do anything that you could see from the outside:
Code:
#include <math.h>
#include <stdio.h>
char c[20];

int main() {
  float x = 8.0001;

  x = floor(x*1000.)/1000.;
  sprintf(c, "%f10.4\n", x);
  printf(c);
}
When I compile it with either avr-gcc or avr-g++ without optimization, the assembler listing shows the program loading a constant 0x41000069, which is easily decoded to be "a little bit more than 8," then loading 0x447a0000, which is exactly 1000.0.  Then it calls mulsf3, and then floor.  It loads 0x447a0000 - again 1000.0 - and calls divsf3, and calls sprintf.  Just what you'd expect.  When I compile it with an optimization level of 1, it loads 0x41000000 - exactly 8.0 - and then calls sprintf, with nothing in between that looks like it could do multiplication or division, and no mention of floor

Without optimization, it loads something that looks very much like 8.0001, the value that is assigned to x, and then processes it as I'd expect.  With optimization, it loads the expected result - 8.0 - directly, and proceeds to the output functions.  Those results support the notion that the compiler evaluates expressions that collapse to constants at compile time, and generates output code to access those values directly rather than calculate them.

Still no optimization quirks, no bugs, no problems with the compiler, and everything is still kosher.
Logged

UK
Offline Offline
Shannon Member
****
Karma: 223
Posts: 12630
-
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset


floor(x*1000.) is also a constant, because it's a function - by definition a single valued mapping - with a constant argument;


How is it 'by definition a single valued mapping'?
Logged

I only provide help via the forum - please do not contact me for private consultancy.

Ayer, Massachusetts, USA
Offline Offline
Edison Member
*
Karma: 54
Posts: 1857
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset


floor(x*1000.) is also a constant, because it's a function - by definition a single valued mapping - with a constant argument;


How is it 'by definition a single valued mapping'?
Because the compiler does value propagation, and it knows in the previous line you assigned 8.0001 to x.  Now, if x had been a non-const static or global variable, and was initialized to 8.0001, it generally would have to assume that the value could vary, and call the floor function.


Code:
#include <math.h>
#include <stdio.h>
char c[20];

int main() {
  float x = 8.0001;

  x = floor(x*1000.)/1000.;
  sprintf(c, "%f10.4\n", x);
  printf(c);
}
Logged

USA
Online Online
Sr. Member
****
Karma: 17
Posts: 382
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

... it's a function - by definition a single valued mapping ...
How is it 'by definition a single valued mapping'?
The mathematical definition of function says that it has no more than one value for any particular set of inputs.  An example of something that isn't strictly a function is the square root, which has two values for every positive number.  It's usually made into a function by restricting it to positive values.  When I said "single-valued mapping," I meant that "floor()" has exactly one output value for any particular input.  Mathematically speaking, you could say that "floor()" maps the set of real numbers onto the set of integers. 
Logged

Dallas, Texas
Offline Offline
God Member
*****
Karma: 31
Posts: 887
Old, decrepit curmugeon
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Nobody's shown that the details of the calculation were "optimized away."  The only thing that's been shown is that the assembled program doesn't appear to call floor().  That's no error, bug, or quirk.  The program doesn't call floor() because the compiler called it at compile time, along with multiplication and division, and embedded the result in the output code.  There's no point in having the Arduino make those deterministic calculations every time it runs the program, when the compiler can make them once at compile time. 

The programmer called a function, the compiler decided that function call was not needed...  I completely agree that is not an error or a bug, which I have stated repeatedly...  It is a quirk.  It is a quirk because the machine decided that the programmer was inefficient and overrode the programmers directive.  The compiler may be (and actually is correct); however, that doesn't alter the fact that a machine decided something without communicating to the person the 'change'.  Now the reality is the issue is not AVR-GCC (at least not entirely), but an artifact (quirk) of the Arduino environment which seeks to protect programmers from the details.   Which is why it is used by so many 'programmers' who don't have the experience to recognize problems like this.

I called it an undocumented feature for a reason.  The documentation for the AVR-GCC leaves a lot to be desired...  The quality of documentation is historically the biggest weakness of Open Source software.  I personally don't think it is a problem, since the source code is available and nobody reads the manual anyway.
Logged

New true random number library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version 1.0.1

USA
Online Online
Sr. Member
****
Karma: 17
Posts: 382
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

... if x had been a non-const static or global variable, and was initialized to 8.0001, it generally would have to assume that the value could vary, and call the floor function.
And that's exactly what I get with x declared as a global variable.  The whole calculation appears in the code, at any optimization level.
Logged

Pages: 1 [2] 3   Go Up
Jump to: