Underflow and floating-point math

[tings]

An article states: "In floating point maths, where if you divide by a
sufficiently large number sufficiently often, you will always be able to
reach a value too small to distinguish from zero, given the finite precision
you have."

What happens when "a value too small to distinguish from zero" is reached by
the above division? Underflow?

What does it mean "sufficiently often" since only one division should be
enough to cause underflow in division between two floating point numbers?

When underflow happens, the result of the above division should be regarded
as "undefined behavior"? In other words, the result could be any floating
number or just a meanless "number." Is this correct?

THANKS IN ADVANCE!

[Michael Mair]

tings wrote:

An article states: "In floating point maths, where if you divide by a
sufficiently large number sufficiently often, you will always be able to
reach a value too small to distinguish from zero, given the finite precision
you have."

What happens when "a value too small to distinguish from zero" is reached by
the above division? Underflow?
You arrive at zero because the value cannot be distinguished from
zero. IOW:
\forall floating point numbers f
\exists floating point number g, natural number n:
"f/(g^n)" == "zero"
where "expr" means evaluation of the expression in floating point
arithmetics.
We have 0 < h=f/g^n < min{floating point number e| e>0}
but h is sufficiently small to be rounded to zero.

Could you please define what you mean _exactly_ by underflow?

What does it mean "sufficiently often" since only one division should be
enough to cause underflow in division between two floating point numbers?
Example:
#include <math.h>
#include <float.h>
#include <stdio.h>

int main (void)
{
double f = 2.0*DBL_MIN;
double g = 1.0/DBL_EPSILON;
unsigned int n = 3;

printf("%*.*g\n", DBL_DIG+1, DBL_DIG, f/pow(g, n));

return 0;
}
should work on most machines.

When underflow happens, the result of the above division should be regarded
as "undefined behavior"? In other words, the result could be any floating
number or just a meanless "number." Is this correct?

No.
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[James Hess]

tings wrote:

An article states: "In floating point maths, where if you divide by a
sufficiently large number sufficiently often, you will always be able to
reach a value too small to distinguish from zero, given the finite precision
you have."
You can't be sure that dividing by just a large number will do
that though. There will be lots of single numbers you could divide by
to get underflow, and after all...
(a/b)/c = a/(b*c)

It would take more work to find the number of least magnitude
that you could pick... in any case, it's just a way of stating it.
It's the same if you divide numbers that aren't so large,
enough times it will eventually happen that you get underflow.

If all you are doing is divisions by numbers whose magnitude is
big, then it's going to be the end result if you performed
just enough of these divisions [by themselves].
What does it mean "sufficiently often" since only one division should be
enough to cause underflow in division between two floating point numbers?
I believe an underlying assumption is that you are performing
other operations and keeping a cumulative result, you are not
just dividing but performing a computation that involves systematic
application of something else, perhaps many operations (additions,
multiplications, or subtractions) as well as divisions.

So "often" is characterizing at what rate you are dividing your
current result by a large number which diminishes its magnitude
compared to operations that will amplify its magnitude in getting
your next result.

Being sufficiently often means that your divisions are not so
scattered or interleaved with other operations that increase
in magnitude that you stay away from zero.

i.e. if you had

double value = 500;

for(i = 0; i < 10000; i++) {
value = value * 100 - 1;
value = value / 100;
}

You will certainly be performing many divisions, but 'value'
will probably never be so close as to be rounded to 0.
Only about 1/3 of your operations are divisions, and 1/3 of your
operations increase value in number.

So the divisions were probably not often enough.

Now if you did

for(i = 0; i < 10000; i++) {
value = value * 100 + 1;
for(k = 0; k < 10; k++) { value = value / 100; }
}

You might find that to be dividing sufficiently often.
When underflow happens, the result of the above division should be regarded
as "undefined behavior"? In other words, the result could be any floating
number or just a meanless "number." Is this correct?

It depends on the nature of what you are doing. In some case it
could be suggesting a possibility that you lost precision or
something blew up, but...

I wouldn't generalize that, IMO.. you need to evaluate whether the
result fits your expectations and is the right thing to get or if
the underflow is making a mess and you need to get a higher precision
or perform the computations differently.

I don't know of any hard and fast rule.
-Mysid

[jacob navia]

tings wrote:
[snip]

When underflow happens, the result of the above division should be regarded
as "undefined behavior"? In other words, the result could be any floating
number or just a meanless "number." Is this correct?

No. The standard says (page 213, 7.12.1)

5 The result underflows if the magnitude of the mathematical result is
so small that the mathematical result cannot be represented, without
extraordinary roundoff error, in an object of the specified type.195)
If the result underflows, the function returns an implementation-defined
value whose magnitude is no greater than the smallest normalized
positive number in the specified type; if the integer expression
math_errhandling & MATH_ERRNO is nonzero, whether errno acquires the
value ERANGE is implementation-defined; if the integer expression
math_errhandling & MATH_ERREXCEPT is nonzero, whether the ‘‘underflow’’
floating-point exception is raised is implementation-defined.

Taking the lcc-win32 compiler as an example we have:
1) underflow is masked and will be approximated as zero. Since zero
is less than the smallest representable number it is within the
standard specs.

2) lcc-win32 does NOT set any errno flag if underflow occurs

3) If the user unmasks the underflow flag with the standard
function fesetexceptionflag before the underflow occurs, the machine
will trap at each underflow.

I hope this makes this clear.

jacob

[SM Ryan]

"tings" <ti******@hotmail.com> wrote:
# An article states: "In floating point maths, where if you divide by a
# sufficiently large number sufficiently often, you will always be able to
# reach a value too small to distinguish from zero, given the finite precision
# you have."

Most representations limit the space for the exponent. So you might be able
to fit 2^-20 in the exponent, or 2^-100, or 2^-1000, but eventually you reach
an exponent like 2^-100000000000 which requires more bits in the exponent
than the representation is likely to provide. The representation might
replace that with 0 or special value to signal what happenned.

# What happens when "a value too small to distinguish from zero" is reached by
# the above division? Underflow?

Depends on the implementation. Many CPUs nowadays use what's called IEEE reals.
That an additional interface on top of C (or Fortran or Pascal or ...) that
gives you more control over rounding and notification. You're going to have
check you math library documentation for more information.

# What does it mean "sufficiently often" since only one division should be
# enough to cause underflow in division between two floating point numbers?
#
# When underflow happens, the result of the above division should be regarded
# as "undefined behavior"? In other words, the result could be any floating
# number or just a meanless "number." Is this correct?

This is the business of Numerical Analyis, a strange black art that ponders
why (a+b)+c might not equal a+(b+c). Fools rush in where angels fear tread.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
OOOOOOOOOO! NAVY SEALS!

[CBFalconer]

jacob navia wrote:

.... snip ...
3) If the user unmasks the underflow flag with the standard
function fesetexceptionflag before the underflow occurs, the
machine will trap at each underflow.

There is no such standard function. If you had said 'The lcc-win
peculiar function' it would have been acceptable. As it is, it is
a gross misstatement of fact.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

[Richard Bos]

CBFalconer <cb********@yahoo.com> wrote:

jacob navia wrote:

3) If the user unmasks the underflow flag with the standard
function fesetexceptionflag before the underflow occurs, the
machine will trap at each underflow.
There is no such standard function.

Actually, there is, only it's spelled "fesetexceptflag".
If you had said 'The lcc-win peculiar function' it would have
been acceptable.
No, then it would have been off-topic. That is jacob navia's usual modus
operandi, and IYAM, _not_ to be encouraged.
As it is, it is a gross misstatement of fact.

I suspect a mere typo - in this, unusual, case.

Richard

[jacob navia]

CBFalconer wrote:

jacob navia wrote:

... snip ...

3) If the user unmasks the underflow flag with the standard
function fesetexceptionflag before the underflow occurs, the
machine will trap at each underflow.

There is no such standard function. If you had said 'The lcc-win
peculiar function' it would have been acceptable. As it is, it is
a gross misstatement of fact.

I stand corrected. It is fesetexceptflag and not as I mistyped...

Of course even when I make an obvious typing error Chuck will not
forgive me such a sin... He never makes such errors.

[jacob navia]

Richard Bos wrote:

CBFalconer <cb********@yahoo.com> wrote:

jacob navia wrote:

3) If the user unmasks the underflow flag with the standard
function fesetexceptionflag before the underflow occurs, the
machine will trap at each underflow.

There is no such standard function.

Actually, there is, only it's spelled "fesetexceptflag".

If you had said 'The lcc-win peculiar function' it would have
been acceptable.

No, then it would have been off-topic. That is jacob navia's usual modus
operandi, and IYAM, _not_ to be encouraged.

As it is, it is a gross misstatement of fact.

I suspect a mere typo - in this, unusual, case.

Richard

Well, it was a typo. I excuse me for committing such a grave sin.

I will pay for this in programmer's hell in its 8th circle:
the one reserved for heretics and non-conformant implementors.

jacob

[CBFalconer]

Richard Bos wrote:

CBFalconer <cb********@yahoo.com> wrote:

jacob navia wrote:

3) If the user unmasks the underflow flag with the standard
function fesetexceptionflag before the underflow occurs, the
machine will trap at each underflow.

There is no such standard function.

Actually, there is, only it's spelled "fesetexceptflag".

I just learned something, and you can guess how often I use those
facilities. At any rate my apologies to Jacob.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

[Keith Thompson]

jacob navia <ja***@jacob.remcomp.fr> writes:

CBFalconer wrote:

jacob navia wrote:
... snip ...

3) If the user unmasks the underflow flag with the standard
function fesetexceptionflag before the underflow occurs, the
machine will trap at each underflow.

There is no such standard function. If you had said 'The lcc-win
peculiar function' it would have been acceptable. As it is, it is
a gross misstatement of fact.

I stand corrected. It is fesetexceptflag and not as I mistyped...

Of course even when I make an obvious typing error Chuck will not
forgive me such a sin... He never makes such errors.

I'm guessing you wrote that before you saw his apology. I suggest
dropping it.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Keith Thompson]

jacob navia <ja***@jacob.remcomp.fr> writes:

tings wrote:
[snip]

When underflow happens, the result of the above division should be regarded
as "undefined behavior"? In other words, the result could be any floating
number or just a meanless "number." Is this correct?

No. The standard says (page 213, 7.12.1)

>> 5 The result underflows if the magnitude of the mathematical result is
so small that the mathematical result cannot be represented, without
extraordinary roundoff error, in an object of the specified type.195)
If the result underflows, the function returns an implementation-defined
value whose magnitude is no greater than the smallest normalized
positive number in the specified type; if the integer expression
math_errhandling & MATH_ERRNO is nonzero, whether errno acquires the
value ERANGE is implementation-defined; if the integer expression
math_errhandling & MATH_ERREXCEPT is nonzero, whether the "underflow"
floating-point exception is raised is implementation-defined. >>

That section describes the behavior of the functions in <math.h>, not
necessarily of floating-point division.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Keith Thompson]

"tings" <ti******@hotmail.com> writes:

An article states: "In floating point maths, where if you divide by a
sufficiently large number sufficiently often, you will always be able to
reach a value too small to distinguish from zero, given the finite precision
you have."

What happens when "a value too small to distinguish from zero" is reached by
the above division? Underflow?

What does it mean "sufficiently often" since only one division should be
enough to cause underflow in division between two floating point numbers?

When underflow happens, the result of the above division should be regarded
as "undefined behavior"? In other words, the result could be any floating
number or just a meanless "number." Is this correct?

The quotation from the article is a rather vague statement of a more
general principle.

Floating-point overflow occurs when the mathematical result of an
operation is too large in magnitude to be represented (for example, if
a double result would be greater than DBL_MAX or less than -DBL_MAX).

Floating-point underflow occurs when the mathematical result is
non-zero, but too small to be represented. In C, I don't believe this
is considered an error; the result can be either 0.0 or some tiny
value. A flag of some sort might or might not be set.

Starting with some arbitrary value and repeatedly dividing it by some
sufficiently large value is one way to cause an underflow. For example:

#include <stdio.h>
int main(void)
{
double x = 1.0;
double previous;
int count = 0;

while (1) {
x /= 10.0;
count ++;
if (x == previous) {
printf("x = %g after %d iterations\n", x, count);
return 0;
}
else if (count >= 1000) {
printf("x = %g, bailing out after %d iterations\n", x, count);
return 0;
}
previous = x;
}
return 0;
}

On one system I just tried, this produces the output:

x = 0 after 325 iterations

You can, of course, get the same effect by repeatedly multiplying by a
small number, or by dividing or multiplying just once by a very large
or small number, respectively. Underflow is determined by the
mathematical result of the operation. The sentence you quoted should
be considered merely an example of what can cause it.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Richard Bos]

jacob navia <ja***@jacob.remcomp.fr> wrote:

Richard Bos wrote:

CBFalconer <cb********@yahoo.com> wrote:

If you had said 'The lcc-win peculiar function' it would have
been acceptable.

No, then it would have been off-topic. That is jacob navia's usual modus
operandi, and IYAM, _not_ to be encouraged.

As it is, it is a gross misstatement of fact.

I suspect a mere typo - in this, unusual, case.

Well, it was a typo. I excuse me for committing such a grave sin.

I will pay for this in programmer's hell in its 8th circle:
the one reserved for heretics and non-conformant implementors.

No, you won't.

Not for this typo, that is.

Richard