Re: calculating an exponent?

From: Alf P. Steinbach (alfps_at_start.no)
Date: 09/28/04 

Date: Tue, 28 Sep 2004 15:42:00 GMT

* Jani Yusef:
> Alf P. Steinbach wrote:
> > * Jani Yusef:
> >
> >>Ok, this one has me stumped.
> >>Is it possible to calculate an exponent, say, a^n, using only right
> >>and left shifts along with additions and subtractions?
> >
> >
> > All arithmetic operations are implemented that way (in software or hardware).
> >
> > Presumably 'a' and 'n' are non-negative integers.
> >
> > The only question is then how (in)efficient you want the algorithm to
> > be. For efficiency it might be a good idea to first consider efficient
> > multiplication. With multiplication you can then tackle the efficiency of the
> > exponentiation, e.g. by noting treating odd n and even n differently.
>
> Hmmm, thats interesting but I am still confused as to how this is done?
> Suppose I want to calculate 2^5 , for example. What would the
> calculation look like.

In the C language family:

    power = 1 << 5;

a simple left shift 5 bits.

> Would it be broken down first into 2*(2*2)*(2*2) ors omething like that?

For an arbitrary 'a' that is one option yes; how much this technique
really helps is discussed by Knuth in (I think) volume 1 of the TAOCP.

> How is that different then, say, and even exponent?

For an even exponent n = 2*m you have a^n = a^(2*m) = (a^2)^m, which
reduces the size of the exponent involved by a factor of 2. If 'm' is
even this can be applied again. If 'm' is odd you then have m = 1+2*k,
and can apply b=a^2, b^m = b^(1+2*k) = b*(b^2)^k, which is the same
as before with 'n', reducing the exponent further, and so on.

> Sorry for all the questions but I really don't understand this at all.

Then consider a simple loop that goes 'n' times and multiplies by 'a'
in each iteration -- it's not the most efficient but works. 

-- 
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

Relevant Pages

  • Re: calculating an exponent?
    ... Jani Yusef: ... > Is it possible to calculate an exponent, say, a^n, using only right ... > and left shifts along with additions and subtractions? ... For efficiency it might be a good idea to first consider efficient ...
    (comp.programming)
  • Re: calculating an exponent?
    ... > Alf P. Steinbach wrote: ... For efficiency it might be a good idea to first consider efficient ... Multiplication can be implemented with a sequence of shifts and conditional additions. ...
    (comp.programming)
  • Re: calculating an exponent?
    ... Alf P. Steinbach wrote: ... >>Is it possible to calculate an exponent, say, a^n, using only right ... >>and left shifts along with additions and subtractions? ... For efficiency it might be a good idea to first consider efficient ...
    (comp.programming)