Recursion to Iteration - Scheme to C

Question

Can somewone help me convert this scheme function:

#lang racket
(define (powmod2 x e m)    
  (define xsqrm (remainder (* x x) m))    
  (cond [(= e 0) 1]    
        [(even? e) (powmod2 xsqrm (/ e 2) m)]    
        [(odd? e) (remainder (* x (powmod2 xsqrm (/ (sub1 e) 2) m)) m)]))

Into a function in C, and don't use recursion i.e use iteration.

I'm out of ideas', the part that is bothering me is when e is odd and then the recursive call is in the remainder function. I dont know how to transfer that in a while loop? any tips or suggestions:

This is what i have so far:

int powmod2(int x, int e, int m) {
    int i = x;
    int xsqrm = ((x * x) % m);
    while (e != 0){
        if (e%2 == 0) {
            x = xsqrm;
            e = (e/2);
            xsqrm = ((x * x) % m);
        }
        else {
            i = x; 
            x = xsqrm;
            e = (e - 1)/2;
            xsqrm = ((x * x) % m); 

        }
    }
    e = 1;
    return (i*e)%m;

}

Answer 1

The even version is straightforward because the code has been written tail recursively so the call to (powmod2 xsqrm (/ e 2) m) can be expressed iteratively by replacing e with half of e and x with its square modulo m:

int powmod2(int x, int e, int m) { /* version for when e is a power of 2 */
  while ((e /= 2) != 0)
    x = (x * x) % m;
  return x;
}

However the odd version has not been written tail recursively. One approach is to create a helper method that uses an accumulator. This helper method can then be written tail recursively for both even and odd exponent. You can then transform that into an iteration.

Answer 2

You are having trouble doing the conversion because the original scheme code is not tail recursive. Try to add extra parameters to powmod2 so that you do not need to do the multiplication by remainder in the odd case after calling the recursive function.

To illustrate, its hard to loopify the following function

int fac(n){
    if(n == 0) {
        return 1;
    }else{
        return n * fac(n-1)
    }
}

But it is easy to loopify the version with an accumulation parameter

int fac(n, res){
    if(n == 0) {
        return res;
    }else{
        return fac(n-1, res*n)
    }
}

int real_fac(n){ return fac(n, 1); }