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!

[Jarno A Wuolijoki]

On Mon, 27 Oct 2003, Eric Sosman wrote:

"E. Robert Tisdale" wrote:

dmattis wrote:

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?

double Power(double x, unsigned int n) {
return (0 < n)? Power(x, n/2)*Power(x, n - n/2): 1.0;
}

I confess that I considered suggesting this method, but
then decided that wanton cruelty was not (yet) justified.

Well, either that or the interpretation of "suitable base case to
stop the recursion" might need some clarification.

[Arthur J. O'Dwyer]

On Tue, 28 Oct 2003, Jarno A Wuolijoki wrote:

On Mon, 27 Oct 2003, Eric Sosman wrote:

"E. Robert Tisdale" wrote:

double Power(double x, unsigned int n) {
return (0 < n)? Power(x, n/2)*Power(x, n - n/2): 1.0;
}

I confess that I considered suggesting this method, but
then decided that wanton cruelty was not (yet) justified.

Well, either that or the interpretation of "suitable base case to
stop the recursion" might need some clarification.

In particular, where is it guaranteed that the base case (n <= 0)
is ever reached? I admit I'm not conversant in the details of
C floating point, but it seems like an unwarrantedly dubious
assumption to be making. What's to say that 1e-100/2 != 1e-100 ?

-Arthur

[Irrwahn Grausewitz]

"Arthur J. O'Dwyer" <aj*@nospam.and rew.cmu.edu> wrote:

On Tue, 28 Oct 2003, Jarno A Wuolijoki wrote:

On Mon, 27 Oct 2003, Eric Sosman wrote:

> "E. Robert Tisdale" wrote:
> >
> > double Power(double x, unsigned int n) {
> > return (0 < n)? Power(x, n/2)*Power(x, n - n/2): 1.0;
> > }
>
> I confess that I considered suggesting this method, but
> then decided that wanton cruelty was not (yet) justified.

Well, either that or the interpretation of "suitable base case to
stop the recursion" might need some clarification.

In particular, where is it guaranteed that the base case (n <= 0)
is ever reached? I admit I'm not conversant in the details of
C floating point, but it seems like an unwarrantedly dubious
assumption to be making. What's to say that 1e-100/2 != 1e-100 ?

Err, n is of type unsigned int, thus all divisions are integer
divisions...

Regards
--
Irrwahn
(ir*******@free net.de)

[Arthur J. O'Dwyer]

On Tue, 28 Oct 2003, Irrwahn Grausewitz wrote:

"Arthur J. O'Dwyer" <aj*@nospam.and rew.cmu.edu> wrote:

> > "E. Robert Tisdale" wrote:
> >
> > double Power(double x, unsigned int n) {
> > return (0 < n)? Power(x, n/2)*Power(x, n - n/2): 1.0;
> > }

In particular, where is it guaranteed that the base case (n <= 0)
is ever reached? I admit I'm not conversant in the details of
C floating point, but it seems like an unwarrantedly dubious
assumption to be making. What's to say that 1e-100/2 != 1e-100 ?

Err, n is of type unsigned int, thus all divisions are integer
divisions...

Oops. I was thrown by the use of 'double' everywhere else.
Seems silly to use 'double' for the first operand if you're only
going to allow positive integers for the second operand...
plus, in this case Tisdale's solution does exponentially more
work than it really has to. There should be only one call
to Power() within the function itself.

(Proper solution left as an exercise for the OP.)

-Arthur

[Christian Bau]

In article
<Pi************ *************** ********@unix47 .andrew.cmu.edu >,
"Arthur J. O'Dwyer" <aj*@nospam.and rew.cmu.edu> wrote:

On Tue, 28 Oct 2003, Irrwahn Grausewitz wrote:

"Arthur J. O'Dwyer" <aj*@nospam.and rew.cmu.edu> wrote:

>> > "E. Robert Tisdale" wrote:
> > >
> > > double Power(double x, unsigned int n) {
> > > return (0 < n)? Power(x, n/2)*Power(x, n - n/2): 1.0;
> > > }

In particular, where is it guaranteed that the base case (n <= 0)
is ever reached? I admit I'm not conversant in the details of
C floating point, but it seems like an unwarrantedly dubious
assumption to be making. What's to say that 1e-100/2 != 1e-100 ?

Err, n is of type unsigned int, thus all divisions are integer
divisions...

Oops. I was thrown by the use of 'double' everywhere else.
Seems silly to use 'double' for the first operand if you're only
going to allow positive integers for the second operand...
plus, in this case Tisdale's solution does exponentially more
work than it really has to. There should be only one call
to Power() within the function itself.

I think it does more than exponentially more work than needed...

What is n - n/2 if n is equal to 1?

[Peter Nilsson]

Irrwahn Grausewitz <ir*******@free net.de> wrote in message news:<p8******* *************** **********@4ax. com>...

"Arthur J. O'Dwyer" <aj*@nospam.and rew.cmu.edu> wrote:

On Tue, 28 Oct 2003, Jarno A Wuolijoki wrote:

On Mon, 27 Oct 2003, Eric Sosman wrote:
> "E. Robert Tisdale" wrote:
> >
> > double Power(double x, unsigned int n) {
> > return (0 < n)? Power(x, n/2)*Power(x, n - n/2): 1.0;
> > }
>
> I confess that I considered suggesting this method, but
> then decided that wanton cruelty was not (yet) justified.

Well, either that or the interpretation of "suitable base case to
stop the recursion" might need some clarification.

In particular, where is it guaranteed that the base case (n <= 0)
is ever reached? I admit I'm not conversant in the details of
C floating point, but it seems like an unwarrantedly dubious
assumption to be making. What's to say that 1e-100/2 != 1e-100 ?

Err, n is of type unsigned int, thus all divisions are integer
divisions...

The floating point reference is a red herring. Think about what the
function will do when n is 1.

--
Peter

[Glen Herrmannsfeldt]

"James Hu" <jx*@despammed. com> wrote in message
news:x9******** ************@co mcast.com...

On 2003-10-27, dmattis <dm*****@yahoo. com> wrote:

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?
This is not a C question... but the C answer is use pow() (unless you
are purposefully avoiding floating point, in which case a table lookup
is in order).

The algorithm described, in non-recursive form, is commonly used in
languages that supply an integer exponentiation operator. A table
dimensioned INT_MAX-INT_MIN+1 will take up a lot of memory.
<DYOHW> Rewrite your word problem into a recurrence relationship. Use
induction to prove this recurrence correctly calculates x to the nth
power. It should be obvious at that point what your function should
look like and what your base case is. </DYOHW>

Yes, he should do that.

-- glen

[James Hu]

On 2003-10-28, Glen Herrmannsfeldt <ga*@ugcs.calte ch.edu> wrote:

"James Hu" <jx*@despammed. com> wrote in message
news:x9******** ************@co mcast.com...

On 2003-10-27, dmattis <dm*****@yahoo. com> wrote:

> 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?
This is not a C question... but the C answer is use pow() (unless you
are purposefully avoiding floating point, in which case a table lookup
is in order).

The algorithm described, in non-recursive form, is commonly used in
languages that supply an integer exponentiation operator.

Yes, but those typically take a floating point type for the x argument,
and an int type for the n argument.
A table dimensioned INT_MAX-INT_MIN+1 will take up a lot of memory.

That is an imaginative approach, but not what I had in mind.

#include <stdint.h>

static int8_t hbit[256] =
{-1
,0
,1,1
,2,2,2,2
,3,3,3,3,3,3,3, 3
,4,4,4,4,4,4,4, 4,4,4,4,4,4,4,4 ,4
,5,5,5,5,5,5,5, 5,5,5,5,5,5,5,5 ,5,5,5,5,5,5,5, 5,5,5,5,5,5,5,5 ,5,5
,6,6,6,6,6,6,6, 6,6,6,6,6,6,6,6 ,6,6,6,6,6,6,6, 6,6,6,6,6,6,6,6 ,6,6
,6,6,6,6,6,6,6, 6,6,6,6,6,6,6,6 ,6,6,6,6,6,6,6, 6,6,6,6,6,6,6,6 ,6,6
,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7 ,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7 ,7,7
,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7 ,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7 ,7,7
,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7 ,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7 ,7,7
,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7 ,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7 ,7,7
};

int int_pow(int x, uint8_t n)
{
int t = 1;
if (n == 0) return 1;
if (x == 0) return 0;
switch (hbit[n]) {
case 7: if (n & 1) t *= x; n >>= 1; x *= x;
case 6: if (n & 1) t *= x; n >>= 1; x *= x;
case 5: if (n & 1) t *= x; n >>= 1; x *= x;
case 4: if (n & 1) t *= x; n >>= 1; x *= x;
case 3: if (n & 1) t *= x; n >>= 1; x *= x;
case 2: if (n & 1) t *= x; n >>= 1; x *= x;
case 1: if (n & 1) t *= x; n >>= 1; x *= x;
default: if (n & 1) t *= x;
}
return t;
}

-- James

[Irrwahn Grausewitz]

Christian Bau <ch***********@ cbau.freeserve. co.uk> wrote:

"Arthur J. O'Dwyer" <aj*@nospam.and rew.cmu.edu> wrote:

> >> > "E. Robert Tisdale" wrote:
> >> > >
> >> > > double Power(double x, unsigned int n) {
> >> > > return (0 < n)? Power(x, n/2)*Power(x, n - n/2): 1.0;
> >> > > }

<snip> plus, in this case Tisdale's solution does exponentially more
work than it really has to. There should be only one call
to Power() within the function itself.

I think it does more than exponentially more work than needed...

What is n - n/2 if n is equal to 1?

Arrgh, Trollsdale did it again!

And on first glance I thought he actually posted valid code; stupid me.
--
Irrwahn
(ir*******@free net.de)

[Marcus Lessard]

Maybe it's just me but doesn't the contrived nature of the function scream
out "Homework Assignment?" Maybe I'm missing something but I just can't see
why you'd ever want to compute this value..

Alea iacta

"Julian V. Noble"

Here is tested C code for raising an integer to an integer power,
recursively. (I hope this isn't a HW assignment but a legitimate
query.)