From: "Billinghurst, David (CRTS)" <David.Billinghurst@riotinto.com>
To: <gsl-discuss@sources.redhat.com>
Subject: RE: erroneous claim at sources.redhat.com/gsl/ref/gsl-ref_4.html#SEC3 2
Date: Tue, 15 Jul 2003 13:05:00 -0000 [thread overview]
Message-ID: <FAC87D7C874EAB46A847604DA4FD5A640348C0@crtsmail.corp.riotinto.org> (raw)
> 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". */
+
next reply other threads:[~2003-07-15 13:05 UTC|newest]
Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top
2003-07-15 13:05 Billinghurst, David (CRTS) [this message]
-- strict thread matches above, loose matches on Subject: below --
2003-07-15 12:48 erroneous claim at sources.redhat.com/gsl/ref/gsl-ref_4.html# SEC3 2 keith.briggs
[not found] <0AAF93247C75E3408638B965DEE11A700101020B@i2km41-ukdy.nat.bt.com>
2003-07-15 9:57 ` Achim Gädke
2003-07-15 13:06 ` jimmy mcguire
2003-07-15 12:22 ` Achim Gädke
2003-07-15 8:52 erroneous claim at sources.redhat.com/gsl/ref/gsl-ref_4.html#SEC3 2 keith.briggs
2003-07-15 11:36 ` Achim Gädke
2003-07-16 15:49 ` Brian Gough
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=FAC87D7C874EAB46A847604DA4FD5A640348C0@crtsmail.corp.riotinto.org \
--to=david.billinghurst@riotinto.com \
--cc=gsl-discuss@sources.redhat.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).