Why is my arithmetic with a long long int behaving this way?

Question

I'm trying to calculate large integers with the long long datatype but when it gets large enough (2^55), the arithmetic behavior is unpredictable. I am working in Microsoft Visual Studio 2017.

In this first case, I am subtracting 2 from the long long variable m in the initialization. This works fine for all n until I try 54, then m will simply not be subtracted by 2.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>

using namespace std;

#define LL long long

int main()
{
    LL n;
    cin >> n;
    LL m = pow(2, n + 1) - 2;
    cout << m;
    return 0;
}

However, using this code m does get subtracted by 2 and is working as I would expect.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>

using namespace std;

#define LL long long

int main()
{
    LL n;
    cin >> n;
    LL m = pow(2, n + 1);
    m -= 2;
    cout << m;
    return 0;
}

I expect both codes to be equivalent, why is this not the case?

I'm curious where you picked up `#define LL long long`. I see it pretty often on this site, but I'm not aware of who or what is propagating it. Edit : Is it another one of those code golf habits? — François Andrieux, May 03 '19 at 13:54
@FrançoisAndrieux It's used a lot in programming challenges to save typing time. — NathanOliver, May 03 '19 at 13:55
[`using namespace std;` is considered bad practice.](https://stackoverflow.com/q/1452721) — L. F., May 03 '19 at 13:55
@FrançoisAndrieux I guess Its just a bit of lazziness.. Due to the `#define` all occurences of `LL` will be replaced by `long long` at compile time — Lucas, May 03 '19 at 13:56
@Lucas but `using LL = long long` is also compile time, same size to type, and better. There is no reason to use a macro there — Guillaume Racicot, May 03 '19 at 14:04
Prefer to use *bit shifting* instead of `pow(2, N)`, such as `(1 << N)`. Bit shifting uses integers and most processors have a single instruction for shifting. — Thomas Matthews, May 03 '19 at 14:19
@L.F. Don't randomly push stuff like that without understanding why. `using namespace std;` is _perfectly_ fine when writing code examples. — pipe, May 03 '19 at 14:51
@pipe: We understand perfectly well why. We don't want to promote bad practices just because you think it's "magically fine" for code examples. There are plenty of code examples on this site that were broken by `using namespace std;` — Mooing Duck, May 03 '19 at 16:56
@ThomasMatthews when you're telling people to prefer bit-shift for *signed* integer types, please alert them that for signed integer types overflow is *undefined behavior*, that this is not just theoretical undefined behavior but can create actual bugs on common compilers like `gcc`, and that the numerical result can be surprising and unexpected if you don't consciously think about overflow even when it is compiled to behave exactly as expected for a fixed-width integer type. — mtraceur, May 03 '19 at 21:13
Minor nit unrelated to your problem: prefer `typedef` or `using` to `#define` for types. Simple lexical substitution can blow up on you, but with `typedef`, the compiler knows what’s going on. — Davislor, May 03 '19 at 23:59

score 50 · Accepted Answer · edited Sep 24 '19 at 16:48

50

The issue with

LL m = pow(2, n + 1) - 2;

is that pow(2, n + 1) is not a long long. It has the type double (refer to cppreference) and because the value is so large, subtracting 2 from it will not change its value. That means that m will not have the correct value. As you have already found, you need to assign the result first and then do the subtraction. Another alternative is to write your own pow that will return a integer type when given an integer type so you can do the raising to the power and subtraction at the same time.

edited Sep 24 '19 at 16:48

asynts

2,213
2
21
35

answered May 03 '19 at 13:47

NathanOliver

171,901
28
288
402

10

For the OP: You should use bit shifting instead of `pow()` function. Something like `(1 << (n + 1))`. – Thomas Matthews May 03 '19 at 14:17
1

@StackDanny The problem is at `pow(2, 54)`, not `pow(2, 53)` – NathanOliver May 03 '19 at 14:24
6

Good answer but you should probably mention that the reason it works in the second example is that `pow(2,n)` "accidentally" fits exactly in the most commonly used floating point representation, even for very large results, so there is never a round-off error involved. – pipe May 03 '19 at 14:55
2

@pipe, for powers of two and binary computers, it's not an "accident" in any way. – ilkkachu May 03 '19 at 18:32
3

@ThomasMatthews you'll need `1ULL << (n + 1)` to shift more than 31 bits – phuclv May 04 '19 at 04:25
_"Another alternative is to write your own pow"_ -- you can't be seriously suggesting that? There must be a standard implementation, somewhere. To reinvent the square wheel is the worst advice. – ivan_pozdeev May 05 '19 at 04:47
@ivan_pozdeev I am serious. There is no `pow` implementation that gives you an integer in C++. You have to write your own or get on from some third party library. – NathanOliver May 05 '19 at 12:42
I believe you that this is an oversight in the standard library ([until recently](https://stackoverflow.com/questions/2398442/why-isnt-int-powint-base-int-exponent-in-the-standard-c-libraries)). By "standard", I meant in some highly-used general-purpose 3rd-party library like Boost. – ivan_pozdeev May 05 '19 at 17:32
@ivan_pozdeev that overload still returns a `double`. – NathanOliver May 05 '19 at 17:51

score 19 · Answer 2 · edited Jun 20 '20 at 09:12

I expect both codes to be equivalent, why is this not the case?

Your expectation is wrong. Your second code would be equivalent to this:

auto m = static_cast<LL>( pow(2, n + 1) ) - 2;

as due to conversion rule for arithmetic operators and the fact that std::pow() returns double in this case:

For the binary operators (except shifts), if the promoted operands have different types, additional set of implicit conversions is applied, known as usual arithmetic conversions with the goal to produce the common type (also accessible via the std::common_type type trait). If, prior to any integral promotion, one operand is of enumeration type and the other operand is of a floating-point type or a different enumeration type, this behavior is deprecated. (since C++20)

If either operand has scoped enumeration type, no conversion is performed: the other operand and the return type must have the same type

Otherwise, if either operand is long double, the other operand is converted to long double

Otherwise, if either operand is double, the other operand is converted to double

Otherwise, if either operand is float, the other operand is converted to float

...

(emphasis is mine) your original expression would lead to double - double instead of long long int - long long int as you do in the second case hence the difference.

score 17 · Answer 3 · answered May 03 '19 at 15:33

The pow function returns a value of type double, which only has 53 bits of precision. While the returned value will fit in a double even if n is greater than 53, subtracting 2 results in a value of type double that requires more than 53 bits of precision so the result of the subtraction is rounded to the nearest representable value.

The reason breaking out the subtraction works is because the double value returned from pow is assigned to a long long, then you subtract an int from a long long.

Since you're not dealing with floating point numbers and you're only raising 2 to a power, you can replace the call to pow with a simple left shift:

LL m = (1LL << (n + 1)) - 2;

This keeps all intermediate values at type long long.

Why is my arithmetic with a long long int behaving this way?

3 Answers3