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