## bluebrandon 3 years ago Can someone help me write a non-recursive version if this function in C? http://db.tt/0NISjQXX I just started learning C after Scheme and loops are still kind of confusing for me.

1. DBhatta

The code doesn't look like c. if it is which version or type is it?

2. rivermaker

If you can describe the functionality I can help

3. rivermaker

Ok is it computing \[x^{e} \mod m\] And you can write a recursive C version.

4. rivermaker

int xsqrm( int x, int m) { return (x * x) % m int powermod2(int x, int e, int m) { if (e == 0) return 1; if (e % 2 == 0) return powermod2(xsqrm(x, m), e/2); return (x * powermod2(xsqrm(x, m), e/2)) % m ; }

5. bluebrandon

for anyone curious this is the solution I came up with int powmod2(int x, int e, int m) { int y = 1; while (e!= 0) { if (e%2 == 0) { e = e/2; x = (x*x)%m; } else { e = (e-1)/2; y = (x*y)%m; x = (x*x)%m; } } return y; } My problem was that I was missing a step in the odd case that I was able to introduce with the y variable. The original I needed to convert this was a recursive version written in scheme. Thanks for your help though!

6. rivermaker

e = e/2 is enough in both cases; because integer division truncates. So you can remove the two statements inside the if and else and replace by e /= 2 in the while loop