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!

[Sheldon Simms]

On Mon, 27 Oct 2003 09:54:05 -0800, 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?

This question is off topic here. I would suggest you try
posting in comp.programming, but I can't actually figure out
what you want. You've described the algorithm completely,
what more do you want?

-Sheldon

p.s. I'm hoping that what you want isn't for someone to simply
do your homework for you.

[James Hu]

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

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

-- James

[Eric Sosman]

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?

This seems a fairly clear description of the procedure,
assuming `n' is a non-negative integer. (If `n' can be
negative the problem is harder; if `n' can be a non-integer
problem is much harder.) What problem are you having with
it? Perhaps if you'd show us what you've written thus far,
someone will be able to help.

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

[Richard Heathfield]

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?

/*
untested,
unreadable,
unambitious,
unenthusiastic
*/
#define k \
unsigned char
k Power(k x,k
n){k r=1;if(n
){if(1==n){r=
x;}else{k t =
Power(x,n>>1)
;if(1&n){r=x;
}r *= t*t; }}
return r ;}

--
Richard Heathfield : bi****@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

[Glen Herrmannsfeldt]

"Sheldon Simms" <sh**********@yahoo.com> wrote in message
news:pa****************************@yahoo.com...

On Mon, 27 Oct 2003 09:54:05 -0800, 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?

This question is off topic here. I would suggest you try
posting in comp.programming, but I can't actually figure out
what you want. You've described the algorithm completely,
what more do you want?

Well, to help make it on topic, I sometimes notice C's lack of an integer
power function, such as that described. (Though I believe that it works
better as an iterative function than a recursive function.) Sometimes I use
an SQ macro, which squares an expression through mutliplication. If the
expression is more than a single variable, I hope that the compiler does
common subexpression elimination.

-- glen

[Julian V. Noble]

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?

Thanks!

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

// Recursive raise integer to integer power
//
// If j is even, return (i^2)^(j/2), else return i * (i^2)^(j/2)
//
// ----------------------------------------------------
// (c) Copyright 2003 Julian V. Noble. //
// Permission is granted by the author to //
// use this software for any application pro- //
// vided this copyright notice is preserved. //
// ----------------------------------------------------
#include <math.h>
#include <stdio.h>

int power( int i, int j ); // prototype

int main( void )
{
int a;
int b;

printf("What are m and n? ");
scanf(" %d", &a);
scanf(" %d", &b);

printf( " %d\n", power(a,b) ) ;

return 0;
}

int power( int i, int j )
{
int k;
if (j==0) // i^0 = 1
{ return 1;
}

if (j & 1) // odd?
k = i;
else // even?
k = 1;

return k * power( i*i, j/2);
}

--
Julian V. Noble
Professor Emeritus of Physics
jv*@spamfree.virginia.edu
^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/

"Science knows only one commandment: contribute to science."
-- Bertolt Brecht, "Galileo".

[Julian V. Noble]

Glen Herrmannsfeldt wrote:

"Sheldon Simms" <sh**********@yahoo.com> wrote in message
news:pa****************************@yahoo.com...

On Mon, 27 Oct 2003 09:54:05 -0800, 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?

This question is off topic here. I would suggest you try
posting in comp.programming, but I can't actually figure out
what you want. You've described the algorithm completely,
what more do you want?

Well, to help make it on topic, I sometimes notice C's lack of an integer
power function, such as that described. (Though I believe that it works
better as an iterative function than a recursive function.) Sometimes I use
an SQ macro, which squares an expression through mutliplication. If the
expression is more than a single variable, I hope that the compiler does
common subexpression elimination.

-- glen

You are correct in saying that the iterative is probably better than the
recursive version. If anyone is interested I'll post my iterative version.

--
Julian V. Noble
Professor Emeritus of Physics
jv*@spamfree.virginia.edu
^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/

"Science knows only one commandment: contribute to science."
-- Bertolt Brecht, "Galileo".

[E. Robert Tisdale]

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

[Eric Sosman]

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

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

[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.andrew.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*******@freenet.de)

[Arthur J. O'Dwyer]

On Tue, 28 Oct 2003, Irrwahn Grausewitz wrote:

"Arthur J. O'Dwyer" <aj*@nospam.andrew.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.andr ew.cmu.edu>,
"Arthur J. O'Dwyer" <aj*@nospam.andrew.cmu.edu> wrote:

On Tue, 28 Oct 2003, Irrwahn Grausewitz wrote:

"Arthur J. O'Dwyer" <aj*@nospam.andrew.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*******@freenet.de> wrote in message news:<p8********************************@4ax.com>. ..

"Arthur J. O'Dwyer" <aj*@nospam.andrew.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********************@comcast.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.caltech.edu> wrote:

"James Hu" <jx*@despammed.com> wrote in message
news:x9********************@comcast.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.andrew.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*******@freenet.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.)

[Eric Sosman]

Marcus Lessard wrote:

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

<off-topic>

If computing positive integer powers is of so little
interest, it's hard to see why Knuth gives the topic an
entire section of its own in "The Art of Computer Programming,
Volume II: Seminumerical Algorithms."

The method outlined is the first serious power-computing
algorithm Knuth introduces in that section. He writes that
some authors have declared the method optimal, but he is
kind enough to spare them embarrassment by omitting their
names; clearly they forgot to consider cases like n==15.

</off-topic>

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

[Glen Herrmannsfeldt]

"James Hu" <jx*@despammed.com> wrote in message
news:Nv********************@comcast.com...

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

"James Hu" <jx*@despammed.com> wrote in message
news:x9********************@comcast.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.

The languages I know of supply routines for integer n, and integer, float,
double, complex, and complex double x.

The OP didn't supply the type of x, but the algorithm works for any type
where mulitply is defined.

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

The algorithm also works for n > 255.

-- glen

[Glen Herrmannsfeldt]

"Marcus Lessard" <sp****@spam.com> wrote in message
news:bn**********@pyrite.mv.net...

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

Computing integer powers of numbers is fairly common in scientific
programming, and is one of the relatively few things missing from C used in
scientific programming.

However, requiring it as a recursive function does scream of homework. A
simple for loop should be easier and faster.

-- glen

[Arthur J. O'Dwyer]

On Tue, 28 Oct 2003, Eric Sosman wrote:

<off-topic>
If computing positive integer powers is of so little
interest, it's hard to see why Knuth gives the topic an
entire section of its own in "The Art of Computer Programming,
Volume II: Seminumerical Algorithms."

The method outlined is the first serious power-computing
algorithm Knuth introduces in that section. He writes that
some authors have declared the method optimal, but he is
kind enough to spare them embarrassment by omitting their
names; clearly they forgot to consider cases like n==15.

What's wrong with n==15? The algorithm given is still O(lg N)
in such cases. No, probably Knuth was thinking of *better*
algorithms that could compute powers more quickly -- I don't
know of any, but perhaps a couple of exp() and log() lookup
tables, plus iteration, could do things faster than straight
recursion.

-Arthur

[James Hu]

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

"James Hu" <jx*@despammed.com> wrote in message
news:Nv********************@comcast.com...

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

> "James Hu" <jx*@despammed.com> wrote in message
> news:x9********************@comcast.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.

The languages I know of supply routines for integer n, and integer, float,
double, complex, and complex double x.

Well, lets just call most of those floating point, except for integer
and complex x (which I assume you mean A+Bi with A and B integers, but
C has no such type).
The OP didn't supply the type of x, but the algorithm works for any type
where mulitply is defined.
Since the proposed algorithm does not deal with negative powers, it
is safe to assume the the type of n is unsigned.

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

[.. snip .. ]
The algorithm also works for n > 255.

But not without overflowing the int type. My function does not
prevent overflow from happening, but the caller can check to
make sure overflow will not before invoking the function. And
the caller can then discover the degenerate unity cases and
dispatch it without incurring the function call overhead.

However, here is an alternate implementation (now, with two
table lookups):

#include <stdint.h>
#include <limits.h>

static int32_t xpow[32] =
{0,INT_MAX,46341,1291,216,74,36,22,15,11,9,8,6,6,5 ,5,4,4,4,4,3,3
,3,3,3,3,3,3,3,3,3,2
};

static int8_t hbit[32] =
{-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
};

int32_t int_pow(int32_t x, unsigned n)
{
int32_t t = 1;
int32_t ax;
if (n == 0) return 1;
if (x == 0) return 0;
if (n == 1) return x;
if (x == INT_MIN) return 0;
if (((x<0)?-x:x) >= xpow[(n<32)?n:31])
return (x<0)?((n&1)?INT_MIN:INT_MAX):INT_MAX;
if (x == 1 || x == -1) n &= 1;
switch (hbit[n]) {
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: t *= x;
}
return t;
}
-- James

[Eric Sosman]

"Arthur J. O'Dwyer" wrote:

On Tue, 28 Oct 2003, Eric Sosman wrote:

<off-topic>
If computing positive integer powers is of so little
interest, it's hard to see why Knuth gives the topic an
entire section of its own in "The Art of Computer Programming,
Volume II: Seminumerical Algorithms."

The method outlined is the first serious power-computing
algorithm Knuth introduces in that section. He writes that
some authors have declared the method optimal, but he is
kind enough to spare them embarrassment by omitting their
names; clearly they forgot to consider cases like n==15.

What's wrong with n==15? The algorithm given is still O(lg N)
in such cases. No, probably Knuth was thinking of *better*
algorithms that could compute powers more quickly -- I don't
know of any, but perhaps a couple of exp() and log() lookup
tables, plus iteration, could do things faster than straight
recursion.

The binary method starts with x and then computes x^2,
x^3, x^6, x^7, x^14, x^15 -- six multiplications.

The factor method starts with x and then computes x^2
and x^3 with two multiplications. Letting y = x^3 it then
computes y^2, y^4, y^5 (= x^15) in three more multiplications,
for five in all.

Perhaps not a big deal when `x' is something simple like
a floating-point number -- but worth paying heed to if `x'
is, say, a large matrix.

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

[James Hu]

On 2003-10-28, James Hu <jx*@despammed.com> wrote:
[ ... ]

{0,INT_MAX,46341,1291,216,74,36,22,15,11,9,8,6,6,5 ,5,4,4,4,4,3,3 [ ... ] if (x == INT_MIN) return 0; [ ... ] return (x<0)?((n&1)?INT_MIN:INT_MAX):INT_MAX;

[ ... ]

References to INT_MAX and INT_MIN should be changed to INT32_MAX
and INT32_MIN respectively.

-- James

[gc]

My take

double Power(double x, unsigned int n) {
if(n==0) return 1.;
else return (n&1) ? x*Power(x*x,(n-1)/2) : Power(x*x,n/2);
}

[Richard Heathfield]

Glen Herrmannsfeldt wrote:

"Marcus Lessard" <sp****@spam.com> wrote in message
news:bn**********@pyrite.mv.net...

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

Computing integer powers of numbers is fairly common in scientific
programming, and is one of the relatively few things missing from C used
in scientific programming.

However, requiring it as a recursive function does scream of homework. A
simple for loop should be easier and faster.

Hmmm. I raised 7 to the power 7777 using recursion and iteration. (Since the
result occupies over 6500 decimal digits, I won't display it here!)

The recursive calculation took 0.22 seconds, and the iterative version 1.06
seconds - almost five times slower. Perhaps you could demonstrate an
iterative version that can hold a candle to the recursive technique?

--
Richard Heathfield : bi****@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

[Christian Bau]

In article
<Pi***********************************@unix48.andr ew.cmu.edu>,
"Arthur J. O'Dwyer" <aj*@nospam.andrew.cmu.edu> wrote:

What's wrong with n==15? The algorithm given is still O(lg N)
in such cases. No, probably Knuth was thinking of *better*
algorithms that could compute powers more quickly -- I don't
know of any, but perhaps a couple of exp() and log() lookup
tables, plus iteration, could do things faster than straight
recursion.

Knuth was thinking of the fact that this algorithm uses six
multiplications to calculate x^15, but it can be done using five
multiplications.

[Christian Bau]

In article <bn**********@hercules.btinternet.com>,
Richard Heathfield <do******@address.co.uk.invalid> wrote:

Glen Herrmannsfeldt wrote:

"Marcus Lessard" <sp****@spam.com> wrote in message
news:bn**********@pyrite.mv.net...

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

Computing integer powers of numbers is fairly common in scientific
programming, and is one of the relatively few things missing from C used
in scientific programming.

However, requiring it as a recursive function does scream of homework. A
simple for loop should be easier and faster.

Hmmm. I raised 7 to the power 7777 using recursion and iteration. (Since the
result occupies over 6500 decimal digits, I won't display it here!)

The recursive calculation took 0.22 seconds, and the iterative version 1.06
seconds - almost five times slower. Perhaps you could demonstrate an
iterative version that can hold a candle to the recursive technique?

double power (double x, unsigned long n) {

if (n == 0) {
return 1.0;
} else {
double result = x;
unsigned long k = 1;

while (2*k <= n) k *= 2;
while (k > 1) { k /= 2; result *= (n & k) ? result * x : result; }
return result;
}
}

But your example is much more difficult because the execution time of a
single multiplication depends on the size of the numbers involved, so it
is not the number of operations that counts, but their cost.

[Arthur J. O'Dwyer]

On Tue, 28 Oct 2003, Richard Heathfield wrote:

Glen Herrmannsfeldt wrote:

However, requiring it as a recursive function does scream of homework.
A simple for loop should be easier and faster.
Hmmm. I raised 7 to the power 7777 using recursion and iteration. (Since
the result occupies over 6500 decimal digits, I won't display it here!)

Really. I guess you must have used 'long double', huh? :)
The recursive calculation took 0.22 seconds, and the iterative version 1.06
seconds - almost five times slower. Perhaps you could demonstrate an
iterative version that can hold a candle to the recursive technique?

#include <math.h>

double pow3(double x, unsigned int n)
{
do {
return exp(n*log(x));
} while (1);
}
-Arthur

[Richard Heathfield]

Arthur J. O'Dwyer wrote:

On Tue, 28 Oct 2003, Richard Heathfield wrote:

Glen Herrmannsfeldt wrote:

>
> However, requiring it as a recursive function does scream of homework.
> A simple for loop should be easier and faster.
Hmmm. I raised 7 to the power 7777 using recursion and iteration. (Since
the result occupies over 6500 decimal digits, I won't display it here!)

Really. I guess you must have used 'long double', huh? :)

No, I used bignum routines written in ISO C.

The recursive calculation took 0.22 seconds, and the iterative version
1.06 seconds - almost five times slower. Perhaps you could demonstrate an
iterative version that can hold a candle to the recursive technique?

#include <math.h>

double pow3(double x, unsigned int n)
{
do {
return exp(n*log(x));
} while (1);
}

Ah, I don't think you were taking me entirely seriously. That's a shame,
because I was in fact asking a serious question.

--
Richard Heathfield : bi****@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

[Nudge]

Arthur J. O'Dwyer wrote:

On Tue, 28 Oct 2003, Eric Sosman wrote:

<off-topic>
If computing positive integer powers is of so little
interest, it's hard to see why Knuth gives the topic an
entire section of its own in "The Art of Computer Programming,
Volume II: Seminumerical Algorithms."

The method outlined is the first serious power-computing
algorithm Knuth introduces in that section. He writes that
some authors have declared the method optimal, but he is
kind enough to spare them embarrassment by omitting their
names; clearly they forgot to consider cases like n==15.

What's wrong with n==15? The algorithm given is still O(lg N)
in such cases. No, probably Knuth was thinking of *better*
algorithms that could compute powers more quickly -- I don't
know of any, but perhaps a couple of exp() and log() lookup
tables, plus iteration, could do things faster than straight
recursion.

(x << 4) - x

There. O(1)

/me runs for cover ^_^

[James Hu]

On 2003-10-27, James Hu <jx*@despammed.com> wrote:

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

I am trying to write a recursive version of Power(x,n) that works by
[...]

... the C answer is use pow() (unless you are purposefully avoiding
floating point, in which case a table lookup is in order).

Ok, my previous versions contained minor snafus. This one is tested,
and profiled:

#include <stdint.h>
#include <limits.h>

static int32_t xpow[32] =
{0,INT32_MAX,46340,1290,215,73,35,21,14,10,8,7
,5,5,4,4,3,3,3,3,2,2,2,2,2,2,2,2,2,2,2,1
};

static int8_t hbit[32] =
{-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
};

int32_t int_pow(int32_t x, unsigned n)
{
int32_t t = 1;
if (n == 0) return 1;
if (x == 0) return 0;
if (n == 1) return x;
if (x == INT32_MIN)
return (n&1)?x:INT32_MAX;
if (((x<0)?-x:x) > xpow[(n>31)?31:n])
return (x<0)?((n&1)?INT32_MIN:INT32_MAX):INT32_MAX;
if (n>31)
return (n&1)?x:1;
switch (hbit[n]) {
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: t *= x;
}
return t;
}

-- James

[James Hu]

On 2003-10-29, Richard Heathfield <do******@address.co.uk.invalid> wrote:

Arthur J. O'Dwyer wrote:

On Tue, 28 Oct 2003, Richard Heathfield wrote:

The recursive calculation took 0.22 seconds, and the iterative version
1.06 seconds - almost five times slower. Perhaps you could demonstrate an
iterative version that can hold a candle to the recursive technique?

#include <math.h>
double pow3(double x, unsigned int n)
{
do {
return exp(n*log(x));
} while (1);
}

Ah, I don't think you were taking me entirely seriously. That's a shame,
because I was in fact asking a serious question.

Richard, could you post your iterative version? Maybe we can help
you tweak it.

-- James

[Marcus Lessard]

Then maybe it is just me, but I didn't explain myself clearly. The
objective of calculating powers is all well and good and no doubt of use but
what confuses me is the highly specified nature of the algorithm: (from OP):

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

Will this be more efficient? Or is it just the solution demanded by the
professor?

ML

"Eric Sosman"

If computing positive integer powers is of so little
interest, it's hard to see why Knuth gives the topic an
entire section of its own in "The Art of Computer Programming,
Volume II: Seminumerical Algorithms."

[Tim Woodall]

Richard Heathfield <do******@address.co.uk.invalid> wrote in message news:<bn**********@hercules.btinternet.com>...

Glen Herrmannsfeldt wrote:

<snip>

However, requiring it as a recursive function does scream of homework. A
simple for loop should be easier and faster.

Hmmm. I raised 7 to the power 7777 using recursion and iteration. (Since the
result occupies over 6500 decimal digits, I won't display it here!)

The recursive calculation took 0.22 seconds, and the iterative version 1.06
seconds - almost five times slower. Perhaps you could demonstrate an
iterative version that can hold a candle to the recursive technique?

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. IIRC
Knuth goes into this in some detail and mentions some exponents where
this idiom does not use the minimum possible number of
multiplications. (e=15 being the smallest which can be evaluated as
mpow(mpow(x,3),5))

(Getting very OT now. squaring is particularly fast when very big
number are involved where FFT techniques become "efficient")

Tim.

[Wolfgang Riedel]

Richard Heathfield wrote:

Glen Herrmannsfeldt wrote:

"Marcus Lessard" <sp****@spam.com> wrote in message
news:bn**********@pyrite.mv.net...

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

Computing integer powers of numbers is fairly common in scientific
programming, and is one of the relatively few things missing from C used
in scientific programming.

However, requiring it as a recursive function does scream of homework. A
simple for loop should be easier and faster.

Hmmm. I raised 7 to the power 7777 using recursion and iteration. (Since the
result occupies over 6500 decimal digits, I won't display it here!)

The recursive calculation took 0.22 seconds, and the iterative version 1.06
seconds - almost five times slower. Perhaps you could demonstrate an
iterative version that can hold a candle to the recursive technique?

--
Richard Heathfield : bi****@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

6573 (!?)

[Arthur J. O'Dwyer]

On Wed, 29 Oct 2003, Richard Heathfield wrote:

Arthur J. O'Dwyer wrote:

On Tue, 28 Oct 2003, Richard Heathfield wrote:

Hmmm. I raised 7 to the power 7777 using recursion and iteration. (Since
the result occupies over 6500 decimal digits, I won't display it here!)

Really. I guess you must have used 'long double', huh? :)

No, I used bignum routines written in ISO C.

[I did figure as much; still, I don't think the original discussion
was meant to generalize to bignums. I thought we'd been talking
about 'foo(double, unsigned int)'.]

The recursive calculation took 0.22 seconds, and the iterative version
1.06 seconds - almost five times slower. Perhaps you could demonstrate an
iterative version that can hold a candle to the recursive technique?

#include <math.h>

double pow3(double x, unsigned int n)
{
do {
return exp(n*log(x));
} while (1);
}

Ah, I don't think you were taking me entirely seriously. That's a shame,
because I was in fact asking a serious question.

:) Well, suppose someone goes and looks up ISO C implementations
of 'exp' and 'log', and plugs them into the above function in the
right places, then. I'd be willing to bet that there's at least
one efficient iterative method of computing exp(n) and log(n),
although maybe not to the appropriate precision for bignum work.
Certainly a bignum solution would need lots of support code.

For a serious solution, you could simulate the recursive solution
by looking at the individual bits of the exponent; but since your
own iterative solution didn't take too long, I'm guessing that
that's what you did already.

-Arthur

[Glen Herrmannsfeldt]

"Marcus Lessard" <sp****@spam.com> wrote in message
news:bn**********@pyrite.mv.net...

Then maybe it is just me, but I didn't explain myself clearly. The
objective of calculating powers is all well and good and no doubt of use but what confuses me is the highly specified nature of the algorithm: (from OP):
"...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..."

Will this be more efficient? Or is it just the solution demanded by the
professor?

Except for some special cases, it is the most efficient set of multiplies to
generate a given power.

In the iterative form, it is the algorithm used by languages that I know of
that supply such an operation.

If n is a power of two, such as 2**m, it will square the number m times.

I suppose as an example for recursive algorithms it is a little better than
factorial.

-- glen

[Eric Sosman]

Richard Heathfield wrote:

Hmmm. I raised 7 to the power 7777 using recursion and iteration. (Since the
result occupies over 6500 decimal digits, I won't display it here!)

The recursive calculation took 0.22 seconds, and the iterative version 1.06
seconds - almost five times slower. Perhaps you could demonstrate an
iterative version that can hold a candle to the recursive technique?

SomeType my_power(SomeType x, unsigned int n) {
/* This is the right-to-left binary method used
* by the O.P., expressed iteratively rather
* than recursively. A similar left-to-right
* method would use one less multiplication
* (note that the first multiplication in this
* method is always by unity, and thus wasted),
* but needs extra code to find the high-order
* 1-bit of `n'. Other methods are faster for
* certain values of `n' (e.g., 15), but are
* also more complicated. See Knuth, "The
* Art of Computer Programming, Volume II:
* Seminumerical Algorithms" Section 4.6.3;
* this is Algorithm A from that section.
*/
SomeType y = 1;

/* Optional: Make an explicit test for x==0 here.
* As things stand, my_power(0,0) -> 1.
*/

for (;;) {
if (n & 1)
y *= x;
if ((n >>= 1) == 0)
return y;
x *= x;
}
}

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

[Marcus Lessard]

"Glen Herrmannsfeldt"
....

If n is a power of two, such as 2**m, it will square the number m times.

I suppose as an example for recursive algorithms it is a little better than factorial.

-- glen

From a mathematical point of view there is no difference in breaking up the
computation into a set of squares and then multiplying. What is going on in
the underlying processing that makes using the squares more efficient than
just multiplying x by itself n times?

ML

[Eric Sosman]

Marcus Lessard wrote:

"Glen Herrmannsfeldt"
...

If n is a power of two, such as 2**m, it will square the number m times.

I suppose as an example for recursive algorithms it is a little better

than

factorial.

-- glen

From a mathematical point of view there is no difference in breaking up the
computation into a set of squares and then multiplying. What is going on in
the underlying processing that makes using the squares more efficient than
just multiplying x by itself n times?

Count the multiplications:

x*x*x*...*x*x*x = x^128

x*x = x^2, x^2*x^2 = x^4, ..., x^64*x^64 = x^128

Which do you think will be faster: 127 multiplications or 7?

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

[Richard Heathfield]

James Hu wrote:

Richard, could you post your iterative version? Maybe we can help
you tweak it.

Well, I'm not really ready to release the underlying library code yet. But
here's the high-level stuff:

while(MF_Compare(a2, zero) != 0)
{
MF_Multiply(t, a3, a1);
MF_Copy(a3, t);
MF_Subtract(t, a2, one);
MF_Copy(a2, t);
}

As you can see, this does involve two copy operations, which I concede is a
bit lame, but eliminating them is not going to make a huge difference. (The
profile suggests that they take up zero time, which can't be quite true, of
course, but you get the general idea.)

The profile says that the recursive version spends 0.21 seconds doing 18
multiplications, whilst the iterative version spends 0.96 seconds doing
7777 multiplications.

--
Richard Heathfield : bi****@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

[Richard Heathfield]

Wolfgang Riedel wrote:

Richard Heathfield wrote:

Hmmm. I raised 7 to the power 7777 using recursion and iteration. (Since
the result occupies over 6500 decimal digits, I won't display it here!)

The recursive calculation took 0.22 seconds, and the iterative version
1.06 seconds - almost five times slower. Perhaps you could demonstrate an
iterative version that can hold a candle to the recursive technique?

6573 (!?)

Yes, exactly right. :-)

In case you want a quick check against your own code, the first few digits
are 21254808227343471907345591571884156862...

and it finishes ...65911020435734015379207.

--
Richard Heathfield : bi****@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

[Dave Vandervies]

In article <bn**********@titan.btinternet.com>,
Richard Heathfield <bi****@eton.powernet.co.uk> wrote:

James Hu wrote:

Richard, could you post your iterative version? Maybe we can help
you tweak it.
Well, I'm not really ready to release the underlying library code yet. But
here's the high-level stuff:

while(MF_Compare(a2, zero) != 0)
{
MF_Multiply(t, a3, a1);
MF_Copy(a3, t);
MF_Subtract(t, a2, one);
MF_Copy(a2, t);
}

As you can see, this does involve two copy operations, which I concede is a
bit lame, but eliminating them is not going to make a huge difference. (The
profile suggests that they take up zero time, which can't be quite true, of
course, but you get the general idea.)

If you have bitwise operators (and-with-1 for "is odd" and shift-right
for "integer divide by two"), you might want to try an iterative
square-and-multiply, something like this:
--------
/*Raise a1 to the power of a2, storing result in a3*/
if(MF_Compare(a2,zero) == 0) /*Assumes return 0 -> equal*/
{
/*Special case, zeroth power is always 1*/
MF_Copy(a3,one);
}
else
{
MF_Copy(a3,a1);
while(MF_Compare(a2,one) > 0) /*assumes return > 0 -> arg1>arg2*/
{
MF_Multiply(t,a3,a3);
/*MF_IS_ODD can be implemented using a bitwise and with 1*/
if(MF_IS_ODD(a2))
{
/*As a side effect of the multiplication, we can put the
result back in the variable we want it to end up in,
and avoid a separate copy operation
*/
MF_Multiply(a3,t,a1);
}
else
{
MF_Copy(a3,t);
}
/*MF_DIVIDE_BY_TWO can be implemented by a bitwise right shift,
avoiding having to do a long-division operation
*/
MF_DIVIDE_BY_TWO(a2);
}
}
/*a3 now contains the desired result*/
--------
This was translated without additional checking from code I wrote that
passed a brief sanity check doing the same thing with unsigned longs.
Any bugs are a result of either translation error or incomplete testing
of the original.

The profile says that the recursive version spends 0.21 seconds doing 18
multiplications, whilst the iterative version spends 0.96 seconds doing
7777 multiplications.
Ahh. So what you were really comparing was a recursive square-and-
multiply(?) and an iterative counted-multiply.
The iterative square-and-multiply should compare somewhat more favorably
with the recursive one.
dave

--
Dave Vandervies dj******@csclub.uwaterloo.ca[O]ur recruitment drive isn't until June, so we're short-handed as it is.

Damn! My copy of the Gay Agenda must be out of date.
--Graham Reed and Zebee Johnstone in the scary devil monastery

[Micah Cowan]

Richard Heathfield <do******@address.co.uk.invalid> writes:

Glen Herrmannsfeldt wrote:

"Marcus Lessard" <sp****@spam.com> wrote in message
news:bn**********@pyrite.mv.net...

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

Computing integer powers of numbers is fairly common in scientific
programming, and is one of the relatively few things missing from C used
in scientific programming.

However, requiring it as a recursive function does scream of homework. A
simple for loop should be easier and faster.

Hmmm. I raised 7 to the power 7777 using recursion and iteration. (Since the
result occupies over 6500 decimal digits, I won't display it here!)

The recursive calculation took 0.22 seconds, and the iterative version 1.06
seconds - almost five times slower. Perhaps you could demonstrate an
iterative version that can hold a candle to the recursive technique?

Richard, are you serious? How about "emulating" the recursion via
stack and iteration? There are several advantages to this, IMHO:

- You have precise control the size of the stack
- If the stack runs out, you can exit gracefully: or even grow
the stack. Try doing that when your implementation's stack
runs out.

--
Micah J. Cowan
mi***@cowan.name

[Glen Herrmannsfeldt]

"Arthur J. O'Dwyer" <aj*@nospam.andrew.cmu.edu> wrote in message
news:Pi**********************************@unix49.a ndrew.cmu.edu...

On Wed, 29 Oct 2003, Richard Heathfield wrote:

Arthur J. O'Dwyer wrote:

On Tue, 28 Oct 2003, Richard Heathfield wrote:
>
> Hmmm. I raised 7 to the power 7777 using recursion and iteration. (Since> the result occupies over 6500 decimal digits, I won't display it here!)
Really. I guess you must have used 'long double', huh? :)

No, I used bignum routines written in ISO C.

[I did figure as much; still, I don't think the original discussion
was meant to generalize to bignums. I thought we'd been talking
about 'foo(double, unsigned int)'.]

Well, mostly the suggestion was int, float, and double, but the basic
algorithm should work for other types.

Though by iterative algorithm I did mean an iterative implementation of the
square and multiply algorithm.

Here is the loop from the OS/360 (not copyrighted) Fortran library routine
for double base to integer power. Not included is the check for a negative
power, and later reciprocal of the result. They use a two register shift,
instead of AND to test the low bit after the shift, which might save one or
two instructions.

PLUS LD FACTOR,ONE LOAD FACTOR OF ONE IN FACTOR REG
LOOP SRDL EXPN,1 SHIFT LOW BIT EXPN REG INTO ADDR REG
LTR ADDR,ADDR TEST SIGN POS ADDR REG FOR MINUS BIT
BC 10,JUMP IF SIGN BIT NOT MINUS,BRANCH TO JUMP
MDR FACTOR,BASE MULTIPLY FACTOR REG BY BASE NO REG
JUMP LTR EXPN,EXPN CHECK IF EXPONENT PLUS,MINUS,OR ZERO
BC 8,NEXT IF EXPONENT NOW ZERO, BRANCH TO NEXT
MDR BASE,BASE MULTIPLY BASE NO BY DOUBLING ITSELF
BC 15,LOOP BRANCH TO LOOP TO TEST NEXT EXPN BIT

I post this as proof that the algorithm has actually been used in production
software. With any function call overhead, I would expect it to be slower
in the recursive version. Though for bignum versions, the difference may be
small, as the multiply will be somewhat slower. Also, I don't know which
bignum libraries can do a square in place (without copying it first).

-- glen

-- glen

[Tim Woodall]

On Tue, 28 Oct 2003 12:41:13 -0500 (EST),
Arthur J. O'Dwyer <aj*@nospam.andrew.cmu.edu> wrote:

What's wrong with n==15? The algorithm given is still O(lg N)
in such cases. No, probably Knuth was thinking of *better*
algorithms that could compute powers more quickly -- I don't
know of any, but perhaps a couple of exp() and log() lookup
tables, plus iteration, could do things faster than straight
recursion.

x^3 can be done with two multiplications and x^5 can be done with 3
using the square and multiply algorithm

x2 =x * x x2 = x * x
y =x * x2 z = x * x2
x4 = x2 * x2
y2 = y * y z = z * x4
y4 = y2 * y2 x8 = x4 * x4
z = y * y4 z = z * x8

So x^15 can be done with 5 multiplications by calling the square and
multiply algorithm twice. But the square and multiply algorithm
requires 6 multiplications for x^15. A general algorithm would
require the ability to factor n which is not known to be easy ;-)

(Factoring n isn't guaranteed to give a better solution than square
and multiply, 33 being the smallest counter example. Knuth has about
20 pages on finding a general optimal solution)

Tim.

--
God said, "div D = rho, div B = 0, curl E = - @B/@t, curl H = J + @D/@t,"
and there was light.

http://tjw.hn.org/ http://www.locofungus.btinternet.co.uk/