🚀 go-pugleaf

In article <3f7a622d.113216013@news.eircom.net>,
wallacethinmintr@eircom.net (Russell Wallace) writes:
|> 
|> >The reason I say the last is that there is no need to calculate a
|> >multiplication to full accuracy - all you need is to generate
|> >enough bits for a decision.  Of course, this means that operations
|> >can take variable times, which is Not Approved Of.  But it might
|> >help, especially for extended precision multiplication.
|> 
|> I'm no expert on numerical analysis, so tell me if I'm missing
|> something obvious, but:
|> 
|> Let's suppose you have N bits of precision (N ~= 53 for IEEE double
|> precision IIRC).
|> 
|> In the base case where rounding truncates; you have N bits of
|> precision.

OK.

|> If rounding is to nearest, .5 rounding away from zero (the simplest
|> type of rounding, it requires the consideration of only one extra
|> bit), you effectively have something like N+0.5 bits of precision in
|> calculations.

Well, maybe.

|> With more complicated rounding, such as to even (IIRC, IEEE supports
|> modes like this, at considerable complexity penalty), or
|> probabilistic, you effectively have something like N+0.5+epsilon bits.

Not really, but explaining why takes a while.  It isn't important,
anyway.

|> Now my question is: why is it worth so much trouble to get an extra
|> epsilon of a bit, when by using e.g. Intel's 80 bit format for
|> temporaries, you get something like an extra 16 bits?

Because of the order of error build up.  Consider the simple summation
of a vector of length L:

Truncation is almost always biassed, so that the relative error will
be of order L*eps/2.  Most roundings are not much biassed for well
mixed inputs and so the error will be of order sqrt(L)*eps/4.  A
major gain.

In the case where the initial value of the sum is A and you are
adding small numbers very near B, where the variation in B is less
than A*eps/L, ANY true rounding will have error of order L*eps/4
(though with a much smaller factor than for truncation).  True
probabilistic rounding, however, maintains an order sqrt(L)*eps/2.8.

Now, if you use extra precision for the sum, this ceases to be a
problem, but that applies only when you know WHERE in your program
the accuracy loss will occur and you use the extended precision
appropriately.  If you use extra precision, then you are merely
reducing eps - sometimes this will eliminate the problem, sometimes
it won't.

This is why hardware designers go to great trouble (and it IS great
trouble) to support rounding.  IBM originally omitted from the
System/360 because doing so can save a complete cycle on floating
point operations.  Note that the problem with rounding is twofold:

    1) You have to maintain at least one extra bit (two for IEEE)
to know how to round.

    2) You may have to renormalise or reraise an exception after
the rounding (and this is where the extra cycle goes, in general).

What I and a few other people have said over many years (and I am
a mere follower) is that the extra cost of PERMITTING a true
probabilistic rounding mode is negligible, and there are certain
calculations for which it is vastly better.  Apparently it is
starting to be adopted in graphics.


Regards,
Nick Maclaren.