R Glover - 4 years ago 140

Java Question

So I am using this modular exponentiation algorithm I saw on Wikipedia somewhere and it has been working fine for me for small numbers. But when I use larger numbers (E.g. 7000000000) it always returns a 0.

`public static void main(String[] args) {`

System.out.println(modPow(2L, 7000000000L - 1L, 7000000000L));

}

public static long modPow(long base, long exponent, long modulus) {

long result = 1L;

base = base % modulus;

while(exponent > 0) {

if(exponent % 2 == 1) {

result = (result * base) % modulus;

}

exponent = exponent >> 1;

System.out.println(result);

base = (base*base) % modulus;

}

return result;

}

I tracked the problem down to the result variable, as the function loops it has the values:

`2`

8

128

32768

2147483648

-4854775808

0

0

...0s onward

This clearly shows that the result variable is being stored as an int, but I have clearly defined it as a long. I have tried adding (long) to all the calculations in case it was casting it to an int for some reason but that doesn't work.

It is probably something simple or basic that I am missing but I can't see why this isn't working. Any help is greatly appreciated.

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

Your `result * base`

overflows `long`

.

Add something like the below statement inside your `if`

```
System.out.println("result * base = " + result*base);`
```

and you will see:

```
result * base = 2
2
result * base = 8
8
result * base = 128
128
result * base = 32768
32768
result * base = 2147483648
2147483648
result * base = -9223372036854775808
-4854775808
```

Note that `Long.MAX_VALUE`

is 9223372036854775807

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**