Recursive Functions

[Tim Woodall]

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]

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]

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

 

[James Hu]

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]

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.