Why am I getting a negative value?

Question

There is some mistake in power function of my code it returns correct answer for small values but gives wrong answer for large values.

#include<stdio.h>
long long MOD= 1000000007;
long long power(long long i,long long j)
{
        if(j==0)
                return 1;
        long long d;
        d=power(i,j/(long long)2);
        if(j%2==0)
                return (d*d)%MOD;
        else
                return (d*d*i)%MOD;
}

int main()
{
        long long inv=1;
        inv=power(25,MOD-2)%MOD;
        printf("%lld\n",inv);
}

What problem are you having? Compilation error? Runtime error? Wrong results? If the last, what do you expect the result to be for some value, and what do actually get? — Some programmer dude, Mar 25 '13 at 13:03
@PeterK.: `y` has type `long long` so `y/2` and `y/(long long) 2` are guaranteed to be the same thing. — Dietrich Epp, Mar 25 '13 at 13:29
http://stackoverflow.com/questions/9169167/need-help-in-mod-1000000007-questions — Alon, Mar 25 '13 at 13:34
@user2205153 why do you accept my answers and then come back on your decision? Was there something incorrect? — UmNyobe, Mar 26 '13 at 10:04

score 1 · Answer 1 · answered Mar 25 '13 at 13:28

1

Your arithmetic overflowed the values representable in a long long in your C implementation.

Also, you are working on a challenge problem or homework which has been discussed numerous times on Stack Overflow, as you can see by searching for “1000000007”.

answered Mar 25 '13 at 13:28

Eric Postpischil

195,579
13
168
312

I have no problem with algorithm.I am having problem with c .In python I am getting correct result of same problem – TLE Mar 25 '13 at 13:36

UmNyobe · Answer 2 · 2013-03-25T13:35:45.877

You need to be careful with (d*d*i)%MOD;, because more than one operation without modulo is incorrect, taking precision and risk of overflowing in account. To be strictly correct you need to write

 return ((d*d)%MOD * i)%MOD;

Even in this case I assumed i == i%MOD

EDIT: I take an example :

log2((MOD-1)x(MOD-1)x25) = log2(1000000006x1000000006x25) = 64.438

Which means you will be overflowing during your computation with this input.

score 0 · Accepted Answer · answered Mar 26 '13 at 04:43

range of signed long long is -2^63 to (2^63 - 1) and the last bit is used to store sign . In your case when multiplication of large numbers is evaluated than your result will overflow and 64th bit of number(which stores sign) will get value 1 (which means -ve value).

That's the reason you are getting negative value as output.

Read this

Why am I getting a negative value?

3 Answers3