This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.

Index Nav: Message Nav: [Date Index] [Subject Index] [Author Index] [Thread Index] [Date Prev] [Date Next] [Thread Prev] [Thread Next] [Raw text]

# Re: [PATCH] Optimize x*x*x*x*x*x using 3 multiplications.

• From: Geoff Keating <geoffk at geoffk dot org>
• To: dewar at gnat dot com (Robert Dewar)
• Cc: gcc at gcc dot gnu dot org
• Date: 01 Aug 2003 12:33:00 -0700
• Subject: Re: [PATCH] Optimize x*x*x*x*x*x using 3 multiplications.
• References: <20030801041740.88506F2E2E@nile.gnat.com>

```dewar@gnat.com (Robert Dewar) writes:

> > Optimize x*x*x*x*x*x using 3 multiplications.
>
> It is interesting to note that in general this kind of optimization decreases
> accuracy (it is more accurate to do the full 5 multiplications). Nevertheless
> it is probably reasonable. In Ada 83, this optimization is in fact not
> permitted, since it is not guaranteed to have sufficient accuracy. Ada 95
> deliberately relaxed this accuracy rule to allow this kind of optimization.

We can model a floating-point multiplication '*' of two values, x and y,
as computing

x y (1 + e) < x * y < x y (1 - e)

where 'e' is 1/2 ulp, that is 2^-24 for single-precision IIRC.

So, if we're computing x*x*x*x from left-to-right, we get:

x x (1 + e) < x * x < x x (1 - e)
x x (1 + e) x (1 + e) < (x * x) * x < x x (1 - e) x (1 - e)
x x (1 + e) x (1 + e) x (1 + e)
< ((x * x) * x) * x
< x x (1 - e) x (1 - e) x (1 - e)

If we compute it as (x * x) * (x * x), we get

x x (1 + e) x x (1 + e) (1 + e)
< (x * x) * (x * x)
< x x (1 - e) x x (1 - e) (1 - e)

which, since real arithmetic is associative, is exactly the same as