Shefin_'s blog

Weird Precision Behavior in "Inline Function" on GNU C++17 7.3.0
By Shefin_, 3 years ago, In English

I was solving the problem 185B/186D. Then I encountered a weird issue. I got WA on test $$$8$$$ in this submission: 123642519. But, when I made the solve function inline, it passed test $$$8$$$ (though it got WA on test $$$31$$$): 123642504.

In test $$$8$$$, the submission without inlined solve function prints 2.712800440549510 6.287199559450490 0.000000000000000 as output. On the other hand, the submission with inlined solve function prints 2.700961045920403 6.299038954079596 0.000000000000000 as output. So, the outputs have significant precision differences.

My question is, how the inlined function has an impact on precision? It will be very helpful if anybody gives an insight.

  • Vote: I like it
  • +47
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 5   Vote: I like it +5 Vote: I do not like it

A plausible explanation for this behavior is that the compiler increased the precision of the inline function variables to long double. And this increased precision caused the function to reach the correct answer after 200 iterations. You may check the following technical report for more details about this issue.

David Monniaux. The pitfalls of verifying floating-point computations. 2007. hal-00128124v1

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you. What I've found out from the paper about inline functions is:

    ...if the program is compiled with optimization on, f is inlined; no parameter passing takes place, thus no conversion to double...

    So, if I have a function like inline double f(double x) and I call it with a long double value, there is a high chance that all calculations related to variable x will be performed in long double.

    But that shouldn't be the case in my submissions as I've used double everywhere.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Actually, changing the data type of the floating-point variables in the solve function to long double was sufficient to get your code accepted without prefixing the function header with inline.

      123689411

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah. Even the same code of mine using GNU C++17 (64) compiler got AC. Actually, I was not concerned about getting AC. I was only concerned about the weird inline behavior. Maybe you were right. Some sort of high precision was triggered by the C++ compiler somehow.

        → Reply
»
3 years ago, # |
  Vote: I like it +39 Vote: I do not like it

TL;DR — your solution is bad and you got lucky to pass test 8 with one version. Don't assume that inline will help you in the future.

if((x==0 && a != 0) || (y==0 && b != 0) || (z==0 && c != 0))

That's not a correct way to check if real values are equal to 0. You need to compare with epsilon.

What happened is that some value like $$$x$$$ got very close to $$$0$$$ and you got a huge negative value as $$$log(x)$$$, maybe even smaller than $$$-inf$$$, which you hardcoded as $$$-2^{61}$$$.

Nested ternary search isn't the intended solution and it would be bold to claim that it works without big precision errors. Maybe it does. We use values from the range $$$(-inf, 10000)$$$ and that's a big range. I'm not sure fixing the comparison with $$$0$$$ is enough. I actually think it isn't. Nested ternary search is already scary (in terms of precision) for reasonable ranges.

Here's one possible fix: change each ternary search range from $$$[0, s]$$$ to $$$[eps, s]$$$, and use long doubles. You won't need to compare with 0 or use your own infinity value. This new version shouldn't yield huge errors but there's a catch: each of $$$x, y, z$$$ will be at least $$$eps$$$, even though it's maybe optimal to use $$$0$$$. This would be ok if the statement said "each of three printed values can have error 1e-6" but instead the statement wants a small error on the final sum value. You need to analyze if that is satisfied too.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +10 Vote: I do not like it

    Thanks for your explanation.

    That's not a correct way to check if real values are equal to 0. You need to compare with epsilon.

    Yeah, that was a terrible mistake. I wanted to handle $$$log(0)$$$ and unfortunately forgot that I was dealing with floating-point values. Later, I got AC by modifying the condition of the while loop of ternary search to while(hi-lo > eps): 123643009.

    But, taking the mistake in concern, shouldn't the submissions with and without inline function produce the same output and get WA on the same test case? Since the same mistake is occurring in both submissions.

    "Don't assume that inline will help you in the future"

    -That's true. But, I'm just curious that what's actually happening here.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      shouldn't the submissions with and without inline function produce the same output and get WA on the same test case?

      I don't know. I mostly understand precision but I don't know what C++ inline can do. Maybe CodingKnight is right that higher precision is triggered. I think that even using two same lines of code within one program can give you two slightly different values — just because e.g. one of them is inside a function and C++ compiler did some optimization magic. Don't quote me on that though.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it +51 Vote: I do not like it

        I've written a blog on higher (excess) precision before https://codeforces.me/blog/entry/78161. I do not believe that inline is what is fundamentally causing the issue.

        I think you will find the following examples very interesting:

        Example 1
        Example 2
        Example 3

        The TLDR is that for legacy reasons g++ 32 bit uses long doubles for all its floating point calculations. Even a function declared as returning a double actually returns a long double. Only when a number is stored is it actually rounded to float/double. It is a mess. If you instead use g++ 64 bit, then floating point numbers will behave like you'd expect them to.

        In my examples, the x represented as a long double is slightly smaller than 1.0. But if rounded to a double its value is exactly 1.0. The pow call causes x to temporarily be stored, which rounds it up to 1.0.

        → Reply