Not using % or any java built in methods (math), how to do modulo exponentiation?

Question

So I need to do modulo exponentiation using 2^N mod M, but I cant use % or any built in java.math or Math method. Applying mod M as 2^N increases seems* like it would work. But is doesn't seem to ( or im just doing it wrong...)

int N = 63;
int M = 1000;
int result;
while (n > 0)
    {
        power *= 2;
        n --;   
        // this part defn doesnt work... best idea so far 
        if (power >M)
        {
            result = power - m; 
        }

    }

Answer 1

Per §15.17.3 "Remainder Operator %" of The Java Language Specification, Java SE 7 Edition, (a/b)*b+(a%b) is always equal to a. Turning this around, we have a%b == a - (a/b)*b. So, you should be able to write:

power *= 2;
power -= (power/M) * M;

Or, since you're only multiplying by two each time, you know that power cannot exceed M before this operation, so you can rewrite the above as:

power *= 2;
if (power > M) {
    power -= M;
}

Answer 2

Maybe power -= m instead of result = power - m?

Answer 3

Since BigInteger.modPow already implements this, you should just look at the source code of BigInteger.

Answer 4

Annotated code:

    int M = 13;
    int result = 2;
    int n = 10;

    while (--n > 0) // do n iterations multiplying the number with 2
        result *= 2;

    if (M < 0) // safe guard if someone gives you a negative M then flip it
        M *= -1;

    while ((result-M) >= 0) // keep subtracting M until right before it turns negative
        result -= M;

Remember though, that integers are not big enough for 2^63 like your code shows you're trying to do. ints are 32 bit signed, so 2^31 to -2^31-1 is the range.

Your version seems also to do modulus on each iteration of multiplication. You can do that, too. And it will allow you to use 2^63 like your code tries:

    int M = 13;
    int result = 2;
    int n = 10;

    if (M < 0)
        M *= -1;

    while (--n > 0) {
        result *= 2;
        while ((result-M) >= 0)
            result -= M;
    }

Answer 5

Assumptions: power and modulo > 0, a validation should be in place before calling this method.

long modPow(long x, long power, long modulo) {
  if (power > 1) {
    x = modPow(x, power / 2, modulo) * modPow(x, (power + 1) / 2, modulo);
  }
  return x - x / modulo * modulo;
}

call it:

result = modPow(2, power, modulo);

Here is a recursive version. If power is too big to handle it, we split it in 2. We then return x % modulo(inspired by "ruakh example"). We also know that:

y = y / 2 + (y + 1) / 2

so

x^n = x^(n/2) * x^[(n+1)/2]

This way, we know that every modPow call will return a number smaller than modulo every time.

Advantages? Parallelization and if you want to make things even fancier, add memoisation.

You can easily convert my version in a Fork / Join model, you can find more details about it here

Answer 6

Haven't you noticed that it is the power of 2 ? Why hadn't you used it?

2^N mod M is to be counted as

long power=1L << N;
long temp=power/M;
long result= power-temp*M;

Answer 7

You can just use power-=M as the modulo is nothing but continuous subtraction of the divisor from divident until the divident<divisor.

The below should work

public class HelloWorld{
public static void main(String []args){
int N = 63;
int M = 1000;
long result=0;
long power=1;
for(int i=0;i<N;i++)
    {
        power *= 2;
        N--; 
       if (power >=M)
        {
            power = power - M; 
        }

    }
    System.out.println("power:"+power);
     }
}