converting recursive function to iterative
 

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!

Re: converting recursive function to iterative
 

On 11 May, 12:21, V <vishal.st...@gmail.com> wrote:
> 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)

Re: converting recursive function to iterative
 

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

Re: converting recursive function to iterative
 

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

n May 12, 6:54 pm, V <vishal.st...@gmail.com> wrote:
> 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
> {
> {
CORRECTION----> i--;
> while (i--)
> {
> result *= 2;
> }
>
> result *= mul (V,c);
> }
> return result;
> }
>
> }

Re: converting recursive function to iterative
 

V <vishal.study@gmail.com> writes:

> 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.

--
Ben.