Even though I use % 1000000007 it still results on 0

Question

my goal on this code is to make exponential operations without pow(). It works for evey value a^b which b <= 30. I'm aware that I should be using x % 1000000007 to prevent integers overflows.

#include <stdio.h>
    int main(void) {
        int i, a, b, rst;
        rst = 1;
        scanf("%d %d", &a, &b);
        for (i = 0; i < b; i++){
            rst = rst * a;
            if( b == 0){
                rst = 1;
            }           
        }
        printf("%d\n", rst % 1000000007);
        return 0;
    }

Why does it returns a "0" for example on "2^40 % 1000000007" even though I'm using % 1000000007?

What is the logic behind your `% 1000000007`? Where did that particular number come from? If `int` is 32 bits on your system, then it can't hold a vale of 2**40. Try adding a `printf` call or using a debugger to track the value of `rst` through and after the loop. — Keith Thompson, Mar 28 '18 at 23:04
A quick Google search indicates that `% 1000000007` is common in programming contests: https://www.geeksforgeeks.org/modulo-1097-1000000007/ — Keith Thompson, Mar 28 '18 at 23:05
The problem is that after 32 times through the loop, the value in `rst` is 0. That's because 2^32 mod 2^32 = 0. — user3386109, Mar 28 '18 at 23:07

score 1 · Accepted Answer · answered Mar 28 '18 at 23:13

1

First, you don't need if statement in for loop.
Second, you are trying to stop integer overflow after it already happens. So you need to do it after every multiplication operation.
Third, you can use unsigned long long int instead of int, because int is machine dependent (may be 1000000007 is too big for int on your machine).

I guess this should work:

#include <stdio.h>

int main()
{
    unsigned long long int i, a, b, rst;

    scanf("%llu %llu", &a, &b);

    rst = 1;
    for (i = 0; i < b; i++){
        rst = (rst * a) % 1000000007;
    }
    printf("%llu\n", rst);

    return 0;
}

answered Mar 28 '18 at 23:13

Eziz Durdyyev

1,110
2
16
34

It's probably not `1000000007` that's too big for `int` (it's less than 32 bits). It's `rst`. – Keith Thompson Mar 29 '18 at 00:22
@KeithThompson But sir, I think `rst` is not going to be bigger than `1000000007`. Or Am I missing something? – Eziz Durdyyev Mar 29 '18 at 00:27
The loop computes `a**b` (a raised to the b'th power). The example the OP used was 2**40. Your modified version avoids overflow by applying `% 1000000007` at each step. – Keith Thompson Mar 29 '18 at 01:09
@KeithThompson, So you are saying that my code prints wrong answer (which is 511620083)? – Eziz Durdyyev Mar 29 '18 at 01:35
I wasn't talking about your code. I'm saying that in the OP's code, it's not `1000000007 ` that's too big for `int`, it's `rst` when `a` and `b` are `2` and `40`, respectively. – Keith Thompson Mar 29 '18 at 16:26

Even though I use % 1000000007 it still results on 0

1 Answers1