Question

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.

Answer 1

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

Answer 2

If you can describe the functionality I can help

Answer 3

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

Answer 4

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 ;
}

Answer 5

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!

Answer 6

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