Re: Recursive Functions

From: Arthur J. O'Dwyer (ajo_at_nospam.andrew.cmu.edu)
Date: 10/29/03 

Date: Wed, 29 Oct 2003 10:16:28 -0500 (EST)

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