does modulus function is only applicable on integer data types?

Question

my algorithm calculates the arithmetic operations given below,for small values it works perfectly but for large numbers such as 218194447 it returns a random value,I have tried to use long long int,double but nothing works because modulus function which I have used can only be used with int types , can anyone explain how to solve it or could provide a links that can be useful

#include<stdio.h>
#include<math.h>

int main()
{
    long long i,j;
    int t,n;

    scanf("%d\n",&t);

    while(t--)
    {
        scanf("%d",&n);

        long long k;
        i = (n*n);
        k = (1000000007);
        j = (i % k);

        printf("%d\n",j);
    }

    return 0;
}

Please indent/format your code so that it's readable. Thanks. — Oliver Charlesworth, Sep 01 '14 at 19:12
Possible duplicate:- http://stackoverflow.com/questions/2177781/how-to-calculate-modulus-of-large-numbers — Rahul Tripathi, Sep 01 '14 at 19:13
Unrelated: just using `1000000007` would seem considerably clearer than recomputing `pow(10,9)+7` repeatedly, which we can only hope a reasonably intelligent compiler optimized anyway. — WhozCraig, Sep 01 '14 at 19:19
@user3315556 besides the clarity of the code and its performance, nothing at all (thus the comment and not a answer, the link provided by R.T should be considered for potential answer-material). — WhozCraig, Sep 01 '14 at 19:25
@JoelCornett because it is represented with a -ve sign in the beginning that represents overflow of memory I think — user3315556, Sep 01 '14 at 20:08

score 1 · Answer 1 · answered Sep 01 '14 at 19:25

The problem in your code is that intermittent values of your computation exceed the range of values that can be stored in an int. n^2 for values of n>2^30 cannot be represented as int.

Follow the link above given by R.T. for a way of doing modulo on big numbers. That won't be enough though, since you also need a class/library that can handle big integer values . With only standard C libraries in place, that will otherwise be a though task do do on your own. (ok, for 2^31, a 64 bit integer would do, but if you're going even larger, you're out of luck again)

score 1 · Accepted Answer · answered Sep 01 '14 at 19:27

You could declare your variables as int64_t or long long ; then they would compute the modulus in their range (e.g. 64 bits for int64_t). And it would work correctly only if all intermediate values fit in their range.

However, you probably want or need bignums. I suggest you to learn and use GMPlib for that.

BTW, don't use pow since it computes in floating point. Try i = n * n; instead of i = pow(n,2);

^{P.S. this is not for a beginner in C programming, using gmplib requires some fluency with C programming (and programming in general)}

score 0 · Answer 3 · answered Oct 15 '14 at 22:10

After accept answer

To find the modulo of a number n raised to some power p (2 in OP's case), there is no need to first calculate power(n,p). Instead calculate intermediate modulo values as n is raise to intermediate powers.

The following code works with p==2 as needed by OP, but also works quickly if p=1000000000.

The only wider integers needed are integers that are twice as wide as n.

Performing all this with unsigned integers simplifies the needed code.

The resultant code is quite small.

#include <stdint.h>

uint32_t powmod(uint32_t base, uint32_t expo, uint32_t mod) {
  // `y = 1u % mod` needed only for the cases expo==0, mod<=1
  // otherwise `y = 1u` would do.
  uint32_t y = 1u % mod;

  while (expo) {
    if (expo & 1u) {
      y = ((uint64_t) base * y) % mod;
    }
    expo >>= 1u;
    base = ((uint64_t) base * base) % mod;
  }

  return y;
}

#include<stdio.h>
#include<math.h>

int main(void) {
  unsigned long j;
  unsigned t, n;

  scanf("%u\n", &t);

  while (t--) {
    scanf("%u", &n);

    unsigned long k;
    k = 1000000007u;
    j = powmod(n, 2, k);

    printf("%lu\n", j);
  }

  return 0;
}

does modulus function is only applicable on integer data types?

3 Answers3