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

["Billinghurst, David (CRTS)" <David dot Billinghurst at riotinto dot com>]

> From: Achim Gädke [mailto:achim@element.fkp.physik.tu-darmstadt.de]
> Sent: Tuesday, 15 July 2003 7:19 PM
> To: keith.briggs@bt.com
> Cc: gsl-discuss@sources.redhat.com
>Subject: Re: erroneous claim at sources.redhat.com/gsl/ref/gsl-ref_4.html#SEC3 2
>
> Keith, do you have a simple approach to the more efficient algorithm, that 
> seems to base on a factorization ( 15=5*3 ).
>
> Achim

Code for this was put into gcc recently
(http://gcc.gnu.org/ml/gcc-patches/2003-06/msg02472.html)

Comments in the code given below.  Check the follow-up posts (or grab the current
code from CVS).  I recall there was a bug somewhere.

+ /* To evaluate powi(x,n), the floating point value x raised to the
+    constant integer exponent n, we use a hybrid algorithm that
+    combines the "window method" with look-up tables.  For an
+    introduction to exponentiation algorithms and "addition chains",
+    see section 4.6.3, "Evaluation of Powers" of Donald E. Knuth,
+    "Seminumerical Algorithms", Vol. 2, "The Art of Computer Programming",
+    3rd Edition, 1998, and Daniel M. Gordon, "A Survey of Fast Exponentiation
+    Methods", Journal of Algorithms, Vol. 27, pp. 129-146, 1998.  */
+
+ /* Provide a default value for POWI_MAX_MULTS, the maximum number of
+    multiplications to inline before calling the system library's pow
+    function.  powi(x,n) requires at worst 2*bits(n)-2 multiplications,
+    so this default never requires calling pow, powf or powl.  */
+
+ #ifndef POWI_MAX_MULTS
+ #define POWI_MAX_MULTS  (2*HOST_BITS_PER_WIDE_INT-2)
+ #endif
+
+ /* The size of the "optimal power tree" lookup table.  All
+    exponents less than this value are simply looked up in the
+    powi_table below.  This threshold is also used to size the
+    cache of pseudo registers that hold intermediate results.  */
+ #define POWI_TABLE_SIZE 256
+
+ /* The size, in bits of the window, used in the "window method"
+    exponentiation algorithm.  This is equivalent to a radix of
+    (1<<POWI_WINDOW_SIZE) in the corresponding "m-ary method".  */
+ #define POWI_WINDOW_SIZE 3
+
+ /* The following table is an efficient representation of an
+    "optimal power tree".  For each value, i, the corresponding
+    value, j, in the table states than an optimal evaluation
+    sequence for calculating pow(x,i) can be found by evaluating
+    pow(x,j)*pow(x,i-j).  An optimal power tree for the first
+    100 integers is given in Knuth's "Seminumerical algorithms".  */
+