Recursive Functions

[dmattis]

I am trying to write a recursive version of Power(x,n) that works by
breaking n down into halves(where half of n=n/2), squaring
Power(x,n/2), and multiplying by x again if n was odd, and to find a
suitable base case to stop the recursion. Can someone give me an
example of this?

Thanks!

[Tim Woodall]

James Hu <jx*@despammed. com> wrote in message news:<Se******* *************@c omcast.com>...

On 2003-10-29, Tim Woodall <go****@woodall .me.uk> wrote:

Richard Heathfield <do******@addre ss.co.uk.invali d> wrote in message news:<bn******* ***@hercules.bt internet.com>.. .
I'm surprised there is much if any difference:

long mpow(long x, long e)
{
long r=1;

while(e)
{
if(e&1)
r*=x;
x*=x;
e>>=1;
}
return r;
}

Its fairly trivial to remove one multiplication at the cost of n if
tests (where n is the number of bits in e) and one multiplication can
become an assignment but other than that I don't think fewer
multiplications are possible using the square and multiply idiom.

double ulpow (double x, unsigned long n)
{
double t = 1;

if (n & 1) t = x;
while (n >>= 1) {
x *= x;
if (n & 1) t *= x;
}
return t;
}

Am I missing something? Where did we add an additional test per
iteration?

You need more tests that that. but an extra
while(!(n&1)) {
n >>= 1;
x*=x;
}
might be sufficient to cover the cases where the least significant
bit of n isn't 1. But you need an extra test for n==0 otherwise my
while loop is infinite. but you can then drop your first if as it will
always be true.

I think I was probably wrong about needing all the extra test but I
was thinking of trying to do it all in one loop where you need a
if(t==1) t=x else t*=x;

Tim.

[James Hu]

go****@woodall. me.uk (Tim Woodall) wrote in message news:<fa******* *************** ****@posting.go ogle.com>...

James Hu <jx*@despammed. com> wrote in message news:<Se******* *************@c omcast.com>...

double ulpow (double x, unsigned long n)
{
double t = 1;

if (n & 1) t = x;
while (n >>= 1) {
x *= x;
if (n & 1) t *= x;
}
return t;
}

You need more tests that that. [...]

Tim, I seem to be unable to find a case that causes the
above routine to misbehave. Could you give me a hint?

Thanks,

-- James

[Eric Sosman]

James Hu wrote:

go****@woodall. me.uk (Tim Woodall) wrote in message news:<fa******* *************** ****@posting.go ogle.com>...

James Hu <jx*@despammed. com> wrote in message news:<Se******* *************@c omcast.com>...

double ulpow (double x, unsigned long n)
{
double t = 1;

if (n & 1) t = x;
while (n >>= 1) {
x *= x;
if (n & 1) t *= x;
}
return t;
}

You need more tests that that. [...]

Tim, I seem to be unable to find a case that causes the
above routine to misbehave. Could you give me a hint?

This code avoids multiplying by unity if `n' is odd,
but still performs the "wasted" multiplication if `n' is
even. Consider the case for `n' equal to 2:

t = 1
if (n & 1) [false]
while (n >>= 1) [n <- 1, true]
x *= x
if (n & 1) [true]
t *= x [t <- 1 * x, wasted]
while (n >>= 1) [n <- 0, false]

The most convenient way to avoid the wastage may be
to use two loops in sequence. Just typed in, untested:

if (n == 0)
return 1;
while (!(n & 1)) {
x *= x;
n >>= 1;
}
t = x;
while (n >>= 1) {
x *= x;
if (n & 1)
t *= x;
}

--
Er*********@sun .com

[James Hu]

Eric Sosman <Er*********@su n.com> wrote in message news:<3F******* ********@sun.co m>...

James Hu wrote:

Tim, I seem to be unable to find a case that causes the
above routine to misbehave. Could you give me a hint?

This code avoids multiplying by unity if `n' is odd,
but still performs the "wasted" multiplication if `n' is
even.

I see now. Thanks!

-- James

[Nudge]

Richard Heathfield wrote:

Well, I was indeed comparing different algorithms. My mistake was to label
them "recursive" and "iterative" . It was in fact the difference between
square-and-multiply and multiply-n-times that I was attempting to
highlight, and I made a complete pig's breakfast of it by attaching
informal labels ("recursive" and "iterative" ) to these algorithms instead
of spelling out precisely what I mean. Silly of me.

When tail-recursion optimization can be performed on a recursive
algorithm, it can be written iteratively.

AFAIU, in such cases, the iterative version will perform better than
the recursive version.