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

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 .

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 unful) 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)

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

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

V 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
> {
> {
> while (i--)
> {
> result *= 2;
> }
>
> result *= mul (V,c);
> }
> return result;
> }
> }

I have no idea what this is about, since you didn't bother to quote
anything. However, consider how much more understandable the above
is when written (generating same code) as:

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

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

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.


** Posted from http://www.teranews.com **

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.