MinGW 64 error in integer (long int) arithmetic

Question

Hope you can help me; I have the following code:

#include <iostream>
#include <math.h>

using namespace std;

long int
cifra (long int b, long int e, long int n)
{
  /* Calcula a tal que (b^e)=a MOD n. Algoritmo 3.1 de Allenby & Redfern,1989. */
  long int a, i, q, r;

  a = 1;
  q = b / n;
  r = b - q * n;
  for (i = 1; i <= e; i++)
    {
      a = a * r;
      q = a / n;
      a = a - q * n;        /* ou, de forma equivalente, a=mod(a,n) */
    }
  return a;
}

int
main ()
{

  long int a, b, e, n;

  b = 116104101;
  e = 19661;
  n = 383768051;

  a = cifra (b, e, n);

  cout << "a=" << a << endl;

  return 0;
}

and this should output

a=199324862

as it does when I used the online C++ Compiler (https://www.onlinegdb.com/online_c++_compiler, which uses g++).

However: if I run it on Code::Blocks with MinGW64 (on Windows 10), I get the wrong result:

a=298405922

Any ideas? Am I doing anything wrong?

Answer 1

Overflow

q * n, a * r, q * n risk overflow.

The width of long is at least 32-bit, yet a full range multiplication obliges 2x long width for the product. On some platforms it is 64-bit and thus success with the test values on some, failure on others.

Either:

1. Use a wider type for intermediate calculations. long long would suffice for OP's test case of b = 116104101; e = 19661; n = 383768051; yet still fail with long long for b = 116104101<<32; e = 19661<<32; n = 383768051<<32;

or

2. Perform the math more carefully. Example: Modular exponentiation without range restriction.

---

Slow

for (i = 1; i <= e; i++) is very slow with large e. Research Modular exponentiation.

---

Bug

int64_t cifra(int64_t b, int64_t e, int64_t n) incorrect with some small corner cases. cifra(b, 0, 1) returns 1 when it should return 0.

// a = 1;
a = n > 1 ? 1 : 0;
// or 
a = 1%n;
// or ...

---

Sample fix

Example fix for OP's code with limited range. I went for unsigned types as analyzing signed types with negative values is too tedious right now.

uint32_t cifra32(uint32_t b, uint32_t e, uint32_t n) {
  uint64_t a = 1%n;
  uint64_t q = b / n;
  uint64_t r = b - q * n;
  for (uint32_t i = 1; i <= e; i++) {
      a = a * r;
      q = a / n;
      a = a - q * n;
    }
  return a;
}

More improvements possible.

Answer 2

It seems that you're assuming that long int is a 64-bit (or larger) integer type, but it's actually a 32-bit type in that particular environment. If you need a certain size type you should use something more explicit like int64_t or uint64_t. Also, you might want to use the remainder operator % to avoid the q variable altogether, e.g. r = b % n or just b %= n:

#include <iostream>
#include <cstdint>

int64_t cifra(int64_t b, int64_t e, int64_t n) {
    /* Calcula a tal que (b^e)=a MOD n. Algoritmo 3.1 de Allenby & Redfern,1989. */
    int64_t a, i;

    a = 1;
    b %= n;
    for (i = 1; i <= e; i++) {
        a = (a * b) % n;  /* ou, de forma equivalente, a=mod(a,n) */
    }
    return a;
}

int main() {

    int64_t a, b, e, n;

    b = 116104101;
    e = 19661;
    n = 383768051;

    a = cifra(b, e, n);

    std::cout << "a=" << a << std::endl;
    return 0;
}