Inconsistencies when using cmath's fmod (C++)

Question

I am getting some very confusing results when using the fmod function.

The following code:

double x = pow(142, 35);
double y = fmod(x, 221);
std::cout << x << std::endl << y;

outputs:

2.13842e+75
206

But when hard coding the x value:

double x = pow(142, 35);
double y = fmod(2.13842e+75, 221);
std::cout << x << std::endl << y;

The output is changed to:

2.13842e+75
14

I have no idea what the cause of this is, and it is creating some ugly bugs within my program. Any insight would be greatly appreciated. Thanks in advance.

Update answer with a modular power algorithm that should solve your issue. — Shafik Yaghmour, Mar 28 '14 at 03:53

score 3 · Accepted Answer · edited May 23 '17 at 11:57

3

So when I output the first results like this:

std::cout << std::fixed << x << std::endl << y << std::endl;

I see this:

2138415301692701661114266637060519453227273059369895888628790658837784821760.000000
206.000000

when I used this number above for xs value like so:

double y = fmod(2138415301692701661114266637060519453227273059369895888628790658837784821760.000000, 221);

then I get the result of 206 for y from the first example, the main problem is that you are hitting limit with IEEE double.

Update

This algorithm for modular power:

template <typename T>
T modpow(T base, T exp, T modulus) {
  base %= modulus;
  T result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % modulus;
    base = (base * base) % modulus;
    exp >>= 1;
  }
  return result;
}

that I found from here will give you the correct result.

edited May 23 '17 at 11:57

Community

1
1

answered Mar 28 '14 at 03:15

Shafik Yaghmour

154,301
39
440
740

1

I am very confused then. If you type 142^35 mod 221 into wolfram alpha the result is 12. I guess 14 is not the desired result as I mentioned before. The code is being used for RSA decryption, so the result should be between 0 and 25, and would correspond to a alphabetical character. – motza Mar 28 '14 at 03:19
2

12 is the correct answer. Even a double isn't large enough to hold the answer. The actual value of 142^35 is 2138415301692701650291828893190357329823022421032574372998179511073104723968; only the first 17 digits match. You need an arbitrary precision calculator such as bc on Linux to perform the calculation correctly. – esorton Mar 28 '14 at 03:22
@esorton I was just checking that, that was my suspicion – Shafik Yaghmour Mar 28 '14 at 03:23
@legends2k seems to and it is usually used for RSA which is what the OP is using it for, see the [Wikipedia article on it](http://en.wikipedia.org/wiki/Modular_exponentiation). – Shafik Yaghmour Mar 28 '14 at 03:59
Yeah, I didn't know about this, thanks! Instead of first calculating the power (which will lead to an overflow in the native data types) and then trying to mod it, this does both within the limits, good to know :) – legends2k Mar 28 '14 at 04:01

score 0 · Answer 2 · answered Mar 28 '14 at 03:46

There are a couple of problems here.

First, your print statement truncates the actual value. The default for C++ cout is a precision of 6. It will only print 6 decimal places. Thus, the following two prints yield different results even though they print the same variable:

double x = pow(142, 35);
std::cout << x << std::endl << y;
// prints 2.13842e+75
std::cout << std::fixed << x << std::endl << y << std::endl;
// prints 2138415301692701661114266637060519453227273059369895888628790658837784821760.0000000

Note that the std::fixed manipulator is used to change the output. Thanks to @Shafik Yaghmour for providing the manipulator.

Second, even the value printed above is incorrect due to the lack of precision of a double. An IEEE double uses 52 bits to store the mantissa. This is sufficient for 15 to 17 digits of precision. You need to use an arbituary precision calculator to determine the actual result (for example, the bc command line utility).

% bc
142^35
2138415301692701650291828893190357329823022421032574372998179511073104723968
(142^35)%221
12

Looking at the two values, the first 17 digits match as expected.

See http://en.wikipedia.org/wiki/Double-precision_floating-point_format for additional details on the limits of an IEEE double.

Inconsistencies when using cmath's fmod (C++)

2 Answers2

Linked