Блог пользователя Dd2dD2

Автор Dd2dD2, история, 20 месяцев назад, По-английски

Why does the following code output 1000000000000000000 and not 1000000000000000001?

#include <bits/stdc++.h>
using namespace std;
 
long long inf = 1e18+1;

int main() {
    cout << inf << '\n';
}
  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
20 месяцев назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

If I were to guess it is some weird floating point precision error? This code works as expected

#include <bits/stdc++.h>
using namespace std;
 
long long inf = (long long)1e18+1;

int main() {
    cout << inf << '\n';
}
»
20 месяцев назад, # |
Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится

Not 100% sure, but 1e18 is a floating point number. When the right-hand side is being computed, 1 is added to 1e18, which means the resulting floating point number will require 18 digits of precision, which was most probably truncated or rounded because no floating point types can handle it. Then, it is converted to long long.

Also take a look at this:

#include <bits/stdc++.h>
using namespace std;
 
long long inf = 1e18+100;

int main() {
    cout << inf << '\n';
}

Output:

$ g++ a.cpp; ./a.out
1000000000000000128

As pointed out by tn757, the fix is to typecast 1e18 to long long first so we don't have to deal with floating point precision.

»
20 месяцев назад, # |
Rev. 4   Проголосовать: нравится -92 Проголосовать: не нравится

The reason why the output of the code is 1000000000000000000 and not 1000000000000000001 is due to an overflow error.

In C++, the

»
20 месяцев назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится

long double is more precise. You can get it by adding L at the end of a numeral.

long long inf = 1e18L + 1;

»
20 месяцев назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Double has 8 bytes, long long has 8 bytes. Can double represent all the integers that can be represented in long long? No, because how would it represent fractional numbers plus all the integer numbers with the same amount of memory? Double has 15 decimal digits of precision, which means it can represent integers up to 1e15. The next smallest double after 1e18 is 1e18+1000

»
20 месяцев назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
  • (32 bit) float can store all positive integers up to (and including) $$$2^{24} \approx 1.7 \cdot 10^7$$$.
  • (64 bit) double can store all positive integers up to (and including) $$$2^{53} \approx 9 \cdot 10^{15}$$$.
  • (80 bit) long double can store all positive integers up to (and including) $$$2^{64} \approx 1.8 \cdot 10^{19}$$$.

After this limit, there are still many integers that can be represented as floating point numbers, but most integers cannot. For example take float and the integers $$$2^{24} + 1$$$ and $$$2^{24} + 2$$$. $$$2^{24} + 1$$$ cannot be stored in a float, but $$$2^{24} + 2$$$ can.

So now let us analyze long long inf = 1e18+1;. By the default behaviour of C++ 1e18 is of the type double, and it turns out double can store $$$10^{18}$$$ (even though it is above the limit), so no rounding is happening here. However $$$10^{18}+1$$$ happens to not be storeable in a double, so it will round the sum to the closest representable floating point value, which is $$$10^{18}$$$. So the conclusion is that inf will get the value $$$10^{18}$$$.

One fix is to do long long inf = 1e18L+1;, which would make 1e18L a long double. long doubles can handle any integer calculation $$$\leq 2^{64}$$$ no problems. So this time inf will become 10^{18} + 1.