CODEWITHSUNDEEP
pythonc++mathlong-integer
rel1x
rel1x

Reputation: 2441

Long numbers in C++

I have this program in Python:

# ...
print 2 ** (int(input())-1) % 1000000007

The problem is that this program works a long time on big numbers. I rewrote my code using C++, but sometimes I have a wrong answer. For example, in Python code for number 12345678 I've got 749037894 and its correct, but in C++ I've got -291172004.

This is the C++ code:

#include <iostream>
#include <cmath>
using namespace std;
const int MOD = 1e9 + 7;

int main() {
    // ...
    long long x;
    cin >> x;
    long long a =pow(2, (x-1));
    cout << a % MOD;
}

Upvotes: 0

Views: 2366

Answers (4)

Frank Boyne
Frank Boyne

Reputation: 4570

In C++ the various fundamental types have fixed sizes. For example a long long is typically 64 bits wide. But width varies with system type and other factors. As suggested above you can check climits.h for your particular environment's limits.

Raising 2 to the power 12345677 would involve shifting the binary number 10 left by 12345676 bits which wouldn't fit in a 64 bit long long (and I suspect is unlikely to fit in most long long implementations).

Another factor to consider is that pow returns a double (or long double) depending on the overload used. You don't say what compiler you are using but most likely you got a warning about possible truncation or data loss when the result of calling pow is assigned to the long long variable a.

Finally, even if pow is returning a long double I suspect the exponent 12345677 is too large to be stored in a long double so pow is probably returning positive infinity which then gets truncated to some bit pattern that will fit in a long long. You could certainly check that by introducing an intermediate long double variable to receive the value of pow which you could then examine in a debugger.

Upvotes: 0

Stian Svedenborg
Stian Svedenborg

Reputation: 1825

Like has been mentioned by many of the other answers, your problem lies in integer overflow.

You can do like suggested by deniss and implement your own modmul() and modpow() functions.

If, however, this is part of a project that will need to do plenty of calculations with very large numbers, I would suggest using a "big number library" like GNU GMP or mbedTLS Bignum library.

Upvotes: 0

user2512323
user2512323

Reputation:

As already mentioned, your problem is that for large exponent you have integer overflow.

To overcome this, remember that modular multiplication has such property that:

(A * B) mod C = (A mod C * B mod C) mod C

And then you can implement 'e to the power p modulo m' function using fast exponentiation scheme. Assuming no negative powers:

long long powmod(long long e, long long p, long long m){
    if (p == 0){
        return 1;
    }
    long long a = 1;
    while (p > 1){
        if (p % 2 == 0){
            e = (e * e) % m;
            p /= 2;
        } else{
            a = (a * e) % m;
            e = (e * e) % m;
            p = (p - 1) / 2;
        }
    }
    return (a * e) % m;
}

Note that remainder is taken after every multiplication, so no overflow can occur, if single multiplication doesn't overflow (and that's true for 1000000007 as m and long long).

Upvotes: 3

John Difool
John Difool

Reputation: 5722

You seem to be dealing with positive numbers and those are overflowing the number of bits you've allocated for their storage. Also keep in mind that there is a difference between Python and C/C++ in the way a modulo on a negative value is computed. To get a similar computation, you will need to add the Modulo to the value so it's positive before you take the modulo which is the way it works in Python:

cout << (a+MOD) % MOD;

You may have to add MOD n times till the temporary value is positive before taking its modulo.

Upvotes: 0

Related Questions