Re: [OT] Re: Recursive Functions

From: Glen Herrmannsfeldt (gah_at_ugcs.caltech.edu)
Date: 10/29/03 

Date: Wed, 29 Oct 2003 15:25:23 GMT

"Marcus Lessard" <spam08@spam.com> wrote in message
news:bnocqm$145$1@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

Relevant Pages

  • Re: Another way to do x^n
    ... \ raise float to positive integer power ... DUP 0= IF DROP FDROP 1e0 EXIT THEN ... FDUP F0= IF DROP FDROP 0e0 EXIT THEN ... Recursion unnecessarily obfuscates the algorithm. ...
    (comp.lang.forth)
  • Re: Another way to do x^n
    ... \ raise float to positive integer power ... FDUP F0= IF DROP FDROP 0e0 EXIT THEN ... Recursion unnecessarily obfuscates the algorithm. ...
    (comp.lang.forth)
  • Re: to Matt,
    ... algorithm that can run BWT in linear time (with respect to the input ... Quantum computers are thing of past, ... I can use Jules' random compression ... drill a power cord from WB's super nuclear power plant to Sachin's ...
    (comp.compression)
  • Re: Powers of 5
    ... This should give you the modified algorithm almost immediately. ... Courses with greater emphasis on programming have entered ... require the argument to be a power of 2. ...
    (sci.math)
  • Re: to Matt,
    ... algorithm that can run BWT in linear time (with respect to the input ... Quantum computers are thing of past, ... I can use Jules' random compression ... drill a power cord from WB's super nuclear power plant to Sachin's ...
    (comp.compression)