converting recursive function to iterative

[V]

Hello:

Consider the following recursive function:

inline u64 multiplyPower(u64 V, u8 i, u64 c)
{
if (i == 0)
return V;
else
return mul( multiplyPower(V,i-1,c) , c);
}

where mul is defined as:
inline u64 mul(u64 V, u64 c)
{
if ((V & 0x8000000000000000 ))
return (V<<1) ^ c;
else
return V<<1;
}

I would like to convert the recursive function multiplyPower() to an
iterative one. Does it look possible? Can some one please help.
Thanks!

 

[Spiros Bousbouras]

Hello:

Consider the following recursive function:

inline u64 multiplyPower(u64 V, u8 i, u64 c)
{
if (i == 0)
return V;
else
return mul( multiplyPower(V,i-1,c) , c);

}

where mul is defined as:
inline u64 mul(u64 V, u64 c)
{
if ((V & 0x8000000000000000 ))
return (V<<1) ^ c;
else
return V<<1;

}

I would like to convert the recursive function multiplyPower() to an
iterative one. Does it look possible? Can some one please help.

Yes it is possible and quite easy. I am however reluctant
to provide you with a complete answer since this looks
like homework. I will try to give you some hints although
I think it will be hard finding the middle point between
trivial (hence unhelpful) hints and a complete solution.

First, the code for mul is irrelevant. As long as you know
the return type, that's all you need to turn the recursion
into a loop. Second, try working out on a piece of paper
the symbolic result of multiplyPower for small functions
of i and see if that gives you a hint.

For example
i=0 multiplyPower returns V
i=1 multiplyPower returns mul(V,c)

 

[V]

Following is what I can think of...but it doesn't seem to be working ;-
( Any pointers...Thanks!

inline u64 multiplyPower_iter (u64 V, u8 i, u64 c)
{
u64 result=1;
int j;

if ((i == 0))
return V;
else
{
{
while (i--)
{
result *= 2;
}

result *= mul (V,c);
}
return result;
}
}

 

[V]

Mistyped one thing (shown as CORRECTION below)...but still doesn't
work ;-(

 

[Ben Bacarisse]

Mistyped one thing (shown as CORRECTION below)...but still doesn't
work ;-(

Did you follow Spiros Bousbouras advice?

The recursive version does this:

i=0 return V
i=1 return mul(mp(V,0,c),c) i.e. mul(V,c)
i=2 return mul(mp(V,1,c),c) i.e. mul(mul(V,c),c)
i=3 return mul(mp(V,2,c),c) i.e. mul(mul(mul(V,c),c),c),c)

You need to repeatedly apply mul to V which is not what your code
does.