recursion for modular arithmetic

Question

I'm trying to compute this:

x^y (mod a)

Using recursion as it works better for larger numbers. Here's what I have:

public int mod (int x, int y, int a){

if(y == 2){
 return x^2%a;
}
if(y%2 == 1){
  return a%m*mod(x , y/2, a);
}
if(y%2 == 0 ){
return mod(x, y/2, a);
}


}

The code doesnt work and another issue is the "missing return statement" error at the last bracket. What can be done to fix this?

There is no recursion in your code. Use Else if instead of last If, — Rishi Goel, Oct 03 '16 at 07:55
Use `else if` and `else` to sort your missing `return` statement issue assuming y is always a whole number — Nick is tired, Oct 03 '16 at 07:56
@Rishi Goel there is recursion in his second and third `if`s — Nick is tired, Oct 03 '16 at 07:57
The method's signature says that an _int_ must be returned, so whatever route the flow takes you must be able to return an _int_. So change the last if to Else if as suggested by @RishiGoel — abarisone, Oct 03 '16 at 07:58
Possible duplicate of ["Missing return statement" within if / for / while](http://stackoverflow.com/questions/23058029/missing-return-statement-within-if-for-while) — Julien Lopez, Oct 03 '16 at 08:11
`x^2%a` does not do what you think it does. First it evaluates `2 % a`, then it does a *bitwise exclusive OR* (`^`) between `x` and the result of the `2 % a` evaluation. Assuming you meant `x²`, try `x * x % a` instead. — Andreas, Oct 03 '16 at 08:19
What is the variable 'm' that is written in the your piece of code as "return a%m*mod(x , y/2, a);" ? — thread-game, Oct 03 '16 at 08:36

score 3 · Answer 1 · edited Oct 03 '16 at 09:28

In Java, a function, which return type is not void, must return some value. Unfortunately, the compiler isn't smart enough to understand that your if statements cover all range of input parameter's values. The compiler assumes that all your conditions can evaluate to false, thus making this function return no value on this case. So it cannot prove the function's correctness, and reports an error.

score 2 · Answer 2 · edited Oct 03 '16 at 09:28

Your last if statement if(y%2 == 0) is redundant because there are only two possibilities for y%2: it is either 0 or 1.

You checked if it equals 1, so if that condition is wrong, you don't need to check if it equals 0, it is definitely going to be equal to 0 if it is not equal to 1.

Remove that last if and it works fine:

public int mod (int x, int y, int a){

if(y == 2){
 return x^2%a;
}
if(y%2 == 1){
  return a%m*mod(x , y/2, a);
}

return mod(x, y/2, a);


}

recursion for modular arithmetic

2 Answers2