Re: calculating an exponent?

From: Thad Smith (thadsmith_at_acm.org)
Date: 09/28/04 

Date: Tue, 28 Sep 2004 09:46:09 -0600

Jani Yusef wrote:
>
> Alf P. Steinbach wrote:
> > * Jani Yusef:
> >
> >>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. Would it be broken down first into
> 2*(2*2)*(2*2) ors omething like that? How is that different then, say,
> and even exponent? Sorry for all the questions but I really don't
> understand this at all.

Integer exponentiation can be done with a series of squaring and multiplication by the base. 2^5 = ((2^2)^2)*2. The
sequence of squaring and multiplication by the base is determined by the bits of the exponent expressed in binary.

Multiplication can be implemented with a sequence of shifts and conditional additions.

Thad

Relevant Pages

  • Re: controversial paper
    ... You could have n servers, each of which serves up only ... > every nth address in sequence. ... The 'efficiency' could be higher ... > same time there will be portions of it that do not have enough addresses ...
    (sci.crypt)
  • Re: Operations on derived type arrays
    ... myType to force consecutive locations "if needed" but I don't know what "if ... the only thing that SEQUENCE does in the ... The efficiency issues get complicated. ... actual argument to a dummy argument that is not assumed shape. ...
    (comp.lang.fortran)
  • Re: calculating an exponent?
    ... > Alf P. Steinbach wrote: ... For efficiency it might be a good idea to first consider efficient ... as before with 'n', reducing the exponent further, and so on. ...
    (comp.programming)