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

[Achim Gädke <Achim dot Gaedke at physik dot tu-darmstadt dot de>]

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
> >
> >    
>
>
>