My code gives different results on different compilers

Question

My code gives different results on different compilers, the following code gives 499999998352516354 when I enter 1,1000000000 as my input on vs code which is the desired results while it gives 499999998352516352 on codeforces

#include <bits/stdc++.h>  
using namespace std;
int main()
{
   cout<<fixed<<setprecision(90);
   long long x,y;
   long long sum=0;
   long long z=1;
   cin>>x;
   for (int i = 0; i < x; i++)
   {
      cin>>y;
      sum=y*(y+1)/2;
       z= log2(y);
       sum-=2*(pow(2,1+z)-1);
       cout<<sum<<"\n";
       sum=0;
   }
}

Don't use `pow()` on integers. pow() is a floating point function and it can give a result that is 1 less than the expected value because of truncation that happens when converting a floating point number to int. — drescherjm, Oct 28 '22 at 13:20
I tried float m=z; sum-=2*(pow(2,1+m)-1); but I got the same results — Omar Mokhtar, Oct 28 '22 at 13:22
Don't use `pow` on integers, especially powers of 2. For powers of 2 use the `<<` operator. Instead of `pow(2, n)` use `(1 << n)`. — Jabberwocky, Oct 28 '22 at 13:27
and never use the `using` above. See [Why should I not `#include `?](https://stackoverflow.com/q/31816095/995714), [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/q/1452721/995714) — phuclv, Oct 28 '22 at 13:49

Arty · Accepted Answer · 2022-10-28T15:21:28.317

-3

Use std::llround() function around pow() and your code will work.

It is because pow() gives floating value which can be incorrectly truncated to 1 less than needed. And llround() gives correct rounding to whole integer.

Below is fixed code, I also adjusted code formatting and changed to correct necessary C++ headers.

Try it online!

#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

int main() {
    cout << fixed << setprecision(90);
    long long x, y;
    long long sum = 0;
    long long z = 1;
    cin >> x;
    for (int i = 0; i < x; i++) {
        cin >> y;
        sum = y * (y + 1) / 2;
        z = log2(y);
        sum -= 2 * (llround(pow(2, 1 + z)) - 1);
        cout << sum << "\n";
        sum = 0;
    }
}

Input:

1 1000000000

Output:

499999998352516354

As it is suggested in comments you may also use bit shifting 1LL << x instead of pow(2, x) if x is non-negative integer. And instead log2(y) if y is integer then one can use std::bit_width(y) - 1 (read about std::bit_width)

Try it online!

#include <iostream>
#include <iomanip>
#include <cmath>
#include <bit>

using namespace std;

int main() {
    cout << fixed << setprecision(90);
    long long x, y;
    long long sum = 0;
    long long z = 1;
    cin >> x;
    for (int i = 0; i < x; i++) {
        cin >> y;
        sum = y * (y + 1) / 2;
        z = std::bit_width<unsigned long long>(y) - 1;
        sum -= 2 * ((1LL << (1 + z)) - 1);
        cout << sum << "\n";
        sum = 0;
    }
}

edited Oct 28 '22 at 15:21

answered Oct 28 '22 at 13:28

Arty

14,883
6
36
69

2

Sorry, but this is terrible advice. If you want integer numbers with precision, you use bit shifts and integer operations. Don't encourage approximate floating point answer to integer-precision problems – Jeffrey Oct 28 '22 at 13:30
`log2` needs consideration too. – Bathsheba Oct 28 '22 at 13:30
@Bathsheba log2 is correctly truncated, if truncation logic is the correct one. If you change log2 to rounding it will give incorrect answer, not equal to the one OP said. If you want you can do `llround(log2(y) - 0.5)`, but it is same as just casting to integer, which does truncation towards 0. – Arty Oct 28 '22 at 13:34
1

@drescherjm Fixed, provided second code snippet that uses shifting. – Arty Oct 28 '22 at 13:35
@Jeffrey Fixed, added second code snippet that does bit shifting. – Arty Oct 28 '22 at 13:36
@Arty: There are no guarantees under IEEE754 that `log2` is correctly truncated. One of the problems with early implementations of pow(x, y) is that it can be implemented as exp(y log(x)). Chipsets do a better job with exp than they do with log. – Bathsheba Oct 28 '22 at 13:41
@Bathsheba Just now added in Part-3 of my answer example of how log2() can be fixed. If it is what you wanted please tell me. If not then please suggest how to correct it better. – Arty Oct 28 '22 at 13:47
3

`log2` is a bad way to get integer log2. Use `std::bit_width` instead – phuclv Oct 28 '22 at 13:48
2

Best way IMHO is to use a library that implements pow for integer arguments (something like exponentation by squaring). `std::bit_width` is a better choice for `log2` for your case. – Bathsheba Oct 28 '22 at 13:48
@phuclv: We in the same room? – Bathsheba Oct 28 '22 at 13:49
@phuclv Just updated Part-2 of my answer to use `std::bit_width` as you suggested. – Arty Oct 28 '22 at 15:21
@Bathsheba Just updated Part-2 of my answer to use `std::bit_width` as you suggested. – Arty Oct 28 '22 at 15:22

My code gives different results on different compilers

1 Answers1