CODEWITHSUNDEEP
javarecursionexponentmodular-arithmetic
Oria Gruber
Oria Gruber

Reputation: 1533

Turn recursive program to iterative

A friend challenged me to write a program that gets three integers (int a, int n, int k) and computes efficiently as possible, a^n mod k

I came up with this solution

public static int rec(int a,int n,int k) //calc a^n mod k
    {
        if(n == 1)
            return a % k; 
        int exp1 = rec(a, n/2, k), exp2 = exp1;
        if(n % 2 == 1)
            exp2 = rec(a, n/2 + 1, k);

        return (exp1 * exp2) % k;
    }

It's an incredibly simple recursive solution, reliant on the fact that a^(b+c) mod d = (a^b mod d * a^c mod d) mod d, and runs in logarithmic time. At least theoretically.

In practice when we measured our solution, his linear time solution was better than my solution. I suspect it's due to me using recursion rather than loops. Does that make sense? If so - how can I turn this code into an iterative program?

Upvotes: 3

Views: 182

Answers (1)

opensam
opensam

Reputation: 368

Does that make sense?

Yes. As Boris The Spider pointed out, there is no tail optimization in Java.

how can I turn this code into an iterative program?

Let me copy-paste an iterative solution to calculate power of a number from here

int pow(int x, int n) {
int res = 1;
while(n > 0) {
    if(n % 2 == 1) {
        res = res * x;
    }
    x = x * x;
    n = n / 2;
}
return res;
}

Disclaimer : Although the above code looks ok to me, I haven't tested it personally.

Upvotes: 1

Related Questions