0

This question is regarding the modulo operator %. We know in general a % b returns the remainder when a is divided by b and the remainder is greater than or equal to zero and strictly less than b. But does the above hold when a and b are of magnitude 10^9 ?

I seem to be getting a negative output for the following code for input:

74 41 28

However changing the final output statement does the work and the result becomes correct!

    #include<iostream>
    using namespace std;

    #define m 1000000007

    int main(){
       int n,k,d;
       cin>>n>>k>>d;
       if(d>n)
         cout<<0<<endl;
       else
       {
           long long *dp1 = new long long[n+1], *dp2 = new long long[n+1];

           //build dp1:
           dp1[0] = 1;
           dp1[1] = 1;

           for(int r=2;r<=n;r++)
           {
              dp1[r] = (2 * dp1[r-1]) % m;
              if(r>=k+1) dp1[r] -= dp1[r-k-1];
              dp1[r] %= m;
           }

           //build dp2:
           for(int r=0;r<d;r++) dp2[r]  = 0;
           dp2[d] = 1;

           for(int r = d+1;r<=n;r++)
           {
             dp2[r] = ((2*dp2[r-1]) - dp2[r-d] + dp1[r-d]) % m;
             if(r>=k+1) dp2[r] -= dp1[r-k-1];
             dp2[r] %= m;
           }

           cout<<dp2[n]<<endl;
        }
   }

changing the final output statement to:

        if(dp2[n]<0) cout<<dp2[n]+m<<endl;
        else cout<<dp2[n]<<endl; 

does the work, but why was it required?

By the way, the code is actually my solution to this question

0

3 Answers 3

1

This is a limit imposed by the range of int.

int can only hold values between –2,147,483,648 to 2,147,483,647.

Consider using long long for your m, n, k, d & r variables. If possible use unsigned long long if your calculations should never have a negative value.

long long can hold values from –9,223,372,036,854,775,808 to 9,223,372,036,854,775,807

while unsigned long long can hold values from 0 to 18,446,744,073,709,551,615. (2^64)

The range of positive values is approximately halved in signed types compared to unsigned types, due to the fact that the most significant bit is used for the sign; When you try to assign a positive value greater than the range imposed by the specified Data Type the most significant bit is raised and it gets interpreted as a negative value.

2
  • 2
    The values which int or long long can hold are implementation defined, and vary largely. And if you try to assign a value out of range, the results are implementation defined; you don't necessarily get a negative value. Jan 25, 2015 at 12:10
  • ..but, good compiler would issue a warning. Sadly, many new programmers are used to ignore them, since "they are not errors, right?" Jan 25, 2015 at 12:11
1

Well, no, modulo with positive operands does not produce negative results.

However .....

The int type is only guaranteed by the C standards to support values in the range -32767 to 32767, which means your macro m is not necessarily expanding to a literal of type int. It will fit in a long though (which is guaranteed to have a large enough range).

If that's happening (e.g. a compiler that has a 16-bit int type and a 32-bit long type) the results of your modulo operations will be computed as long, and may have values that exceed what an int can represent. Converting that value to an int (as will be required with statements like dp1[r] %= m since dp1 is a pointer to int) gives undefined behaviour.

1
  • IIRC: the results of a conversion which doesn't fit is implementation defined, not undefined behavior. (The results of an operation which doesn't fit is undefined behavior, but this can't occur with %.) Jan 25, 2015 at 12:12
0

Mathematically, there is nothing special about big numbers, but computers only have a limited width to write down numbers in, so when things get too big you get "overflow" errors. A common analogy is the counter of miles traveled on a car dashboard - eventually it will show as all 9s and roll round to 0. Because of the way negative numbers are handled, standard signed integers don't roll round to zero, but to a very large negative number.

You need to switch to larger variable types so that they overflow less quickly - "long int" or "long long int" instead of just "int", the range doubling with each extra bit of width. You can also use unsigned types for a further doubling, since no range is used for negatives.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.