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

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

[Robert Dewar]

> 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.

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

[Paolo Carlini]

Robert Dewar wrote:

>>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).
>
Indeed, very interesting! If you have got two more spare minutes, I 
would be curious to know a sketch of the explanation of this.

Thanks in advance,
Paolo.

Re: [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>

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

[Paolo Carlini]

Geoff Keating wrote:

>which, since real arithmetic is associative, is exactly the same as
>the previous answer.
>
Eh!
I wonder (thanks Craig for your private message), what happens if we 
work in probabilistic setting, that is, computing means and statistics 
wrt the (joint) distributions not just bounding... perhaps this is the 
logic behind the Ada83 and Ada95 choices??

Paolo.

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

[Laurent GUERBY]

On Fri, 2003-08-01 at 21:33, Geoff Keating wrote:
> 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.

You've just showed that a simple error analysis gives the same
error bounds, Robert is likely to reference more advanced (understand
really ugly :) analysis, where all the "e" terms are not blindly set to
the same value for all the domain and their relative value carefully
checked. 

If you compute 14^4 using perfectly rounded 2 digit base 10
multiplication, you get the following:

repeated squaring gives 40e3 (14*14=196=>20e1, 20e1*20e1=40e3
sequential multiplication gives 39e3 (20e1*14=28e2, 28e2*14=392e2=>39e3)

The correctly rounded result is 38416=>38e3, so sequential
multiplication is more accurate here.

This small computation proves nothing general of course but you see the
first multiplication error gets amplified more by squaring seemingly
accordingly to Robert next email proposed intuitive reason :). 

Laurent

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

[Robert Dewar]

> Indeed, very interesting! If you have got two more spare minutes, I 
> would be curious to know a sketch of the explanation of this.

Consider the simpler case

  a = x*x*x*x;

  a = (x**2)**2;

the second form has only two multiplications instead of three.

So casual intuition (your deadly enemy when it comes to floating-point)
expects less loss of accuracy with only two operations.

But a careful error analysis shows that the error bounds for the second
case can be larger than those for the first case (obviously this depends
on the value of x in general).

An intuitive understanding (which is only slightly misleading :-) is that
in the first case, for each of the three multiplications, at least one of
the operands is error-free, but in the second case, the second multiplication
is between two quantities, both of which have rounding "errors".

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

[Richard Kenner]

    I hear you.  And I said, that it wasn't meant for review.

I didn't mean "review" as in "review a patch for approval", but "review" as
in "review this to see what you think about it".  Both need comments.

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

[Michael Matz]

Hi,

On Thu, 31 Jul 2003, Richard Kenner wrote:

>     Like I said it's an experiment still, not thought for inclusion.
>
> Sure, but comments should be the *first* thing written, so that they guide
> the code.

Like with every rule stated in this absolute way, I disagree with it.
Though I understand what you are getting at.

> If you are posting something for review, the comments will say more
> about it than the code itself and will be much quicker to read.

I hear you.  And I said, that it wasn't meant for review.


Ciao,
Michael.

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

[Richard Kenner]

    Like I said it's an experiment still, not thought for inclusion.

Sure, but comments should be the *first* thing written, so that they guide
the code.  If you are posting something for review, the comments will
say more about it than the code itself and will be much quicker to read.

It's important to get in the habit of writing comments *first* because
otherwise they either tend not to be written at all or are done as an
afterthought and aren't very good.  What you most want to encode in the
comments are your thoughts and motivations at the time you are writing
the code.  Going back and trying to recollect those thoughts and motivations
can be error-prone.