Re: erroneous claim at sources.redhat.com/gsl/ref/gsl-ref_4.html# SEC32

[jimmy mcguire <jxmcguire1 at ualr dot edu>]

Breaking my usual rule against speaking proir to knowing for sure, how 
about use the powers of two approach if the destination exponent is a 
power of two or if it is prime, otherwise the break the destination 
exponent into prime addends and construct multiplicative factors 
corresponding to the prime additive exponents. Repeat (recurse) as 
necessary.

Achim Gädke wrote:

> so, is there anyone outside, knowing similar problems?
>
> I agree, repeated squaring is likely to be the best solution, because 
> the binary representation can be obtained easily on a computer.
> So the manual should state, that this algorithm is efficient and in 
> most cases the fastest.
>
> Achim
>
> keith.briggs@bt.com wrote:
>
> > Thanks for the reply!   No, I do not have an algorithm.
> > I think you would have to program special cases up to some maximum n; 
> > after
> > that repeated squaring is the only simple way even if it is not optimal.
> > Keith
> >
> >     Dr. Keith M. Briggs
> >     Senior Mathematician, Complexity Research, BT Exact
> >     http://research.btexact.com/teralab/keithbriggs.html
> >     phone: +44(0)1473  work: 641 911 home: 610 517  fax: 642 161
> >        mail: Keith Briggs, Polaris 134, Adastral Park, Martlesham, 
> > Suffolk
> > IP5 3RE, UK
> >
> >
> > -----Original Message-----
> > From: Achim Gädke [mailto:achim@element.fkp.physik.tu-darmstadt.de]
> > Sent: 15 July 2003 10:19
> > To: Briggs,KM,Keith,XVR2 R
> > Cc: gsl-discuss@sources.redhat.com
> > Subject: Re: erroneous claim at
> > sources.redhat.com/gsl/ref/gsl-ref_4.html#SEC3 2
> >
> >
> > Hi!
> >
> > I could not believe that, but it's true and a nice logic training:
> >
> > x2=x*x;
> > x3=x2*x;
> > x5=x3*x2;
> > x15=x5*x5*x5;
> > with 5 * symbols
> >
> > instead of:
> >
> > x2=x*x;
> > x4=x2*x2;
> > x8=x4*x4;
> > x15=x8*x4*x2*x;
> > here: 6 * symbols.
> >
> > Keith, do you have a simple approach to the more efficient algorithm, 
> > that seems to base on a factorization ( 15=5*3 ).
> >
> > Achim
> >
> > On Tue, 15 Jul 2003 keith.briggs@bt.com wrote:
> >
> >  
> >
> > > > Function: double gsl_pow_int (double x, int n)     
> > >
> > >     >This routine computes the power x^n for integer n. The power is
> > > computed using the minimum number of multiplications. A glance at 
> > > the source code shows that this is wrong.   It uses repeated
> > > squaring, so, for example, x^15 is computed
> > > with 6 multiplies, whereas it can be done with 5.
> > > Keith
> > >
> > >   
> >
> >
> >
> >