Overflowing remainder calculation in C++

Question

I want to calculate the below expression:

pow(2012, 17) % 3569

When I do this in Ruby like this, it shows 915.

print (2012 ** 17) % 3569

When I do this in C++ like this, it shows 1190.

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    cout << remainder(pow(2012, 17), 3569) << endl;
}

915 looks correct. Why are they different and how to fix the C++ code?

You have to implement pow yourself using the square-and-multiply algorithm and use modulo 3569 in every step. The `pow` function works with doubles and is imprecise. — Goswin von Brederlow, May 09 '22 at 08:59
Thank you. I could re-write the script and can get the correct answer. — hidetatz, May 09 '22 at 09:15
duplicate: [Calculating pow(a,b) mod n](https://stackoverflow.com/q/8496182/995714), [Calculating (a^b)%MOD](https://stackoverflow.com/q/11272437/995714) — phuclv, May 10 '22 at 03:33

hidetatz · Answer 1 · 2022-05-09T23:08:29.760

1

Thanks to Goswin, I could rewrite the C++ code like this

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    int result = 1;
    for (int i = 0; i < 17; i++) {
        result *= 2012;
        result = result % 3569;
    }

    cout << result << endl;
}

Now it works. Thank you.

edited May 09 '22 at 23:08

answered May 09 '22 at 09:15

hidetatz

195
8

2

C++ source code files are not scripts (because C++ is not a scripting language, it is a compiled language). – heap underrun May 09 '22 at 13:15

score 0 · Answer 2 · answered May 09 '22 at 23:28

Why are they different

Because C++'s pow does floating-point rather than integer math.

In exact integer arithmetic, pow(2012, 17) would be 145,102,735,039,632,235,424,933,403,463,510,202,882,323,568,682,170,580,992. But the standard IEEE 754 double can only approximate this value as 1.4510273503963223e+56, or to be ultra-precise, 145,102,735,039,632,225,543,927,922,730,425,249,428,937,718,149,261,819,904, with only the first 16 sig figs correct. Taking this number modulo 3569 gives 1190, as you have seen.

To get the expected result of 915, you need to use integer arithmetic. I don't think the standard C++ library has a function for that, but it's easy to implement one. Here's a recursive version:

int powmod(int base, int exponent, int modulus)
{
    if (exponent == 0)
    {
        return 1;
    }
    else if (exponent % 2 == 0)
    {
        int square_root = powmod(base, exponent / 2, modulus);
        return square_root * square_root % modulus;
    }
    else
    {
        return powmod(base, exponent - 1, modulus) * base % modulus;
    }
}

The else if (exponent % 2 == 0) special-casing of even exponents isn't required, but allows the algorithm to run in logarithmic rather than linear time.

Overflowing remainder calculation in C++

2 Answers2