Re: Draft "Unsafe fp optimizations" project description.

[Carlo Wood <carlo at alinoe dot com>]

On Sun, Aug 05, 2001 at 04:01:30PM +0200, Toon Moene wrote:
> However, if we just look at B*C then this product will overflow or
> underflow when the the sum of the exponents of B and C is higher than +N
> or lower than -N.  If we take B and C randomly from the FP-values-sack,
> that will be true for half of the exponent values.  Because there are
> the same number of fp values for every exponent value, it follows that
> the conclusion extends to "half of the fp values".

I think that Toon thinks:

<MATH>
When B = b * 2^B_exp (and C = c * 2^C_exp) and

1 <= b < 2 (and 1 <= c < 2), where these are
more or less evenly distributed over that range,
then 1 <= b * c < 4.  For random numbers, the
chance that b is smaller than x is (x - 1).
The fraction of (b * c) that is smaller than 2 is
therefore

Integral b = 1 to 2 of
  Integral c = 1 to 2 of
    (2/c - 1) dc db

where (dc * db) is the chance that b and c lay it
their respective intervals b..b+db and c..c+dc
and (2/c - 1) is the chance that b < 2/c and
thus b * c < 2.

This is equal to

Integral c = 1 to 2 of
  (2/c - 1) dc =

                2
[2 * ln(c) - c]   = 2 * ln(2) - 1 = 0.3863
                1

With the exponents evenly distributed between
MIN <= exp <= MAX (where MIN is more or less -MAX),
0.25 of the time B_exp + C_exp > MAX,
0.25 of the time B_exp + C_exp < MIN and
1/(2 * MAX) of the time B_exp + C_exp == MAX.
So, an overflow/underflow occurs in

0.25 + 0.25 + (1 - 0.3863)/(2 * MAX) = 0.5 (more or less)

of the cases.
</MATH>

But I agree with Robert:

It is not reasonable to assume that the exponents are evenly
distributed.  If you ask me, it IS reasonable to assume that
only in the order of 1/MAX (or even less!) of the practical
cases B_exp + C_exp are > MAX *because* there is a ceiling
for B*C (hmm, a rather fuzzy reason).

Hence the chance is more of the order of 1/MAX instead of 0.5.

-- 
Carlo Wood <carlo@alinoe.com>