[PATCH] Optimize x*x*x*x*x*x using 3 multiplications.

[Geoff Keating]

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
the previous answer.

-- 
- Geoffrey Keating <geoffk@geoffk.org>