Comparing floating point values for equality
Matthias Hofmann
I need to compare floating point values for equality, but I remember that
this can be a tricky thing in C++. I recall that there are cases when such a
comparison should be done as follows:
bool equal( float f1, float f2 )
{
return std::fabs( f1 - f2 ) < 0.1;
}
I am not sure which constant to use (0.1 seems a bit too much) and whether
this method is necessary at all. Maybe I can simply compare the floating
point values like this:
float f1, f2;
bool equal = (f1 == f2);
Can anyone clarify this for me?
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Greg Herlihy
Matthias Hofmann wrote:
> Hello!
>
> I need to compare floating point values for equality, but I remember that
> this can be a tricky thing in C++. I recall that there are cases when such a
> comparison should be done as follows:
>
> bool equal( float f1, float f2 )
> {
> return std::fabs( f1 - f2 ) < 0.1;
> }
>
> I am not sure which constant to use (0.1 seems a bit too much) and whether
> this method is necessary at all. Maybe I can simply compare the floating
> point values like this:
>
> float f1, f2;
> bool equal = (f1 == f2);
>
> Can anyone clarify this for me?
Well, I tried your idea. Here's my program:
#include <iostream>
int main()
{
float f1 = 0.1f;
f1 *= 9;
float f2 = 0.9f;
if (f1 == f2)
std::cout << f1 << " equals " << f2;
else
std::cout << f1 << " does not equal " << f2;
std::cout << std::endl;
}
and here's its output:
0.9 does not equal 0.9
Greg
Niek Sanders
> comparison should be done as follows:
>
> bool equal( float f1, float f2 )
> {
> return std::fabs( f1 - f2 ) < 0.1;
>
> }
>
The appropriate constant wiggle factor (sometimes called epsilon)
varies depending on your algorithms. If you make the value too large
and you massively reduce the numerical resolution (e=0.1 means that
1.00 == 1.09). Make it too small and you will get false mismatches.
For my code (a raytracer), I tend to use 1E-6 as the wiggle when
dealing with 32-bit floats. A typical item of comparison would be a
polygon vertex coordinate versus a point generated by a ray
intersection algorithm. Look at the sources of numerical noise: the
view ray must be computed, the view ray goes through several affine
transforms (platform -> instrument mount -> global to local) followed
by whatever numerical precision is lost throw the projection from the
intersect algorithm.
So in short, the correct value for the wiggle depends on the accuracy
of the algorithms your floats pass through. If an analytic solution
would indicate the two values equal, then the wiggle should be large
enough for the numeric solution to do the same.
> Maybe I can simply compare the floating point values like this:
>
> float f1, f2;
> bool equal = (f1 == f2);
>
This is almost certainly not what you want. For instance, the
following code returns mismatch on my G4 mac using gcc:
double lhs = 4.44;
double rhs = 4440000.0 * 1E-6;
std::cout << (lhs==rhs? "match" : "mismatch") << std::endl;
Cheers,
Niek Sanders
http://www.cis.rit.edu/~njs8030/
kanze
> I need to compare floating point values for equality, but I
> remember that this can be a tricky thing in C++.
There's nothing tricky about it, neither in C++ nor in any other
language. What's tricky is knowing when comparison for equality
is appropriate -- in C++ and in every other programming
language. Machine floating point values are NOT real numbers,
and do not obey the rules of real number arithmetic.
> I recall that there are cases when such a comparison should be
> done as follows:
> bool equal( float f1, float f2 )
> {
> return std::fabs( f1 - f2 ) < 0.1;
> }
That's rarely an appropriate solution -- according to your
routine, 0.09 is equal to 0.0, and I cannot imagine a context
where that would be acceptable.
There are cases where "close enough" can be treated as equal,
but the definition of close enough will depend very much on what
you are trying to do. Note, however, that when using "close
enough", a equals b and b equals c does not mean that a equals
c; close enough is not an equivalence relationship.
> I am not sure which constant to use (0.1 seems a bit too much)
> and whether this method is necessary at all. Maybe I can
> simply compare the floating point values like this:
> float f1, f2;
> bool equal = (f1 == f2);
> Can anyone clarify this for me?
Not in the scope of a newsgroup article. Try searching for
"What All Computer Programmers Should Know about Floating Point
Arithmetic" -- there are numerous copies on the net, and it
should be required reading before using float or double.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
kwikius
Matthias Hofmann wrote:
> Hello!
>
> I need to compare floating point values for equality, but I remember that
> this can be a tricky thing in C++. I recall that there are cases when such a
> comparison should be done as follows:
>
> bool equal( float f1, float f2 )
> {
> return std::fabs( f1 - f2 ) < 0.1;
> }
>
> I am not sure which constant to use (0.1 seems a bit too much) and whether
> this method is necessary at all. Maybe I can simply compare the floating
> point values like this:
>
> float f1, f2;
> bool equal = (f1 == f2);
>
> Can anyone clarify this for me?
use a compare function which passes in a (+/-) tolerance range in which
the two values can be said to be equal. Note also judicious use of abs.
(From experience I have found that the tolerance argument can be
negative). The function can also be used instead of comparison
operators of course
regards
Andy Little
/*
if( a ~=~ b ) return 0;
if( a > b ) return 1;
if( a < b ) return -1;
*/
#include <cmath>
template <typename Float>
int compare(Float const & a, Float const & b, Float const & tolerance)
{
Float difference = a-b;
if ( std::abs(difference) < std::abs(tolerance) ){
return 0;
}
else{
if (difference > 0){
return 1;
}
else {
return -1;
}
}
}
#include <iostream>
int main()
{
std::cout.precision(9);
double a = 1;
double b = 1.0000001;
double tolerance1 = 1e-6;
double tolerance2 = 1e-8f;
std::cout << "in range tolerance1? "
<< std::boolalpha << (compare(a,b,tolerance1) == 0 ) << '\n';
std::cout << "in range tolerance2? "
<< std::boolalpha << (compare(a,b,tolerance2) == 0 ) << '\n';
Michiel...@tomtom.com
> Hello!
>
> I need to compare floating point values for equality, but I remember that
> this can be a tricky thing in C++.
Not just C++, any language has the same problems. It's a property of
floating poitn numbers.
> I recall that there are cases when such a comparison should be done as follows:
>
> bool equal( float f1, float f2 )
> {
> return std::fabs( f1 - f2 ) < 0.1;
> }
>
> I am not sure which constant to use (0.1 seems a bit too much) and whether
> this method is necessary at all.
Definitely, else equal(1.0, 1.0/3.0*3.0) could be false.
> Maybe I can simply compare the floating
> point values like this:
>
> float f1, f2;
> bool equal = (f1 == f2);
That will likely fail with the numbers suggested.
The advantage of <0.1 is that it "works" around 0. It won't work for
very big
numbers. Are 0.01 and 0.02 equal? Are 1.00 million and 1.00001 million
equal?
There are no quick answers here. One alternative is to check if
abs((f1/f2)-1) < 0.01.
That does work independent of scale, but fails close to 0.
HTH,
Michiel Salters
Dietmar Kuehl
> I need to compare floating point values for equality,
In general, you will almost certainly not get the desired results.
> but I remember that this can be a tricky thing in C++.
This is not a tricky thing in C++: this is a tricky thing in all
programming languages!
> I recall that there are cases when such
> a comparison should be done as follows:
>
> bool equal( float f1, float f2 )
> {
> return std::fabs( f1 - f2 ) < 0.1;
> }
Yes, this is about it. The exact details on the chosen epsilon
depend on your application but effectively, the above approach
is the only viable one.
> I am not sure which constant to use (0.1 seems a bit too much) and whether
> this method is necessary at all. Maybe I can simply compare the floating
> point values like this:
>
> float f1, f2;
> bool equal = (f1 == f2);
No, this does not really work out except in very few cases: if
the values of 'f1' and 'f2' are effectively just copies of the
same original value and never changed their type, this should
be safe. However, as soon as some computations are involved,
you are most likely ending up with different values. The issue
about comparison between floating point values is that the
numeric operations are not closed over the set of possible
values. That is, 'x @ y' (where '@' is any suitable operation)
may yield a value which cannot be represented as a floating
point value. That is, when determining the result of an
expression involving floating point types, some rounding occurs.
The exact details of rounding are also not that straight forward
as the computation may actually be performed using a different
representation for the floating point types. For example, the
processor normally computes with a higher precision than 'float'
and only the result of multiple operations may be rounded to the
actual representation.
The net effect is that floating point values normally differ at
least in a few bits. Even if these are that insignificant that
printing the values shows identical values (with "normal"
precision in printing), the comparison will yield 'false'. To
effectively compare floating point values for equality, you need
to determine a suitable maximum difference and check whether the
distance between your two values does not exceed this difference.
The maximum difference is effectively the accumulated imprecision
over the entire computation. What this value is, depends on the
actual application. Also, I seem to remember that sometimes a
relative difference is used.
--
<mailto:dietma...@yahoo.com> <http://www.dietmar-kuehl.de/>
<http://www.eai-systems.com> - Efficient Artificial Intelligence
Matthias Hofmann
mention that in my algorithm, I am actually dealing with percentages, so the
floating point values will range between 0 and 1. Here's a piece of code
that demonstrates how they are retrieved:
double a, b, c;
double x, y, z;
...
double d1 = a / ( a + b + c );
double d2 = x / ( x + y + z );
if ( equal( d1, d2 ) )
{
// Handle equality.
}
As you can see, I am planning to use 'double' instead of 'float' because the
former has a larger mantissa, and the latter might not be able to handle the
ranges needed for a, b, c and x, y, z. Given that, what epsilon should I
choose in order to get "good" equality results? I am working with Microsoft
Visual C++ on 32 bit Windows, in case that information helps.
kwikius
> Matthias Hofmann wrote:
> > Hello!
> >
> > I need to compare floating point values for equality, but I remember that
> > this can be a tricky thing in C++. I recall that there are cases when such a
> > comparison should be done as follows:
> >
> > bool equal( float f1, float f2 )
> > {
> > return std::fabs( f1 - f2 ) < 0.1;
> > }
> >
> > I am not sure which constant to use (0.1 seems a bit too much) and whether
> > this method is necessary at all. Maybe I can simply compare the floating
> > point values like this:
> >
> > float f1, f2;
> > bool equal = (f1 == f2);
> >
> > Can anyone clarify this for me?
>
> use a compare function which passes in a (+/-) tolerance range in which
> the two values can be said to be equal. Note also judicious use of abs.
> (From experience I have found that the tolerance argument can be
> negative). The function can also be used instead of comparison
> operators of course
Just to make the function slightly more robust:
#include <cmath>
template <typename Float>
int compare(Float const & a,
Float const & b,
Float const & tolerance)
{
Float difference = a-b;
if ( (difference == Float(0) )
|| (std::abs(difference) <= std::abs(tolerance)) ){
return 0;
}
else{
if (difference > 0){
return 1;
}
else {
return -1;
}
}
}
regards
Andy Little
Pete Becker
>
> For my code (a raytracer), I tend to use 1E-6 as the wiggle when
> dealing with 32-bit floats.
Replacing == with this form of "approximately equal" removes the obvious
(but valid) incongruities of ==, but it replaces them with its own set
of quirks.
First, using a fixed value means that your code doesn't scale. If you
change your measurement units from inches to feet the actual numbers
become smaller, but the tolerance stays the same, so points that were
different are now considered equal. In any particular application that
may be appropriate, but as a general solution, the size of the allowable
difference has to depend on the size of the values being compared.
Second, this approach has the rather frightening property that it isn't
transitive. There are lots of values for which equal(a,b) is true, and
equal(b,c) is true, but equal(a,c) is false. This can lead to mysterious
results, including crashes when an algorithm requires transitivity.
--
Pete Becker
Roundhouse Consulting, Ltd.
Pete Becker
>
> and here's its output:
>
> 0.9 does not equal 0.9
>
Your point being, of course, that roundoff during conversion for output
loses precision, so the two (different) values are displayed incorrectly.
The same thing occurs with integer math, except that we're used to it:
int i = 1;
int j = i / 3;
int k = j * 3;
Now, k isn't equal to i, but nobody says "don't use == to compare
integer values."
Floating-point math has the same kind of limitations: representations of
values have a limited precision, so you can lose information when longer
results get cut short to fit in the data type. So you either tolerate
the roundoff error or you code around it. It's not as straightforward
with floating-point types as it is with integral types, but the
principal is the same.
--
Pete Becker
Roundhouse Consulting, Ltd.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Daniel T.
"Matthias Hofmann" <hof...@anvil-soft.com> wrote:
> Hello!
>
> I need to compare floating point values for equality, but I remember that
> this can be a tricky thing in C++. I recall that there are cases when such a
> comparison should be done as follows:
>
> bool equal( float f1, float f2 )
> {
> return std::fabs( f1 - f2 ) < 0.1;
> }
>
> I am not sure which constant to use (0.1 seems a bit too much) and whether
> this method is necessary at all. Maybe I can simply compare the floating
> point values like this:
>
> float f1, f2;
> bool equal = (f1 == f2);
>
> Can anyone clarify this for me?
This is an FAQ, including the formula...
<http://www.parashift.com/c++-faq-lite/newbie.html#faq-29.17>
--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.
Pete Becker
>
>>bool equal( float f1, float f2 )
>>{
>> return std::fabs( f1 - f2 ) < 0.1;
>>}
>
>
> That's rarely an appropriate solution -- according to your
> routine, 0.09 is equal to 0.0, and I cannot imagine a context
> where that would be acceptable.
>
Ignoring the other problems that arise from this kind of "approximately
equal" predicate, the tolerance needs to be determined by the magnitude
of the numbers involved in the problem.
For astronomers measuring distances in miles the difference between 0.09
and 0.00 (not 0.0, which only has two digits precision, while 0.00 has
three) is lost in the measurement noise. That is, if the values being
compared are accurate to the nearest million miles or so <g>,
differences of .09 just don't matter. 1,000,000,000.09 and
1,000,000,000.00 are the same value, and anyone who insisted they are
different would get a long lecture about false precision. (I wrote about
this physicist's perspective on floating point errors in a CUJ column
several years ago, available at www.petebecker.com/js200007.html).
--
Pete Becker
Roundhouse Consulting, Ltd.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Francis Glassborow
Matthias Hofmann <hof...@anvil-soft.com> writes
>Many thanks to all of you for this useful information! I think I should
>mention that in my algorithm, I am actually dealing with percentages, so the
>floating point values will range between 0 and 1. Here's a piece of code
>that demonstrates how they are retrieved:
>
>double a, b, c;
>double x, y, z;
>...
>double d1 = a / ( a + b + c );
>double d2 = x / ( x + y + z );
>
>if ( equal( d1, d2 ) )
>{
> // Handle equality.
>>
>
>As you can see, I am planning to use 'double' instead of 'float' because the
>former has a larger mantissa, and the latter might not be able to handle the
>ranges needed for a, b, c and x, y, z. Given that, what epsilon should I
>choose in order to get "good" equality results? I am working with Microsoft
>Visual C++ on 32 bit Windows, in case that information helps.
Choosing to use fabs(d1 -d2)< epsilon requires knowledge of the expected
size of d1. Consider:
fabs(1 - d1/d2) < epsilon;
Now choose epsilon to meet your needs. Only you know how close to
equality is close enough.
Note that you should always use double unless you have very precise
reasons for needing to use float. I get tired of books for novices that
insist on using float because that rarely saves anything of consequence.
--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects
Simon Bone
> Many thanks to all of you for this useful information! I think I should
> mention that in my algorithm, I am actually dealing with percentages, so the
> floating point values will range between 0 and 1. Here's a piece of code
> that demonstrates how they are retrieved:
>
That is not really the useful information you thought. OK, we now know you
will not be using positive exponents in your fp variables, but that isn't
really too important.
Do you want 2 or 10 decimal digits of significant precision?
e.g. is 0.02 the same as 0.01999999999999999 for your purposes?
They are both around 2% in common parlance, but that isn't necessarily
what you want.
> double a, b, c;
> double x, y, z;
> ...
> double d1 = a / ( a + b + c );
> double d2 = x / ( x + y + z );
>
> if ( equal( d1, d2 ) )
> {
> // Handle equality.
> }
> }
> As you can see, I am planning to use 'double' instead of 'float' because
> the former has a larger mantissa, and the latter might not be able to
> handle the ranges needed for a, b, c and x, y, z. Given that, what
> epsilon should I choose in order to get "good" equality results? I am
> working with Microsoft Visual C++ on 32 bit Windows, in case that
> information helps.
>
Usually we would say the larger mantissa of double gives increased
precision, the larger exponent gives increased range. (Increased range
probably isn't important here, but remember the extra range into *small*
values, i.e. negative exponents, might matter too.)
The precision offered by float is typically equivalent to around 5 decimal
places, which is close to the number of digits many people can compare.
e.g. I spot the difference between 12.345% and 12.346% quite easily.
The precision offered by double is more like 10 decimal places. I have
trouble when asked to manually compare such numbers:
e.g. 12.345678910% vs 12.346578910% say.
A typical use for double is to provide "extra space" to absorb rounding
errors during manipulation of your input values. The results might be
deliberately narrowed to fit a float before output. This can be combined
with control of rounding modes to spot the places where the rounding
errors in the internal manipulation have become visible to those who are
receiving the results. (see below).
Given you are working out percentages, you might intend to present
these to the user. Possibly you want to mark out "close enough"
percentages for extra attention, or equivalently to mark out those not
close enough.
In such cases, you had best work out the rounding you intend to apply for
display, and use that to identify those that match within that
representation. If consistency between the way you manipulate within your
program and results as presented to the user matters, you will need to
ensure whatever comparison function you use is consistent. This could even
suggest textual comparison is appropriate! It really depends upon your
needs.
For other uses, a statistical comparison might be more appropriate. In
which case, your percentages would have a variance or standard deviation
associated with their value. There are many well known tests for this-
consult any statistics or scientific maths text to find something
appropriate.
Generally when implementing such comparisons you would use floating point
values. The pattern of use is usually:
double bar(double b);
float foo (float a,float b) {
// widen the input data to double:
double my_a = a, my_b = b;
// do work, for example:
double res = my_a;
res = bar(my_b);
// narrow respecting the current rounding mode, as set by the caller:
return res;
}
The implementation of bar would be similar but would widen the input data
to long double, and do it's work in that form before narrowing to
double to return results. (This is why implementations that set long
double to the same size as double are brain-dead).
Note that in debugging you might change the rounding mode surrounding the
work portion to identify the places where it makes a difference. But do
respect the rounding mode set by the caller. You would do this by saving
the initial state (i.e. before doing any work) and ensuring it is reset
before the return statement, and also ensure it is reset before
exceptional returns (i.e. use RAII).
Whatever you do, you will need to be aware that it is not a general
purpose solution. Such a function doesn't exist (if it did, it would be a
very attractive candidate for standardization). Others have pointed out
that the range of your values can affect the best choice of epsilon, and
that many comparison functions will not be transitive. These factors
really relate to the meaning you attach to the numbers input to your
comparison function, and also the uses you intend for the results. It is
due to the wide variety of possible meanings of the values and the
possible uses that you can't get a generic answer here.
HTH
Simon Bone
Greg Herlihy
> Greg Herlihy wrote:
>
> >
> > and here's its output:
> >
> > 0.9 does not equal 0.9
> >
>
> Your point being, of course, that roundoff during conversion for output
> loses precision, so the two (different) values are displayed incorrectly.
No, the point is that floating point values, unlike integer
representations, do not always represent exact values exactly. 1
multiplied by 9 equals 9 exactly for integer values, but 0.1 times 9 is
not certain to equal 0.9 exactly when the values are represented by
floating point types. So if the original poster believes that 0.1 times
9 should equal 0.9 exactly, then the suggested test for equality
between the floating point result and the expected floating point
value, will not in fact be able to fulfill that expectation.
> The same thing occurs with integer math, except that we're used to it:
>
> int i = 1;
> int j = i / 3;
> int k = j * 3;
>
> Now, k isn't equal to i, but nobody says "don't use == to compare
> integer values."
Integer multiplication is not the inverse of integer division, so there
should be no expectation that k would be equal to i after performing
those two operations. Instead we know that k will equal 0 exactly and,
more importantly, comparing k with 0 will confirm that equality since k
is an integer value.
> Floating-point math has the same kind of limitations: representations of
> values have a limited precision, so you can lose information when longer
> results get cut short to fit in the data type. So you either tolerate
> the roundoff error or you code around it. It's not as straightforward
> with floating-point types as it is with integral types, but the
> principal is the same.
There is a sharp difference between fixed and floating point
representations. The difference is not merely one of scale. The
difference is that one is exact, and the other is not. 1 divided by 3
using integer division produces an exact result: 0. The 0 valued result
is not an approximation of the actual value, instead both the expected
result from the operation and its represented value are 0. This quality
of exactness - in which the represented value is always an exact value
- is not guaranteed with floating point operations, even when the
values are exactly specified and the expected value of the operation is
exact, as my program demonstrated. For those used to the exactness of
integer arithmatic, the inexactness of floating point values is often
surprising.
Greg
Greg Herlihy
> Many thanks to all of you for this useful information! I think I should
> mention that in my algorithm, I am actually dealing with percentages, so the
> floating point values will range between 0 and 1. Here's a piece of code
> that demonstrates how they are retrieved:
>
> double a, b, c;
> double x, y, z;
> ...
> double d1 = a / ( a + b + c );
> double d2 = x / ( x + y + z );
>
> if ( equal( d1, d2 ) )
> {
> // Handle equality.
> }
>
> As you can see, I am planning to use 'double' instead of 'float' because the
> former has a larger mantissa, and the latter might not be able to handle the
> ranges needed for a, b, c and x, y, z. Given that, what epsilon should I
> choose in order to get "good" equality results? I am working with Microsoft
> Visual C++ on 32 bit Windows, in case that information helps.
If the program is calculating percentages of values that fall within a
predetermined range, then one alternative to floating point
calculations would be fixed point arithmetic. For reasons already
pointed out, floating point values are often overly precise and
insufficiently exact when employed for certain purposes.
With fixed point arithmetic, the program can specify how precise the
percentages expressed should be, and to what degree of precision those
percentages are to be measured. Any values that would differ by less
than the specified degree in a floating point calculation will compare
as exactly equal in a fixed point operation. Furthermore all values
representable are exactly represented: for instance 0.1 times 9 using
fixed point representation will equal 0.9 exactly.
Fixed point is easy to use in practice. For example, to express a
percentage with 0.1% precision (one tenth of one percent), requires
scaling both sides of the ratio by 1000. Next, to obtain a result
accurate to 0.01 or 1/100th requires that the numerator be scaled by
100. Now one downside of fixed point representation is that the range
of representable values is limited by the desired degree of precision.
In particular, fixed point operations must guard against overflow (and
as usual, divide by zero errors), precautions that I have omitted
below.
const long kPercentageScalingFactor = 1000L;
const long kPrecisionScalingFactor = 100L;
long scaledA = a * kPrecisionScalingFactor;
long fxp = (scaledA * kPercentageScalingFactor) /
((a+b+c)* kPercentageScalingFactor);
Now barring overflow or other error, fxp represents a fixed point
number with each "unit" in its scale corresponding to 0.01 of numeric
value. So all values calculated with these scaling factors will be
exact to a 0.01 precision.
Finally, to convert a fixed point value into a floating point
representation (say, for the purposes of displaying it), simply divide
by the precision scaling factor as a floating point value:
double d1 = fxp/(kPrecisionScalingFactor*1.0);
Greg
Matthias Hofmann
news:1140782142....@e56g2000cwe.googlegroups.com...
> if ( (difference == Float(0) )
> || (std::abs(difference) <= std::abs(tolerance)) ){
> return 0;
Why the comparison to Float(0)? If 'difference' is equal to Float(0), then
'std::abs(difference)' should also be smaller than or equal to
'std::abs(tolerance)', shouldn't it?
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Matthias Hofmann
news:postmaster-187F7...@news.east.earthlink.net...
> In article <43fe23b9$0$13607$9b4e...@newsread2.arcor-online.net>,
> This is an FAQ, including the formula...
>
> <http://www.parashift.com/c++-faq-lite/newbie.html#faq-29.17>
I like the formula from the FAQ, because it supports scaling without there
being the danger of a division by zero (because there is no division):
inline bool isEqual( double x, double y )
{
const double epsilon = /* some small number such as 1e-5 */;
return std::abs( x - y ) <= epsilon * std::abs( x );
}
Unfortunately, the FAQ leaves one question open. It says that: "finding the
average of two floating point numbers seems simple but to do it right
requires an if/else with at least three cases". However, it does not provide
the solution - so how is is it done right?
And one more thing: Most of you seem to be using std::abs() rather than
std::fabs(), so where is the difference between the two?
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Pete Becker
>
> No, the point is that floating point values, unlike integer
> representations, do not always represent exact values exactly.
For some unspecified meaning of "exact values". The only useful meaning
of that term is values that can be represented exactly in the floating
point representation being used. With a decimal floating-point
representation, 0.1 can be represented exactly. Integers have similar
(although simpler) problems:
unsinged int i = 65536
printf("%u\n", i);
The value displayed by the call to printf (as well as the value held in
i) depends on the precision of the integer type. On many systems it will
be 65536. On others it will be 0.
> 1
> multiplied by 9 equals 9 exactly for integer values,
And 32768+32768 may or many not equal 65536 exactly for integer values.
> but 0.1 times 9 is
> not certain to equal 0.9 exactly when the values are represented by
> floating point types.
The actual problem here is that the text "0.1" does not describe a value
that can be represented exactly in binary floating point. To get the
floating point value the compiler converts the decimal representation to
binary. But it can be represented exactly under a decimal floating-point
representation.
> So if the original poster believes that 0.1 times
> 9 should equal 0.9 exactly, then the suggested test for equality
> between the floating point result and the expected floating point
> value, will not in fact be able to fulfill that expectation.
Because of the conversion.
>
>
>>The same thing occurs with integer math, except that we're used to it:
>>
>>int i = 1;
>>int j = i / 3;
>>int k = j * 3;
>>
>>Now, k isn't equal to i, but nobody says "don't use == to compare
>>integer values."
>
>
> Integer multiplication is not the inverse of integer division, so there
> should be no expectation that k would be equal to i after performing
> those two operations.
Exactly.
> Instead we know
> that k will equal 0 exactly and,
> more importantly, comparing k with 0 will confirm that equality since k
> is an integer value.
We know because we've been taught that, not because it's obvious ab
initio. How many times have you seen beginners ask why they get 0 when
they do that sort of division?
>
>
>>Floating-point math has the same kind of limitations: representations of
>>values have a limited precision, so you can lose information when longer
>>results get cut short to fit in the data type. So you either tolerate
>>the roundoff error or you code around it. It's not as straightforward
>>with floating-point types as it is with integral types, but the
>>principal is the same.
>
>
> There is a sharp difference between fixed and floating point
> representations. The difference is not merely one of scale. The
> difference is that one is exact, and the other is not. 1 divided by 3
> using integer division produces an exact result: 0. The 0 valued result
> is not an approximation of the actual value,
Nonsense. It's not the right answer. We accept it because we know how
integer arithmetic works, not because it's correct in any mathematical
sense. The problem is that most programmers assume that floating-point
arithmetic works just like real arithmetic, and that's wrong in exactly
the same way that assuming that integer arithmetic works just like real
arithmetic is wrong.
instead both the expected
> result from the operation and its represented value are 0. This quality
> of exactness - in which the represented value is always an exact value
> - is not guaranteed with floating point operations, even when the
> values are exactly specified and the expected value of the operation is
> exact, as my program demonstrated.
Nonsense. If you know the floating point representation you can
determine exactly what the result of every floating-point computation
will be. People who write floating-point math for a living take great
pains to make sure they know exactly what their computation is doing.
People who write integer math for a living should do so, but they're
often sloppy about it, since they think it's simple and obvious.
> For those used to the exactness of
> integer arithmatic, the inexactness of floating point values is often
> surprising.
>
For those who aren't used to the truncating done by integer arithmetic,
the inexactness of integer values is often surprising. Don't forget, you
weren't created knowing how computers handle integer arithmetic.
Beginners have to learn it. Once they absorb it, they often forget what
it was like to not know it.
--
Pete Becker
Roundhouse Consulting, Ltd.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Jerry Coffin
online.net>, hof...@anvil-soft.com says...
> Many thanks to all of you for this useful information! I think I should
> mention that in my algorithm, I am actually dealing with percentages, so the
> floating point values will range between 0 and 1. Here's a piece of code
> that demonstrates how they are retrieved:
>
> double a, b, c;
> double x, y, z;
> ...
> double d1 = a / ( a + b + c );
> double d2 = x / ( x + y + z );
>
> if ( equal( d1, d2 ) )
> {
> // Handle equality.
> }
>
> As you can see, I am planning to use 'double' instead of 'float' because the
> former has a larger mantissa, and the latter might not be able to handle the
> ranges needed for a, b, c and x, y, z. Given that, what epsilon should I
> choose in order to get "good" equality results? I am working with Microsoft
> Visual C++ on 32 bit Windows, in case that information helps.
I'm a bit surprised that nobody's mentioned one point.
std::numeric_limits<X> (where X is a floating point type)
has a member named epsilon that's intended to tell you
what kind of precision you can expect from the floating
point on your particular machine. It's defined as the
minimum representable difference from 1.0.
To use this, you start by scaling it by one of the
numbers in your comparison, and it'll tell you the
minimum difference for numbers of that magnitude.
>From there, you need to deal with the amount of precision
you may have lost during your calculations -- for
example, if you've lost no more than one significant
digit due to roundoff, you'd multiply that by 10 (for two
digits, multiply by 100, etc.)
That gives us something like this:
template<class T>
bool equal(T const &a, T const &b, T const &factor) {
// should really be a compile-time assertion, but you
// get the idea.
assert(!std::numeric_limits<T>::is_integer);
T x = std::numeric_limits<T>::epsilon * factor *a;
T y = std::numeric_limits<T>::epsilon * factor *b;
T diff = abs(a-b);
return (diff < x) || (diff < y);
}
Note that this only makes it a bit easier to figure out
what the "looseness" factor should be for a give type and
range of numbers. This still isn't transitive, so Pete
Becker's points remain entirely valid.
OTOH, unlike many attempts, it is commutative -- that's
why we compute and use both x and y. I've taken the
relatively conservative approach, and assumed that if
there's any question, we've probably lost more rather
than less precision, so we can't meaningfully separate
the numbers unless we're pretty sure the difference
between them is large enough to be meaningful.
--
Later,
Jerry.
The universe is a figment of its own imagination.
Matthias Hofmann
news:HHUufuKDgz$DF...@robinton.demon.co.uk...
> Choosing to use fabs(d1 -d2)< epsilon requires knowledge of the expected
> size of d1.
Both d1 and d2 will be in the range between 0 and 1.
> Consider:
>
> fabs(1 - d1/d2) < epsilon;
Both d1 and d2 might be zero, causing my program to crash with that formula,
doesn't it?
> Now choose epsilon to meet your needs. Only you know how close to
> equality is close enough.
According to the information in Microsoft's MSDN-Library, type double has a
53 bit mantissa and at least 15 decimal digits precision. If I understand
correctly, this means that the smallest epsilon I can choose is 1E-14. This
should be more than enough, I think I'll opt for an epsilon of 1E-10.
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
kwikius
> "kwikius" <an...@servocomm.freeserve.co.uk> schrieb im Newsbeitrag
> news:1140782142....@e56g2000cwe.googlegroups.com...
> > if ( (difference == Float(0) )
> > || (std::abs(difference) <= std::abs(tolerance)) ){
> > return 0;
>
> Why the comparison to Float(0)? If 'difference' is equal to Float(0), then
> 'std::abs(difference)' should also be smaller than or equal to
> 'std::abs(tolerance)', shouldn't it?
Its just a bit faster in the case where the difference is 0, because ||
wont proceed with the other calculations. Though that assumes that the
two comparatees (if thats the correct word?) will be the same
frequently and if not will actually be slower I guess ;-)
Below is a version with an int template parameter that makes epsilon a
percentage of the average of the inputs (calls original function). I
just started using something similar though with compile time pow
function for tests.
Actually there seeems to be a variety of possible options for
comparison. Perhaps there shopuld be a standard comparisons library!
regards
Andy Little
/*
epsilon = 10 to_power Exp * average(a,b)
*/
template <int Exp,typename Float>
int
compare(Float const & a, Float const & b)
{
BOOST_STATIC_ASSERT(Exp<=0);//sanity check
Float average = (a + b)/ 2;
// its possible to make a faster version of this of course
Float epsilon =
std::pow(static_cast<Float>(10),static_cast<Float>(Exp)) * average;
// now call original
return compare(a,b,epsilon);
}
#include <iostream>
int main()
{
double a = 1;
double b = 1.0000001;
std::cout << std::boolalpha << (compare<-7>(a,b) == 0 ) << '\n';
std::cout << std::boolalpha << (compare<-8>(a,b) == 0 ) << '\n';
std::cout << std::boolalpha << (compare<-1>(100.,109.) == 0 )
<< '\n';
std::cout << std::boolalpha << (compare<-1>(100.,111.) == 0 )
<< '\n';
Hartwig Wiesmann
Also the example in the FAQ does not work/not make sense!
Assume x == 0 and y != 0: the example function below will always return
false. This does not make sense as y might be some sort of zero like
1.0e-100 (these type of number often arise due to rounding errors and I
think you would like to have these number evaluated to zero, too).
The most difficult part is what to do if one number is zero. In this
case you have to specify an absolute limit (and it is up to you to find
out what is best for you), for the other case your limit is a relative
one and should be slightly larger than the machine's relative accuracy:
return ((x*y) == 0) ? (std::fabs(x-y) <= Epsilon_absolute) :
(2*(std::fabs(x-y) <=
Epsilon_relative*(std::fabs(x)+std::fabs(y)));
Hartwig
Pete Becker
>
> With fixed point arithmetic, the program can specify how precise the
> percentages expressed should be, and to what degree of precision those
> percentages are to be measured. Any values that would differ by less
> than the specified degree in a floating point calculation will compare
> as exactly equal in a fixed point operation. Furthermore all values
> representable are exactly represented: for instance 0.1 times 9 using
> fixed point representation will equal 0.9 exactly.
>
That last one is true if you're using a DECIMAL fixed-point
representation. It's not true for a BINARY fixed-point representation.
The issue is converting that text sequence '0' '.' '9' into the internal
representation. With a decimal representation it fits in only a few
bits. With a binary representation it doesn't. And in this regard, the
same is true for floating-point representations. If you used a decimal
floating-point package it would also do what you want. The problem is
that when the radix of the text representation and radix of the internal
representation are different you can get values that can be represented
by a non-repeating value in one representation but not the other.
>
> [ implementation details omitted ]
>
> Now barring overflow or other error, fxp represents a fixed point
> number with each "unit" in its scale corresponding to 0.01 of numeric
> value. So all values calculated with these scaling factors will be
> exact to a 0.01 precision.
Yup: you've written a decimal fixed-point computation, which can
represent tenths without repeating fractional parts. But note that
"exact to a 0.01 precision" means "inexact for many values." It can't,
for example, represent 1/256 exactly, although a binary fixed-point
representation with 8 bits in the fraction can.
The advantage that you're pointing out of using fixed-point instead of
floating-point is that it's clearer where the roundoffs are occurring,
so it's easier to control. That's good, unless you need the wider range
that floating-point gives you.
--
Pete Becker
Roundhouse Consulting, Ltd.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Francis Glassborow
Matthias Hofmann <hof...@anvil-soft.com> writes
>And one more thing: Most of you seem to be using std::abs() rather than
>std::fabs(), so where is the difference between the two?
Because in C++ abs() is overlaoded for all the signed int and floating
point types.
--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects
Francis Glassborow
Matthias Hofmann <hof...@anvil-soft.com> writes
>"Francis Glassborow" <fra...@robinton.demon.co.uk> schrieb im Newsbeitrag
>news:HHUufuKDgz$DF...@robinton.demon.co.uk...
>
>> Choosing to use fabs(d1 -d2)< epsilon requires knowledge of the expected
>> size of d1.
>
>Both d1 and d2 will be in the range between 0 and 1.
>
>> Consider:
>>
>> fabs(1 - d1/d2) < epsilon;
>
>Both d1 and d2 might be zero, causing my program to crash with that formula,
>doesn't it?
sufficinetly different in magnitude.
>
>> Now choose epsilon to meet your needs. Only you know how close to
>> equality is close enough.
>
>According to the information in Microsoft's MSDN-Library, type double has a
>53 bit mantissa and at least 15 decimal digits precision. If I understand
>correctly, this means that the smallest epsilon I can choose is 1E-14. This
>should be more than enough, I think I'll opt for an epsilon of 1E-10.
If you are dealing with values in the range 0 to 1 any choice of epsilon
is vulnerable to being inadequate. If the range is, for example .1 to 1
it is much easier to choose a suitable level for approximate equality.
But then conversion to a scaled integer value is probably just as
effective.
--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects
Niek Sanders
> change your measurement units from inches to feet the actual numbers
> become smaller, but the tolerance stays the same, so points that were
> different are now considered equal. In any particular application that
> may be appropriate, but as a general solution, the size of the allowable
> difference has to depend on the size of the values being compared.
>
I did not claim a given wiggle factor as a solution for all problems.
In fact, I spent half of my original post indicating that an
appropriate factor is input and algorithm specific. For my raytracer,
it works fine when dealing with coordinates since I don't need to
spatially distinguish below millimeter resolution (scenes are ~10km in
size, with geometric accuracy in the 20cm range). There are quirks
from using such a system, but they can be managed.
> Second, this approach has the rather frightening property that it isn't
> transitive. There are lots of values for which equal(a,b) is true, and
> equal(b,c) is true, but equal(a,c) is false. This can lead to mysterious
> results, including crashes when an algorithm requires transitivity.
>
You second point is true. However, there is not much point in
transitivity if you don't have a usable method of measuring equality.
You could maintain transivity by limiting equality to having the same
bits--obviously useless for many real world tasks. Alternatively, you
could actually track significant figures. Numerical algebra has all
sorts of neat tricks for determining error (backwards error analysis),
but they come at a computational price. Considering the contents of
the original post (Matthias Hofmann) I don't think he's looking for
that kind of solution.
Cheers,
Niek Sanders
http://www.cis.rit.edu/~njs8030/
Matthias Hofmann
an expression rather than a value. The decimal value 0.1 actually means
1/10, and the value of such an expression is likely to be not representable
numerically, depending on whether the denominator of the fraction is a power
of 2 (for binary representation) or a power of 10 (for a decimal
representation).
When initializing a floating point value with 0.1, the implied fraction of
1/10 is evaluated and the result is stored, causing a loss of precision.
With integers, it's different because no precision is lost, as no expression
is evaluated (as a matter of course, the integer type might still not be
large enough to hold an assigned value).
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Matthias Hofmann
news:1140993321.7...@i39g2000cwa.googlegroups.com...
> > Second, this approach has the rather frightening property that it isn't
> > transitive. There are lots of values for which equal(a,b) is true, and
> > equal(b,c) is true, but equal(a,c) is false. This can lead to mysterious
> > results, including crashes when an algorithm requires transitivity.
> >
>
> You second point is true. However, there is not much point in
> transitivity if you don't have a usable method of measuring equality.
> You could maintain transivity by limiting equality to having the same
> bits--obviously useless for many real world tasks. Alternatively, you
> could actually track significant figures. Numerical algebra has all
> sorts of neat tricks for determining error (backwards error analysis),
> but they come at a computational price. Considering the contents of
> the original post (Matthias Hofmann) I don't think he's looking for
> that kind of solution.
Transitivity is in fact not a problem in my algorithm. But I nevertheless
appreciate your making me aware of this issue, as it might become important
another time.
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Matthias Hofmann
> If you are dealing with values in the range 0 to 1 any choice of epsilon
> is vulnerable to being inadequate. If the range is, for example .1 to 1
> it is much easier to choose a suitable level for approximate equality.
What is the reason for that? What's the difference between the range from 0
to .1 and the range from .1 to 1 that makes my choice of epsilon vulnerable?
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Matthias Hofmann
news:MPG.1e6a5ab11...@news.sunsite.dk...
I found another interesting solution on
http://ltilib.sourceforge.net/doc/html/ltiMath_8h-source.html, which is the
following:
template <class T> inline bool closeTo( const T& a, const T& b,
const T epsilon = std::numeric_limits<T>::epsilon() )
{
const T diff = a - b;
return ( diff <= epsilon ) && ( diff >= -epsilon );
}
As far as I understand it, it is also commutative and, what's even better,
it does not require the use of std::abs(), which is not available on Visual
C++ 6.0.
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Matthias Hofmann
"Hartwig Wiesmann" <hartwig....@wanadoo.nl> schrieb im Newsbeitrag
news:4401d163$0$2949$dbd4...@news.wanadoo.nl...
> Hi Matthias,
>
> Also the example in the FAQ does not work/not make sense!
> Assume x == 0 and y != 0: the example function below will always return
> false.
Thank you very much for pointing that out, I haven't noticed that flaw!
Besides your solution, one could also use an idea by Jerry Coffin from
another post of this thread:
inline bool isEqual( double x, double y )
{
const double epsilon = /* some small number such as 1e-5 */;
double diff = std::abs( x - y );
return diff <= epsilon * std::abs( x ) ||
diff <= epsilon * std::abs( y );
}
This would also make the function symmetric, which is not the case for the
original one from the FAQ.
kanze
> "Francis Glassborow" <fra...@robinton.demon.co.uk> schrieb im
> Newsbeitrag news:HHUufuKDgz$DF...@robinton.demon.co.uk...
> > Choosing to use fabs(d1 -d2)< epsilon requires knowledge of
> > the expected size of d1.
> Both d1 and d2 will be in the range between 0 and 1.
> > Consider:
> > fabs(1 - d1/d2) < epsilon;
> Both d1 and d2 might be zero, causing my program to crash with
> that formula, doesn't it?
Undefined behavior.
> > Now choose epsilon to meet your needs. Only you know how
> > close to equality is close enough.
> According to the information in Microsoft's MSDN-Library, type
> double has a 53 bit mantissa and at least 15 decimal digits
> precision. If I understand correctly, this means that the
> smallest epsilon I can choose is 1E-14. This should be more
> than enough, I think I'll opt for an epsilon of 1E-10.
Strange that no one has mentionned this before, but...
What do the requirements specifications say? And where do the
initial values come from?
If the initial values are the results of physical measurements,
then the problem exists, independantly of problems concerning
floating point representation. And if the precision of the
initial measurements is only, say, three decimal digits (a
frequent case in electronics, at any rate), then it doesn't make
much sense to try for an epsilon of 1E-10. The requirements
specification must define how close the percentages must be for
them to be considered equal; for all pratical purposes, given
the low number of operations you are doing, you can ignore any
added effects of machine floating point arithmetic with regards
to comparing for equality.
(On the other hand, of course, if the initial values can vary by
a significant order of magnitude, then the order you add them
can make a difference. Especially if the values can also be
negative. You still have to take the rules of floating point
arithmetic into consideration for that.)
If the initial values are integral values, say the number of
people in a sample group who prefer a, b or c, then testing for
exact equality would be an appropriate solution, even with
double, if all of the groups contain the same number of people.
If they don't havever, you have to keep in mind that if one
group has 29 people in it, and another 43, you'll never get
equality -- even if you define it with an epsilon of 1E-10.
Again, what you actually should do depends on what information
is really wanted.
Just using some arbitrary epsilon is never the correct solution.
The correct solution depends on the problem, and the problem
must first be specified exactly -- in most cases, testing for an
exact percentage doesn't give any useful information, even if
all of your calculations were done with infinite precision over
the set of reals. Once you know exactly what you're trying to
calculate, and only then, can you start to consider how to
calculate it, using the laws of machine floating point
arithmetic (and not the laws of real arithmetic).
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Martin Bonner
Matthias Hofmann wrote:
> "Francis Glassborow" <fra...@robinton.demon.co.uk> schrieb im Newsbeitrag
> news:XIXasWOx...@robinton.demon.co.uk...
>
> > If you are dealing with values in the range 0 to 1 any choice of epsilon
> > is vulnerable to being inadequate. If the range is, for example .1 to 1
> > it is much easier to choose a suitable level for approximate equality.
>
> What is the reason for that? What's the difference between the range from 0
> to .1 and the range from .1 to 1 that makes my choice of epsilon vulnerable?
The former range includes zero, the latter doesn't. That means that
the former range includes numbers which differ by infinite orders of
magnitudes.
If your percentages were, for example, ingredient/contaminent levels in
food then the differences between 33.7% fat and 33.8% fat (delta = 0.1)
is irrelevent. However the difference between 0.01% dioxin and
0.00001% dioxin (delta ~= 0.01) would be /highly/ significant.
Pete Becker
>
> When initializing a floating point value with 0.1, the implied fraction of
> 1/10 is evaluated and the result is stored, causing a loss of precision.
> With integers, it's different because no precision is lost, as no expression
> is evaluated (as a matter of course, the integer type might still not be
> large enough to hold an assigned value).
>
In other words, no precision is lost except when precision is lost. <g>
In both cases, the compiler translates a sequence of characters into a
value of a particular type, determined by the characters in that
sequence. 0 is an integer; 1.0 is a double. If code initializes an int
with 0.1 the stored value is 0, with a corresponding loss of precision.
If code initializes an int with 1000000000000000000000000000001 (pretend
that has more zeros than your int can handle) it stores a smaller value,
with considerable loss of accuracy. If code initializes a double with
that value (pretend it has more zeros than the precision of a double) it
throws away low bits, and the result is closer to the value of the
initializer than it is when stored in an int.
The fundamental problem is that programmers learn early on to deal with
the peculiarities of integer math, so these peculiarities become nearly
invisible. They are rarely taught to deal with the peculiarities of
floating-point math, so these peculiarities stand out.
--
Pete Becker
Roundhouse Consulting, Ltd.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Steven E. Harris
> The decimal value 0.1 actually means 1/10, and the value of such an
> expression is likely to be not representable numerically, depending
> on whether the denominator of the fraction is a power of 2 (for
> binary representation) or a power of 10 (for a decimal
> representation).
"Not representable numerically" sounds too strong here.
Common Lisp offers a ratio type, which is a subtype of rational.น
,----
| CL-USER> (/ 1 10)
| 1/10
| CL-USER> (type-of 1/10)
| RATIO
| CL-USER> (/ 1 10)
| 1/10
| CL-USER> (type-of 1/10)
| RATIO
| CL-USER> (numerator 1/10)
| 1
| CL-USER> (denominator 1/10)
| 10
| CL-USER> (type-of 0.1)
| SINGLE-FLOAT
| CL-USER> (decode-float 0.1)
| 0.8
| -3
| 1.0
| CL-USER> (= 1/10 0.1)
| NIL
`----
The final expression shows that, as expected, the floating point value
0.1 is not equal to the ratio 1/10.
Footnotes:
น http://www.lispworks.com/documentation/HyperSpec/Body/t_ratio.htm#ratio
--
Steven E. Harris
Jerry Coffin
online.net>, hof...@anvil-soft.com says...
[ ... ]
> I found another interesting solution on
> http://ltilib.sourceforge.net/doc/html/ltiMath_8h-source.html, which is the
> following:
>
> template <class T> inline bool closeTo( const T& a, const T& b,
> const T epsilon = std::numeric_limits<T>::epsilon() )
> {
> const T diff = a - b;
> return ( diff <= epsilon ) && ( diff >= -epsilon );
> }
>
> As far as I understand it, it is also commutative and, what's even better,
> it does not require the use of std::abs(), which is not available on Visual
> C++ 6.0.
It's commutative but almost completely wrong and shows a
fundamental misunderstanding of floating point in
general, and Epsilon in particular. As it stands, it only
gives meaningful results for numbers very close to 1.0.
Epsilon represents the smallest difference from 1.0 that
can be represented. A typical implementation of double
will have around 15 digits of precision, meaning that
Epsilon will be somewhere around 1e-15.
The basic idea of floating point, however, is that you
can take that 15 digits of precision and place it
anywhere in a much larger total range of numbers.
Assuming your compiler uses something like the IEEE
double precision floating point format, that range will
be approximately 308 -- i.e. you can have exponents
ranging from about -308 to +308, and you can have about
15 digits of precision anywhere in that range.
Now, let's consider the code above from that perspective.
If we have (say) 1e+100, then next larger number that can
be represented is about 1.000000000000001e+100. I.e. the
same magnitude, but with a '1' added around 15 places
after the decimal point. Now, if we subtract those two
numbers, we get a difference of about 1e85. The code
above would compare the 1e85 and find that it's
_somewhat_ larger than 1e-15, so it would say that the
numbers aren't equal -- even though the difference
between them is the smallest the floating point format
can possibly represent for this magnitude of numbers.
IOW, for this size of number, we're allowing NO room for
round-off at all -- in fact, it's exactly equivalent to
the simple-minded if (x==y) version of things, because no
difference in the range can possibly be smaller than
epsilon.
At the opposite end of the spectrum, consider a number
something like 1e-100. Here again, we have around 15
decimal digits of precision, so the next larger number we
can represent is approximately 1.000000000000001e-100. If
we compare 1e-100 to 2e-100, there's a BIG difference
between the two; saying the two are the same basically
says we've rounded off so much that we've lost
essentially ALL of our 15 digits or so of precision. If
we use the code above to compare them it says that the
difference is only 1e-100, which is a lot smaller than
1e-15, so it says they're equal. If we were to compare
1e-100 to 1e-104 (i.e. one is ten thousand times as big
as the other) this code still says they're equal. In
fact, this says all numbers below a certain threshold
(about 1e-16) are equal, regardless of their values. This
will say that 1e-17 and 1e-308 are equal, even though
they differ by literally hundreds of orders of magnitude!
About the only range in which this will provide
meaningful results is if your numbers happen to be in the
range around .1 down to .0001 or so -- depending somewhat
on how much precision you might have lost to round off.
If you want to get rid of std::abs from the code I posted
previously, you can write your own pretty easily:
// warning: untested code, but simple enough that it
// stands a reasonable chance of working anyway.
#ifdef VC6 // whatever it defines to identify itself
template <class T>
T abs(T val) { // we'll assume a cheap-to-copy type.
if (val < T(0))
return -val;
return val;
}
#endif
This has a fairly obvious problem if applied to twos-
complement integers, but for floating point types it's
normally fine.
--
Later,
Jerry.
The universe is a figment of its own imagination.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Steven E. Harris
> I found another interesting solution on
> http://ltilib.sourceforge.net/doc/html/ltiMath_8h-source.html,
> which is the following:
>
> template <class T> inline bool closeTo( const T& a, const T& b,
> const T epsilon = std::numeric_limits<T>::epsilon() )
Offering a default epsilon is misleading;
std::numeric_limits<T>::epsilon() needs to be scaled to be at all
meaningful.
My scaling function uses std::ldexp() and std::frexp() (though
scalbn() can also be appropriate). The scaled epsilon is only actually
used when the smaller of the two values being compared is known to be
zero. Otherwise, a ratio subtracted from 1 and compared to zero
implicitly uses std::numeric_limits<T>::epsilon().
Here's the CL version constrained to work with non-negative
values. Note the core function "samep", operating on values x and y,
normalized with y known to be greater than or equal to x. If y is
zero, so too is x. Otherwise, if x is zero, we scale epsilon down to 0
to compare with y. Otherwise, we compute x and y's ratio and check
whether its difference with 1 is detectable via comparison with
zero. That final detection implicitly uses
(single|double)-float-epsilonน, CL's equivalent to
std::numeric_limits<T>::epsilon().
(defun sufficiently-close (m n)
(macrolet ((check-negs (&rest places)
`(progn
,@(loop for place in places
collect `(check-type ,place (real 0 *)
'"a non-negative number")))))
(check-negs m n))
(flet ((samep (x y)
;; Assume y >= x.
(or (zerop y)
(if (zerop x)
(< y (scaled-epsilon 0.0))
(zerop (- 1 (/ x y)))))))
(if (< n m)
(samep n m)
(samep m n))))
Footnotes:
น http://www.lispworks.com/documentation/HyperSpec/Body/v_short_.htm
--
Steven E. Harris
Thant Tessman
> Greg Herlihy wrote:
[...]
>>There is a sharp difference between fixed and floating point
>>representations. The difference is not merely one of scale. The
>>difference is that one is exact, and the other is not. 1 divided by 3
>>using integer division produces an exact result: 0. The 0 valued result
>>is not an approximation of the actual value,
>
>
> Nonsense. It's not the right answer. We accept it because we know how
> integer arithmetic works, not because it's correct in any mathematical
> sense. [...]
Of course it's the right answer. 1 divided by 3 is 0 with a remainder of
1. Ask any third grader.
In this sense, integer arithmetic is indeed fundamentally different in
that as long as you don't overflow, the representation *exactly* matches
the notation--which is not what we are allowed to expect from
floating-point math. More than that, integer math is exact in the sense
that we can do as many integer operations as we want and we won't lose
precision (again as long as we don't overflow). The compromise we make
for the use of floating-point numbers goes far beyond the loss of
precision due to notational conversion.
-thant
--
"A free man must be able to endure it when his fellow men act and
live otherwise than he considers proper. He must free himself from
the habit, just as soon as something does not please him, of calling
for the police." -- Ludwig von Mises
Pete Becker
> If code initializes an int with 1000000000000000000000000000001 (pretend
> that has more zeros than your int can handle) it stores a smaller value,
> with considerable loss of accuracy. If code initializes a double with
> that value (pretend it has more zeros than the precision of a double) it
> throws away low bits, and the result is closer to the value of the
> initializer than it is when stored in an int.
Whoops, hastily written. Pretend that the value has enough zeros so that
it won't fit in an int but will fit in a long long, and that, in
addition, a long long has more bits than the fraction in a double. Phew.
Matthias Hofmann
> It's commutative but almost completely wrong and shows a
> fundamental misunderstanding of floating point in
> general, and Epsilon in particular. As it stands, it only
> gives meaningful results for numbers very close to 1.0.
[ further explanation omitted ]
Thank you very much for this thorough explanation! You have convinced me
that the function using a default epsilon is rather useless. I adopted your
idea and my current implementation of the comparison function looks like
this:
bool IsEqual( double x, double y )
{
const double epsilon =
std::numeric_limits<double>::epsilon();
// Note that std::abs() is not
// available on Visual C++ 6.0.
double diff = fabs( x - y );
return diff <= epsilon * fabs( x )
|| diff <= epsilon * fabs( y );
}
Note that I have taken a less conservative approach by comparing the
difference for being 'less or equal' rather than 'less'. I guess I am still
somewhat influenced by the function I found in the FAQ (
http://www.parashift.com/c++-faq-lite/newbie.html#faq-29.17 ), which
basically does the same thing but without being commutative. I hope that my
most recent approach is otherwise fine.
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Pete Becker
>
> Of course it's the right answer. 1 divided by 3 is 0 with a remainder of
> 1. Ask any third grader.
>
Unfortunately, most of us are no longer third graders. It takes an
effort for beginners to grasp that float f = 1/3; sets f to 0.
--
Pete Becker
Roundhouse Consulting, Ltd.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Matthias Hofmann
news:1141045963.5...@u72g2000cwu.googlegroups.com...
> Strange that no one has mentionned this before, but...
>
> What do the requirements specifications say? And where do the
> initial values come from?
Maybe this the time to explain what I am actually doing in my program...
The context of my intented floating point comparison is entirely different
from what most of you have guessed. I am in fact working on the artificial
intelligence of a computer game. In order to understand the algorithm, I
have to give you some basic information about the content of the game. It is
an economic simulation, and one of its features is the ability to produce
certain goods in a factory. In order to do so, you need to acquire
resources, and the algorithm is supposed to determine which type of resource
the computer should buy. It roughly proceeds as follows:
- It determines the amount currently on stock for each type of resource
(there are three types, let's call them a, b and c), which is stored in
variables a_stock, b_stock and c_stock.
- It determines the share (the percentage) of each resource on stock:
a_share_stock = ( a_stock == 0 ) ? 0 : a_stock / ( a_stock + b_stock +
c_stock );
// Same with b and c.
- It determines the amount required in production for each type of resource,
which is stored in variables a_needed, b_needed and c_needed.
- It determines the share (the percentage) of each resource needed:
a_share_needed = ( a_needed == 0 ) ? 0 : a_needed / ( a_needed + b_needed +
c_needed );
// Same with b and c.
- Now the artifical intelligence can determine the priority of each type of
resource. The priority is expressed by the difference between the shares on
stock and the shares needed:
a_priority = a_share_stock - a_share_needed;
b_priority = b_share_stock - b_share_needed;
c_priority = a_share_stock - c_share_needed;
A lower value means a higher priority, so the ordering might be, for
example:
c_priority = -0.2319...
a_priority = -0.1034...
b_priority = +11.48...
In that case, the artificial intelligence would acquire resources of type c.
The reason why I need to compare these flaoting point values for equality
is, that sometimes there might be more than on type of resource with the
same priority. If this is true, then the price decides: If two priorities
compare equal, the computer is supposed to buy the cheaper type of resource.
My current implementation of the corresponding sorting function looks
roughly like this:
struct
{
double priority;
int price;
} ResourceInfo;
// Returns true if a < b.
bool CompareResources( ResourceInfo a, ResourceInfo b )
{
return ( equal( a.priority, b.priority ) ) ?
( a.price < b.price ) : ( a.priority < b.priority );
}
Now the imlementation of equal() called by the function shown is just my
problem...
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Thant Tessman
> Thant Tessman wrote:
>
>>Of course it's the right answer. 1 divided by 3 is 0 with a remainder of
>>1. Ask any third grader.
>>
>
>
> Unfortunately, most of us are no longer third graders. It takes an
> effort for beginners to grasp that float f = 1/3; sets f to 0.
You can also consult any book on number theory if there's no third
grader handy. The point is that it *is* the right answer and that it
*is* exact in a sense unsupported by IEEE floating-point numbers.
The real problem with C++ (inherited from C of course) is that the rules
that decide whether integer or floating-point math is to be used are
somewhat ad hoc and based on subtle notational clues. When I was first
learning C, I once prepended a zero in front of an integer to get some
numbers to line up in the source. I was convinced the computer was
simply broken. When I found out what was really going on, it was the
first time I reacted to anything computer-related with: "That's really
stupid." I was a teenager at the time. It was a sort of rite-of-passage.
The point should also be made that one of C++'s strengths is the ability
to define your own number types that can be made to (almost) behave as
if they were a built-in number type. I built an arbitrary-precision
rational number implementation that I'm quite happy with. It's sort of
an existence proof that in C++ you don't have to abandon exactness until
you need to calculate a transcendental.[*] Until that point, equality is
well-defined. After that point, it really isn't. I know of at least one
language that doesn't even define equality for floating-point numbers
exactly because it's so ill-defined.
-thant
[*] Of course there are decisions to be made about whether or not
preserving exactness are worth the performance and space requirements
imposed.
--
"Few men desire liberty; most men wish only for a just master."
-- Sallust, 86-34 B.C.
wa...@stoner.com
Matthias Hofmann wrote:
> The reason why I need to compare these flaoting point values for equality
> is, that sometimes there might be more than on type of resource with the
> same priority. If this is true, then the price decides: If two priorities
> compare equal, the computer is supposed to buy the cheaper type of resource.
I'd say you have an algorithmic question more than a language question.
It sounds like you are going to make a discreet decision (DoA(),
DoB(), DoC()) based on floating point values.
In this situation, there is always a point where a very small change in
the input will make a big difference in the result. You can play games
with epsilon to move that point, but the point will still exist.
In some contexts it may be more appropriate to make the output
continuous (DoA(0.9)+DoB(0.1)) rather than discreet.
Will a particular kick of a soccer ball at an undefended goal end up
scoring? Some kicks are so bad the answer is clearly no. Some kicks
are so good the answer is clearly yes. Some kicks are just enough
in-between that the uncertainty principle says you can't be sure. On a
larger scale, you'll reach the point where the decision is made by the
what the referee sees, rather than by where the ball actually went
(whatever that exactly means at sub-atomic scales).
When you have code that says
if(edge_of_ball == edge_of_goal_line)
return ArbitraryRefereeRuling();
The decision to add epsilon to that test is mostly a matter of
game-play. It really isn't a language decision.
Pete Becker
> Pete Becker wrote:
>
>>Thant Tessman wrote:
>>
>>
>>>Of course it's the right answer. 1 divided by 3 is 0 with a remainder of
>>>1. Ask any third grader.
>>>
>>
>>
>>Unfortunately, most of us are no longer third graders. It takes an
>>effort for beginners to grasp that float f = 1/3; sets f to 0.
>
>
> You can also consult any book on number theory if there's no third
> grader handy.
Most people think that 1/3 means one third, not zero. Citing number
theory, the C or C++ Standard, or God doesn't change that.
> The point is that it *is* the right answer and that it
> *is* exact in a sense unsupported by IEEE floating-point numbers.
Yes, it's the "right" answer in that it's what the C and C++ standards
say it means. That's not at all the same as saying that it's obvious
what it means, or that it doesn't take any special training to recognize
its actual meaning. And IEEE floating-point nubers support "exactness"
in exactly the same way: to people trained in limited-precision
arithmetic computations with real-world data (i.e. scientists and
engineers) the results are not surprising.
--
Pete Becker
Roundhouse Consulting, Ltd.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Jerry Coffin
online.net>, hof...@anvil-soft.com says...
[ ... ]
> Note that I have taken a less conservative approach by comparing the
> difference for being 'less or equal' rather than 'less'.
Actually, you're being a lot more conservative. The less
or equal vs. less than is a minor issue -- it only
changes the decision with respect to one exact bit
pattern.
At the same time, the comparison you're doing isn't
further scaling that result. You're scaling epsilon to
tell you the minimum possible change at the magnitude of
numbers you're dealing with, and then using that as the
total deviation that's allowed. IOW, you're basically
saying you'll allow the least significant bit to differ,
but that's all.
As I posted it, the function had a factor to allow you to
specify how many least-significant digits to ignore in
the comparison. This makes it easy to decide that (for
example) if two numbers are equal to 10 places after the
decimal point, you'll treat them as equal, rather than
requiring them to be equal all the way out to 15 digits
(or so) before you consider them equal.
If you're doing any more than extremely minimal
computation on the values before they're compared,
chances are you no longer have enough precision to
justify such a tight tolerance.
> I guess I am still
> somewhat influenced by the function I found in the FAQ (
> http://www.parashift.com/c++-faq-lite/newbie.html#faq-29.17 ), which
> basically does the same thing but without being commutative. I hope that my
> most recent approach is otherwise fine.
Well, I've certainly seen a whole lot worse in any case.
--
Later,
Jerry.
The universe is a figment of its own imagination.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
ThosRTanner
Thant Tessman wrote:
> The real problem with C++ (inherited from C of course) is that the rules
> that decide whether integer or floating-point math is to be used are
> somewhat ad hoc and based on subtle notational clues. When I was first
> learning C, I once prepended a zero in front of an integer to get some
> numbers to line up in the source. I was convinced the computer was
> simply broken. When I found out what was really going on, it was the
> first time I reacted to anything computer-related with: "That's really
> stupid." I was a teenager at the time. It was a sort of rite-of-passage.
>
rites-of-passage in learning C. I think the syntax suffers a lot from
having tried to reduce the number of keystrokes required to implement
anything to a minimum. Leading 0 meaning octal number is merely one of
those, implicit conversion of anything to boolean is another.
I always thought C lost a lot by dropping the VALOF/RESULTIS construct
that BCPL had. I still have occasions when I wish for it, even in C++.
>From the point of view of new programmers, the parsing of a < b < c as
(a < b) < c is a bit of a pain as well (another thing that BCPL
managed).
Francis Glassborow
<peteb...@acm.org> writes
>Most people think that 1/3 means one third, not zero. Citing number
>theory, the C or C++ Standard, or God doesn't change that.
But this is a consequence of the dual use of a solidus as a division
operator (in computing) and as a separator for numerator and denominator
when writing fractions on one line (become much more common with word
processors). This introduces an ambiguity which often misleads. The
newbie programmer has to learn that it is unambiguously a division
operator. They also have to realise something that far too many teachers
do not, that division is an overloaded operation in mathematics with the
context determining the correct answer. If asked how many 3 metre
lengths of cloth can be got from 1 metre the answer is zero, but if I
ask how much each child gets if an apple is divided between three of
them, then answer is one third.
The context for division is generally provided by the type system in a
programming language.
--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects
Thant Tessman
> Thant Tessman wrote:
>>The point is that it *is* the right answer and that it
>>*is* exact in a sense unsupported by IEEE floating-point numbers.
>
>
> Yes, it's the "right" answer in that it's what the C and C++ standards
> say it means. That's not at all the same as saying that it's obvious
> what it means, or that it doesn't take any special training to recognize
> its actual meaning.
No! It's *not* the right answer because the C and C++ standards says so!
It's the right answer because it's the right answer when you're doing
integer math, and it does *not* require specialized training to remind
someone that 1 divided by 3 is 0 in integer math. What requires
specialized training is knowing that C will use integer math if both
operands of the '/' operator are integers even if the result is assigned
to a variable of type 'float' or 'double,' and that if you type a
literal number without a decimal point and without an exponent, it is
considered an integer by the C/C++ language.
It is a mistake for someone with a lot of experience with C/C++ to brush
off the confusion of beginners as nothing more than the consequence of
the lack of specialized training. Sometimes--just sometimes--confusion
is the product of BAD DESIGN. Implementations of one of my favorite
languages typically support rational arithmetic. That is, 1/3 really is
one-third, and 1/3*3 really does equal one. The language also supports
integer division because integer division really is what you want
sometimes. But it doesn't use the '/' symbol to represent it. This is
GOOD DESIGN.
> And IEEE floating-point nubers support "exactness"
> in exactly the same way: to people trained in limited-precision
> arithmetic computations with real-world data (i.e. scientists and
> engineers) the results are not surprising.
An understanding of the limitations of IEEE floating-point numbers does
indeed require specialized training. (Someone in this thread already
referenced a really good paper on the subject.) But, to repeat myself,
IEEE floating-point numbers do *not* support exactness in the same way
as integer math. No amount of specialized training makes floating-point
numbers exact. It may make them useful in real-world situations, but it
does not make them exact. Yes, in SOME SITUATIONS, precision is limited
by your ability to measure, and therefore precision beyond a certain
amount is misleading, but the notion of "exactness" is not as etherial
as you pretend.
-thant
--
"The nationalist not only does not disapprove of atrocities
committed by his own side, but he has a remarkable capacity
for not even hearing about them." -- George Orwell
kanze
> Pete Becker wrote:
> > Thant Tessman wrote:
> >>The point is that it *is* the right answer and that it *is*
> >>exact in a sense unsupported by IEEE floating-point numbers.
> > Yes, it's the "right" answer in that it's what the C and C++
> > standards say it means. That's not at all the same as saying
> > that it's obvious what it means, or that it doesn't take any
> > special training to recognize its actual meaning.
> No! It's *not* the right answer because the C and C++
> standards says so! It's the right answer because it's the
> right answer when you're doing integer math, and it does *not*
> require specialized training to remind someone that 1 divided
> by 3 is 0 in integer math.
I guess it depends on your training. In third grade, I learned
that 1 divided by 3 was 0, with a remainder of 1. Later (fourth
or fifth grade), I learned long division, and learned that 1
divided by 3 was 0.33333... Still later, I learned that there
were different sets of numbers: in the set of rational numbers,
1 divided by 3 was 1/3; in the set of reals, it was 0.33333...,
and in the set of integers, division wasn't defined.
As Francis points out, the '/' character is an overloaded
operation in C++. Arguably, it is a case of overload abuse --
but this may be because for various reasons we think of it as
the "division" operator. And as Pete points out, beginners in
C++, particularly those from an engineering background, find the
results surprising.
I don't have any simple solution to the problem. Maybe it
doesn't even need one -- while it's a problem, it's a lot
simpler problem than machine floating point, and I don't have a
solution to that one either. But Pete's raw statement, that
integer arithmetic has similar problems, remains true. For the
rest, I doubt that Pete would claim that teaching programmers to
handle the anomalies in integral arithmetic is anywhere near as
difficult as teaching them to handle the anomalies in floating
point arithmetic.
[...]
> > And IEEE floating-point nubers support "exactness" in
> > exactly the same way: to people trained in limited-precision
> > arithmetic computations with real-world data (i.e.
> > scientists and engineers) the results are not surprising.
> An understanding of the limitations of IEEE floating-point
> numbers does indeed require specialized training. (Someone in
> this thread already referenced a really good paper on the
> subject.) But, to repeat myself, IEEE floating-point numbers
> do *not* support exactness in the same way as integer math.
> No amount of specialized training makes floating-point numbers
> exact.
This is where I disagree. The results of a floating point
operation, using IEEE is exact. Always. The problem isn't that
it isn't exact; the problem is that the operation has a somewhat
different definition than it does over the set of real numbers.
Just as integral division has a different definition than
division over the set of real numbers.
The important point, in both cases, is to realize that you are
NOT dealing with real numbers, to learn the rigorous and exact
definitions of the operations over the set of numbers you are
dealing with, and to work with that.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
John G Harris
<peteb...@acm.org> writes
<snip>
>Most people think that 1/3 means one third, not zero. Citing number
>theory, the C or C++ Standard, or God doesn't change that.
<snip>
A nine-year old would think it means quotient zero, remainder 1.
A 16-year old would think it means 0.33333333333333333... .
An electronics student would think it means (0.3333 + j0.0).
Moral :
Implicit type-casting is evil.
Turning requirements into code is difficult.
John
--
John Harris
Thant Tessman
> [...] And as Pete points out, beginners in
> C++, particularly those from an engineering background, find the
> results surprising.
Pete Becker made a much stronger statement than that. Earlier, Greg
Herlihy wrote:
> There is a sharp difference between fixed and floating point
> representations. The difference is not merely one of scale. The
> difference is that one is exact, and the other is not. 1 divided by 3
> using integer division produces an exact result: 0. The 0 valued result
> is not an approximation of the actual value,
Pete Becker responded:
> Nonsense. It's not the right answer. We accept it because we know how
> integer arithmetic works, not because it's correct in any mathematical
> sense. [...]
And in this case Pete Becker is simply flat-out wrong. In integer math,
1 divided by 3 is 0. Period. At least in this case, there is no
compromise in the way integer math works in C with the way integer math
works according to mathematicians.
> This is where I disagree. The results of a floating point
> operation, using IEEE is exact. Always. The problem isn't that
> it isn't exact; the problem is that the operation has a somewhat
> different definition than it does over the set of real numbers.
If you want to define exactness in that way, go for it. However...
> The important point, in both cases, is to realize that you are
> NOT dealing with real numbers, to learn the rigorous and exact
> definitions of the operations over the set of numbers you are
> dealing with, and to work with that.
The point is that as long as your calculations don't overflow, integers
in C really do model mathematical integers. [*] And in integer math, 1
divided by 3 is *exactly* zero. On the other hand, IEEE floating point
numbers as a rule don't model integers, rational numbers, or reals in
any way that the term "exact" has any business being applied to. They
are undoubtedly a useful compromise, but the C++ programmer especially
has a huge range of options when it comes to deciding where that
compromise should be made. That's why I brought up my
arbitrary-precision rational number class.
(http://www.standarddeviance.com/sigma) You can theoretically do even
better than that by implementing a "number" class that solves things
symbolically and calculates actual numeric values only on demand. (Think
Mathematica.) This would allow even equations involving transcendental
functions to be solved "exactly" in some situations.
Obfuscating the fact that integers are "exact" in a sense that
floating-point numbers aren't also simultaneously obfuscates the fact
that the C++ programmer can make a choice about when to give up
exactness for the sake of expediency. As a side issue, I also claim that
C is confusing not because integer math is confusing, but because the
way C decides when to do integer math is confusing. But if I haven't
made my point by now, I probably never will...
-thant
[*] There can be other problems with integer math in C, like division
and modulo being broken when operands are negative.
-thant
kanze
> kanze wrote:
> In integer math, 1 divided by 3 is 0. Period. At least in
> this case, there is no compromise in the way integer math
> works in C with the way integer math works according to
> mathematicians.
Not the mathematicians I know. What I learned, when I got to
the level it was called mathematics, and not arithmetic, was
that division isn't defined over the set of integers.
> > This is where I disagree. The results of a floating point
> > operation, using IEEE is exact. Always. The problem isn't
> > that it isn't exact; the problem is that the operation has a
> > somewhat different definition than it does over the set of
> > real numbers.
> If you want to define exactness in that way, go for it.
> However...
I can see only two possible definitions. One is that every
operation has a rigorously defined results, and if that result
isn't present in the set being considered, the operation isn't
defined. The other is that we define the operation over the
set, with possibly different results than that it would have
over a different set.
And I will pleed guilty to being inconsistent:-). The reason
division isn't defined over the set of integers is obviously
because the exact (or correct) result isn't representable. All
I'm really saying here is that we are doing exactly the same
thing in the case of floating point arithmetic and integer
arithmetic: faced with an operation which gives a "wrong" result
over the set we are dealing with, we redefine the operator. I
don't know whether this is mathematically justifiable -- I
rather doubt it, actually. But it is useful.
> > The important point, in both cases, is to realize that you
> > are NOT dealing with real numbers, to learn the rigorous and
> > exact definitions of the operations over the set of numbers
> > you are dealing with, and to work with that.
> The point is that as long as your calculations don't overflow,
> integers in C really do model mathematical integers. And in
> integer math, 1 divided by 3 is *exactly* zero.
Not in the math I learned.
> On the other hand, IEEE floating point numbers as a rule don't
> model integers, rational numbers, or reals in any way that the
> term "exact" has any business being applied to.
Exactly. I've found that to be one of the most effective ways
of presenting the problem -- IEEE floating point numbers are NOT
real numbers. The are IEEE floating point numbers. As such,
they have their own set of operators, which, because of
limitations in the available character set, we use classical
operator symbols to represent. But + on a floating point value
is NOT the addition of two real numbers.
And the results of these operations is exact -- it's just not
the same result as we would have in real arithmetic. The issue
is in all points similar to that of 1/3 in integer arithmetic,
except, of course, that it affects all of the operators, and not
just one. (And that there is no other set in mathematics which
has similar properties.)
Once this point has been assimilated, we can begin to evaluate
under what conditions they are a close enough approximation for
the problem at hand. In practice, there are cases where double,
or even float, is sufficiently close to real numbers that we can
use it directly, as such. (After hearing all of the details, I
think that the original posters problem is probably one of them.)
If, however, such is not the case (and it often isn't), you do
have to know how to manipulate the exact results of IEEE
floating point arithmetic, in order to obtain the desired
results (which should generally be something similar to what you
get over the domain of reals).
> They are undoubtedly a useful compromise, but the C++
> programmer especially has a huge range of options when it
> comes to deciding where that compromise should be made.
> That's why I brought up my arbitrary-precision rational number
> class. (http://www.standarddeviance.com/sigma) You can
> theoretically do even better than that by implementing a
> "number" class that solves things symbolically and calculates
> actual numeric values only on demand. (Think Mathematica.)
> This would allow even equations involving transcendental
> functions to be solved "exactly" in some situations.
> Obfuscating the fact that integers are "exact" in a sense that
> floating-point numbers aren't also simultaneously obfuscates
> the fact that the C++ programmer can make a choice about when
> to give up exactness for the sake of expediency.
It's not obfuscation IF you state that it only affects division
in the int's, but affects every single operation in floating
point.
> As a side issue, I also claim that C is confusing not because
> integer math is confusing, but because the way C decides when
> to do integer math is confusing. But if I haven't made my
> point by now, I probably never will...
If your point is that C has some very confusing rules concerning
type matching, promotion, etc., you're preaching to a
convert:-). And the point isn't that integer math is confusing;
it's just that it is (slightly) different from math in the real
world.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Matthias Hofmann
news:1141145135....@z34g2000cwc.googlegroups.com...
> In this situation, there is always a point where a very small change in
> the input will make a big difference in the result. You can play games
> with epsilon to move that point, but the point will still exist.
This is true, but that problem is not limited to floating point numbers. A
small change in the input will also make a big difference in the result if I
use integer values.
> In some contexts it may be more appropriate to make the output
> continuous (DoA(0.9)+DoB(0.1)) rather than discreet.
Unfortunately this is not possible in my algorithm. The resources are
objects on a map, and the artificial intelligence has to decide which one to
purchase. It cannot, however, buy only a fraction of it.
> Will a particular kick of a soccer ball at an undefended goal end up
> scoring? Some kicks are so bad the answer is clearly no. Some kicks
> are so good the answer is clearly yes. Some kicks are just enough
> in-between that the uncertainty principle says you can't be sure. On a
> larger scale, you'll reach the point where the decision is made by the
> what the referee sees, rather than by where the ball actually went
> (whatever that exactly means at sub-atomic scales).
>
> When you have code that says
> if(edge_of_ball == edge_of_goal_line)
> return ArbitraryRefereeRuling();
> The decision to add epsilon to that test is mostly a matter of
> game-play. It really isn't a language decision.
The ruling of the referee is not arbitrary in my case. When the floats
compare equal, the price (which is an integral type) decides. Or, taking
your example, if the edge of the ball is on the edge of the goal line, the
goal scores if the goalkeeper's team has bribed the referee with less money
than the other team. The choice of epsilon, however, determines when the
ball is on the edge.
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Thant Tessman
> Thant Tessman wrote:
>
>>In integer math, 1 divided by 3 is 0. Period. At least in
>>this case, there is no compromise in the way integer math
>>works in C with the way integer math works according to
>>mathematicians.
>
>
> Not the mathematicians I know. What I learned, when I got to
> the level it was called mathematics, and not arithmetic, was
> that division isn't defined over the set of integers.
Then how come my book on number theory has an entire chapter on it?
(Chapter 2 of "Number Theory and Its History" by Oystein Ore.)
[...]
-thant
--
"The people cannot delegate to government the power to do anything
which would be unlawful for them to do themselves." -- John Locke,
A Treatise Concerning Civil Government
Matthias Hofmann
> As I posted it, the function had a factor to allow you to
> specify how many least-significant digits to ignore in
> the comparison. This makes it easy to decide that (for
> example) if two numbers are equal to 10 places after the
> decimal point, you'll treat them as equal, rather than
> requiring them to be equal all the way out to 15 digits
> (or so) before you consider them equal.
>
> If you're doing any more than extremely minimal
> computation on the values before they're compared,
> chances are you no longer have enough precision to
> justify such a tight tolerance.
You are right, the function you posted can also be used in more general
cases than mine. However, I am only going to use my implementation as a
private function of the class which applies my algorithm, so it is only used
in that context.
But there is one more thing I about the comparison for being 'less or equal'
that I relalized after I had submitted my post: Comparing for being 'less'
will not work if both operands are zero, as this practically leads to the
following expression in the return statement:
return 0 < epsilon * fabs( 0 ) || 0 < epsilon * fabs( 0 );
As zero cannot be less than zero, the function call IsEqual( 0, 0 ) will
return 'false'. So the comparison has to be for 'less than equal', or else
there is something about the behaviour of floating point types that I don't
know...
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Eugene Gershnik
>
> Maybe this the time to explain what I am actually doing in my program...
[...]
> - It determines the amount currently on stock for each type of resource
> (there are three types, let's call them a, b and c), which is stored in
> variables a_stock, b_stock and c_stock.
Which I assume are integers.
> - It determines the share (the percentage) of each resource on stock:
> a_share_stock = ( a_stock == 0 ) ? 0 : a_stock / ( a_stock + b_stock +
> c_stock );
> // Same with b and c.
>
> - It determines the amount required in production for each type of resource,
> which is stored in variables a_needed, b_needed and c_needed.
>
> - It determines the share (the percentage) of each resource needed:
> a_share_needed = ( a_needed == 0 ) ? 0 : a_needed / ( a_needed + b_needed +
> c_needed );
> // Same with b and c.
[...]
See http://www.boost.org/libs/rational/rational.html
You deal with rational fractions so a library that provides rational
numbers suits your requirements exactly. floats and doubles don't.
--
Eugene
wa...@stoner.com
Matthias Hofmann wrote:
> The ruling of the referee is not arbitrary in my case. When the floats
> compare equal, the price (which is an integral type) decides. Or, taking
> your example, if the edge of the ball is on the edge of the goal line, the
> goal scores if the goalkeeper's team has bribed the referee with less money
> than the other team. The choice of epsilon, however, determines when the
> ball is on the edge.
If you use epsilon, you get cases where
a < b
b < c
c < a
and in that case I'd say your choice becomes arbitrary (and your search
might not terminate).
A continous "selection" algorithm that is transitive might be
NeedA + 0.00001*PriceA < NeedB + 0.00001*PriceB
This might be better or worse in terms of game play. However it has
the advantage that
a < b && b < c
guarantees
a < c
and in many contexts that is useful. If your equivalence classes (and
other relations) are not transitive, you will see existing algorithms
(std::sort) crash.
There are other ways to get transitive equivalence classes (round
quantities to the nearest liter or cubic light-year (depending on the
game), ...) that have much of the same feel as an "epsilon" solution.
Jerry Coffin
a...@standarddeviance.com says...
[ ... ]
> And in this case Pete Becker is simply flat-out wrong. In integer math,
> 1 divided by 3 is 0. Period. At least in this case, there is no
> compromise in the way integer math works in C with the way integer math
> works according to mathematicians.
This is open to some argument. From one viewpoint, you're
right: in discrete math, that's the answer. From another
viewpoint, discrete math as a whole is simply an
approximation to real math, and 0 simply happens to be
its closest available approximation to one third.
None of these, however, is anything sacred. They're all
just sets of rules people have put together. Some of
those sets of rules were invented a long time ago, and
some more recently. The fact that one was invented longer
ago doesn't make it necessarily a whole lot better.
Consider as well that there's been a dichotomy throughout
almost the entire history of real math -- that on one
hand we can imagine real math being carried out to
arbitrary precision, but that in any real computation we
can't do that -- and long before electronic computers
came along, people rules for computation. Again, however,
there wasn't just one set of rules -- bankers and
scientists (for example) used slightly different rules
because they had slightly different goals. Neither system
can claim an superiority in a moral sense though --
they're just systems we invented and the only right or
wrong involved is whether the rules were followed or not.
In that respect, computers are starting to do pretty well
-- they're quite dependable in following the rules
they're given, and the rules they're given now mostly
coincide quite closely with what they "should" be.
> > This is where I disagree. The results of a floating point
> > operation, using IEEE is exact. Always. The problem isn't that
> > it isn't exact; the problem is that the operation has a somewhat
> > different definition than it does over the set of real numbers.
>
> If you want to define exactness in that way, go for it. However...
He's absolutely correct from one viewpoint -- given some
inputs and some operations, there's exactly one
acceptable result, and it's completely dependable,
repeatable, etc.
That's a rather loose approximation of real math, but
usually a pretty close approximation of the rules for how
computation should be done that existed before computers
came along. When it differs from those rules, it's
usually for the better. The rules continue to evolve to
cover (for example) areas that most people simply ignored
even a couple of decades ago.
> > The important point, in both cases, is to realize that you are
> > NOT dealing with real numbers, to learn the rigorous and exact
> > definitions of the operations over the set of numbers you are
> > dealing with, and to work with that.
>
> The point is that as long as your calculations don't overflow, integers
> in C really do model mathematical integers. [*]
#include <iostream>
int main() {
int x = -1;
unsigned y = 0;
if (x > y)
std::cout << "I'm not sure I agree.";
return 0;
}
There are differences between floating point math and
real math. There are differences between integer math and
discrete math.
Most of the limits on correct integer calculation are
fairly simple. When things go wrong, they usually do so
in a fairly spectacular fashion so it's fairly easy to
catch and typically quite memorable.
The limitations on floating point calculation are subtle
enough that most people never really understand them.
Even when things go badly wrong, it's often not obvious
or particularly memorable.
--
Later,
Jerry.
The universe is a figment of its own imagination.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Jerry Coffin
online.net>, hof...@anvil-soft.com says...
[ ... ]
> But there is one more thing I about the comparison for being 'less or equal'
> that I relalized after I had submitted my post: Comparing for being 'less'
> will not work if both operands are zero, as this practically leads to the
> following expression in the return statement:
>
> return 0 < epsilon * fabs( 0 ) || 0 < epsilon * fabs( 0 );
>
> As zero cannot be less than zero, the function call IsEqual( 0, 0 ) will
> return 'false'. So the comparison has to be for 'less than equal', or else
> there is something about the behaviour of floating point types that I don't
> know...
I hadn't thought of that, but you're certainly correct.
The real root of the problem is using the numbers as-is
rather than using their magnitudes. It's harder to
follow, but it's probably better to combine our precision
specification with their magnitude to get our epsilon:
bool isEqual(double a, double b, double prec = 1e-9) {
int mag1, mag2;
frexp(a, &mag1);
frexp(b, &mag2);
if ( mag1 != mag2)
return false;
double epsilon = ldexp(prec, mag1);
double difference = std::abs(a-b);
return difference <= epsilon;
}
With this, you specify the agreement in terms of the
number of significant digits -- the default I've provided
requires agreement to ten significant digits to call
numbers equal. If you were going to use this with
different levels of precision on a regular basis, a
functor would probably be more convenient:
class isEqual {
double prec_;
public:
isEqual(double prec=1e-9) : prec_(prec) {}
bool operator()(double a, double b) {
int mag1, mag2;
frexp(a, &mag1);
frexp(b, &mag2);
if ( mag1 != mag2)
return false;
double epsilon = ldexp(prec_, mag1);
double difference = std::abs(a-b);
return difference <= epsilon;
}
}
--
Later,
Jerry.
The universe is a figment of its own imagination.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Greg Herlihy
kanze wrote:
> Thant Tessman wrote:
> > kanze wrote:
>
> > In integer math, 1 divided by 3 is 0. Period. At least in
> > this case, there is no compromise in the way integer math
> > works in C with the way integer math works according to
> > mathematicians.
>
> Not the mathematicians I know. What I learned, when I got to
> the level it was called mathematics, and not arithmetic, was
> that division isn't defined over the set of integers.
If multiplication is defined over the set of integers, then division -
being its inverse - must be defined as well. And clearly 2 multiplied
by 2 is defined, so 4 divided by 2 is as well.
> > > This is where I disagree. The results of a floating point
> > > operation, using IEEE is exact. Always. The problem isn't
> > > that it isn't exact; the problem is that the operation has a
> > > somewhat different definition than it does over the set of
> > > real numbers.
>
> > If you want to define exactness in that way, go for it.
> > However...
>
> I can see only two possible definitions. One is that every
> operation has a rigorously defined results, and if that result
> isn't present in the set being considered, the operation isn't
> defined. The other is that we define the operation over the
> set, with possibly different results than that it would have
> over a different set.
An IEEE value represents a consistent approximation for a particular
value - but the value represented is not exactly the value calculated.
And the fact that dividing 1 by 3 will produce similar, but not
identical, values when using floats or when using doubles demonstrates
that resulting value in either case is an approximation of the value
calculated.
Integer math by contrast does not exhibit this kind of disagreement.
Dividing 1 by 3 with either short or long values both yield 0
identically - proof positive that the result of the operation defined
for integer division is no more, no less, but exactly: 0.
Because the results of integer division across implementations are
always in agreement, while the corresponding results for floating point
division are not, we can conclude that integer values are always exact,
while floating point values are not.
Greg
Jerry Coffin
@j33g2000cwa.googlegroups.com>, gre...@pacbell.net
says...
[ ... ]
> Because the results of integer division across implementations are
> always in agreement, while the corresponding results for floating point
> division are not, we can conclude that integer values are always exact,
> while floating point values are not.
I'm sorry, but repeatable and exact are not synonymous.
--
Later,
Jerry.
The universe is a figment of its own imagination.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Jerry Coffin
@z34g2000cwc.googlegroups.com>, wa...@stoner.com says...
[ ... ]
> If you use epsilon, you get cases where
> a < b
> b < c
> c < a
If so, whoever's implemented the comparison has screwed
up completely, and none of what's being implemented works
right at all.
It is possible for:
a == b
b == c
a < c
But the inequalities you've shown above simply can't
happen. If you use epsilon:
a < b translates to: a + epsilon < b
b < c translates to: b + epsilon < c
Your third inequality then requires that:
a + 2 * epsilon < a
Since epsilon is basically a distance it can never be
negative, so this simply isn't possible unless somebody's
a) completely mis-defined epsilon, or b) completely mis-
defined the comparisons using epsilon.
--
Later,
Jerry.
The universe is a figment of its own imagination.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Thant Tessman
> In article <du536c$vsv$1...@news.xmission.com>,
> a...@standarddeviance.com says...
>
> [ ... ]
>
>
>>And in this case Pete Becker is simply flat-out wrong. In integer math,
>>1 divided by 3 is 0. Period. At least in this case, there is no
>>compromise in the way integer math works in C with the way integer math
>>works according to mathematicians.
>
>
> This is open to some argument. From one viewpoint, you're
> right: in discrete math, that's the answer. From another
> viewpoint, discrete math as a whole is simply an
> approximation to real math, and 0 simply happens to be
I didn't say "1 divided by 3 is 0." I said "In integer math, 1 divided
by 3 is 0." Are you really trying to debate this? My interest in number
theory came from an interest in cryptography. The notion that integer
math is merely an "approximation" for real math is absurd. Sometimes you
really do want to do integer math. Sometimes you don't.
Remember, this whole thread was about the ability to compare values for
equality. I suggest that any attempt to pin down the meaning of equality
is doomed without some kind of understanding of exactness--an
understanding of exactness that is *not* captured by floating-point
math. Even conditions as supposedly familiar as:
a(b+c) == a*b + a*c
are not at all guaranteed to hold under floating-point math. Hell, even:
a*b*c == c*b*a
isn't guaranteed to hold, and I'm not even sure you're allowed to rely on:
a*b == b*a
I would have thought this was a pretty simple point to make, and lack of
"exactness" would seem to be a pretty appropriate word to describe why
it is that floating-point numbers don't satisfy these conditions and
integers do, but programming in C or C++ for too long can apparently
really screw up people's thinking on the topic.
>>The point is that as long as your calculations don't overflow, integers
>>in C really do model mathematical integers. [*]
>
>
> #include <iostream>
>
> int main() {
> int x = -1;
> unsigned y = 0;
>
> if (x > y)
> std::cout << "I'm not sure I agree.";
> return 0;
> }
Argh! Even I qualified my statement with a footnote. (And "unsigned"
isn't an integer. It's a whole number (or non-negative integer if you
prefer). That C/C++ allows the programmer to compare them with the '>'
operator is merely another example of BAD DESIGN.)
[...]
-thant
kanze
> kanze wrote:
>> Thant Tessman wrote:
>>> kanze wrote:
>>> In integer math, 1 divided by 3 is 0. Period. At least
>>> in this case, there is no compromise in the way integer
>>> math works in C with the way integer math works according
>>> to mathematicians.
>> Not the mathematicians I know. What I learned, when I got
>> to the level it was called mathematics, and not arithmetic,
>> was that division isn't defined over the set of integers.
> If multiplication is defined over the set of integers, then
> division - being its inverse - must be defined as well. And
> clearly 2 multiplied by 2 is defined, so 4 divided by 2 is as
> well.
Why?
If division is defined over the set of integers, it is not the
inverse of multiplication, because there is no inverse of
multiplication for integers (anymore than there is an inverse of
addition for natural numbers).
>>>> This is where I disagree. The results of a floating
>>>> point operation, using IEEE is exact. Always. The
>>>> problem isn't that it isn't exact; the problem is that
>>>> the operation has a somewhat different definition than
>>>> it does over the set of real numbers.
>>> If you want to define exactness in that way, go for it.
>>> However...
>> I can see only two possible definitions. One is that every
>> operation has a rigorously defined results, and if that
>> result isn't present in the set being considered, the
>> operation isn't defined. The other is that we define the
>> operation over the set, with possibly different results than
>> that it would have over a different set.
> An IEEE value represents a consistent approximation for a
> particular value - but the value represented is not exactly
> the value calculated.
An IEEE number represents a value in a specific, finite set. It
doesn't approximate anything what so ever. An IEEE number has
an exact value.
If we speak of "approximation" with regards to IEEE values, it
is because the result of specific operations (including
conversion to/from a string) result in an "approximation" of the
value we would get using real numbers. The resulting value,
taken for itself, is exact; it is only as a result of a specific
operation that it can be considered an "approximation".
This is a very important point if you are analysing the
stability of a recursion. The analysis must deal with the exact
actual results, and not the approximation -- formulas which
converge in real arithmetic may fail to converge in IEEE
floating point arithmetic. The results of the operation in IEEE
arithmetic are exact in the sense that they are precisely
defined -- the result you get is not +/- some epsilon, and is
exactly the same every time you do the operation. (In fact,
this is not strictly true, in that some IEEE implementations use
a more precise representation in some intermediate values.
While this typically results in a better approximation of the
real values, especially in naive use, it can make reasoning
about things like convergent extremely difficult.)
> And the fact that dividing 1 by 3 will produce similar, but
> not identical, values when using floats or when using doubles
> demonstrates that resulting value in either case is an
> approximation of the value calculated.
No. It demonstrates that the set of valid values for floats is
not the same as the set of valid values for double. Something
which seems intuitively obvious to me, based on information
theory and the number of bits used in the representation.
> Integer math by contrast does not exhibit this kind of
> disagreement. Dividing 1 by 3 with either short or long
> values both yield 0 identically - proof positive that the
> result of the operation defined for integer division is no
> more, no less, but exactly: 0.
So if we redefine division of all of the machine types so that
it always results in 0, we solve all problems. An interesting
theory.
The definition of division that I'm used to seeing is that it is
the inverse of multiplication; i.e. if a * b = c, then c / a =
b, for all a, b and c where a != 0. The conventions I've seen
used (but it is now evident that they are not the only ones
possible) is that division is *only* defined where this
equivalence holds. (Strictly speaking, division isn't defined
for the set R of real numbers, but only as a function of R*R',
where R' is the set of real numbers minus 0.)
Other definitions are, of course, possible -- and apparently,
used in specific contexts. Using the actual results of division
in IEEE arithmetic as a definition of division, and considering
them exact, is an example of this. It's no different in
principal than saying that 1/3 results in 0 in integral
arithmetic. In both cases, you are faced with a definition of
division for which the basic equality above, a * b = c <=> c / a
= b, does not hold.
That doesn't mean that such a definition is useless. Quite the
contrary -- I use it all the time. It does mean that when
reasoning about a program or an expression, you must never
forget that you are using a special definition of the operation,
and not the usual definition.
> Because the results of integer division across implementations
> are always in agreement, while the corresponding results for
> floating point division are not, we can conclude that integer
> values are always exact, while floating point values are not.
I hate to say it, but that sounds like nonsense. Or just hand
waving. It doesn't seem to address any real issue.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
kanze
> kanze wrote:
> > Thant Tessman wrote:
> >>In integer math, 1 divided by 3 is 0. Period. At least in
> >>this case, there is no compromise in the way integer math
> >>works in C with the way integer math works according to
> >>mathematicians.
> > Not the mathematicians I know. What I learned, when I got
> > to the level it was called mathematics, and not arithmetic,
> > was that division isn't defined over the set of integers.
> Then how come my book on number theory has an entire chapter
> on it? (Chapter 2 of "Number Theory and Its History" by
> Oystein Ore.)
Clearly, we're using different books:-).
I think we can agree that there are two possible approaches:
division is defined over the set of integers, but the definition
results in an operation which has different properties than
division over the set of real numbers, or division is defined,
period, and if a set does not support it, then it is not defined
over that set.
Generally, what I've seen is that when the definition is
different, there is a tendancy to prefer different operators:
modular addition over an interval of integers is different from
integer/real addition, and is usually represented by a distinct
symbol, a plus character in a circle.
IMHO, whatever approach you take, there are two things you can
say concerning computer arithmetic:
-- regardless of the type, it makes some compromizes with
regards to what we expect -- I expect 1/3 and 2/3 to result
in different values, for example, and
-- coping with these differences is several orders of magnitude
easier in the case of integral values than in the case of
floating point.
In sum, it's a general problem, affecting all machine
arithmetic, but it is simple to manage for the int's, and
incredibly difficult for floating point values.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Francis Glassborow
Herlihy <gre...@pacbell.net> writes
>If multiplication is defined over the set of integers, then division -
>being its inverse - must be defined as well. And clearly 2 multiplied
>by 2 is defined, so 4 divided by 2 is as well.
This is drifting way off topic for this group. One of the problems is
that some are referencing the 'higher math' concept of an integer whilst
others are referring to the common math form where children learn 'whole
number' arithmetic first.
Even the assumption that multiplication implies division is debatable.
However putting that to one side, in the case of integer arithmetic in C
and C++ division is NOT the inverse of multiplication. Consider:
unsigned int i = 65535;
unsigned j;
j = i * i;
j = j/i;
What is the mathematical answer? What is the answer on a system where
unsigned int has 16 bits?, 24-bits? 32-bits?
And you might like to consider systems with other numbers of bits
between 16 and 32. But in no case below 32 bits is the answer the
mathematical one.
--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects
Francis Glassborow
<ne...@nospam.demon.co.uk> writes
>A nine-year old would think it means quotient zero, remainder 1.
>
>A 16-year old would think it means 0.33333333333333333... .
And both would be only partially correct. As the first chapter of
Bentley's Programming Pearls points out, before answering a question you
should enquire why the querient needs an answer. Because only then can
you reliably help.
>
>An electronics student would think it means (0.3333 + j0.0).
--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects
Francis Glassborow
wa...@stoner.com writes
>This might be better or worse in terms of game play. However it has
>the advantage that
> a < b && b < c
>guarantees
> a < c
>and in many contexts that is useful. If your equivalence classes (and
>other relations) are not transitive, you will see existing algorithms
>(std::sort) crash.
Would you care to give a single example where your assertion holds even
in theory for a pure numeric system. To the best of my knowledge floats
even on computers are ordered. The problem is that approximately equal
is not a transitive operation and so is not a substitute for true
equality.
--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects
wa...@stoner.com
Francis Glassborow wrote:
> In article <1141318337.4...@z34g2000cwc.googlegroups.com>,
> wa...@stoner.com writes
> >This might be better or worse in terms of game play. However it has
> >the advantage that
> > a < b && b < c
> >guarantees
> > a < c
> >and in many contexts that is useful. If your equivalence classes (and
> >other relations) are not transitive, you will see existing algorithms
> >(std::sort) crash.
>
> Would you care to give a single example where your assertion holds
My assertion that std::sort will crash is based on 25.3/3, which I
believe says that if the comparison function is not a strict weak
ordering the behavior is undefined (of course that might not be a
crash, but it will be if you are lucky).
My assertion that introducing epsilon can induce a circular-less-than
a<b && b<c && c<a
is shown by example in my reply to JC (assuming that makes it past the
moderator).
> ... even in theory for a pure numeric system.
I'm not sure I know what the definition of a pure numeric system is.
If an axiom of a pure numeric system is
a<b && b<c implies ! c<a
then I can prove that MH's system is not a pure numeric system, when
used with epsilon.
Thant Tessman
> In article <JQfU4pKR...@jgharris.demon.co.uk>, John G Harris
> <ne...@nospam.demon.co.uk> writes
>
>>A nine-year old would think it means quotient zero, remainder 1.
>>
>>A 16-year old would think it means 0.33333333333333333... .
>
>
> And both would be only partially correct. As the first chapter of
> Bentley's Programming Pearls points out, before answering a question you
> should enquire why the querient needs an answer. Because only then can
> you reliably help.
These answers are not "partially" correct. They are either correct or
incorrect depending on the situation.
-thant
--
"A free man must be able to endure it when his fellow men act and
live otherwise than he considers proper. He must free himself from
the habit, just as soon as something does not please him, of calling
for the police." -- Ludwig von Mises
Thant Tessman
> Thant Tessman wrote:
>
>>kanze wrote:
>
>
>>>Thant Tessman wrote:
>
>
>>>>In integer math, 1 divided by 3 is 0. Period. At least in
>>>>this case, there is no compromise in the way integer math
>>>>works in C with the way integer math works according to
>>>>mathematicians.
>
>
>>>Not the mathematicians I know. What I learned, when I got
>>>to the level it was called mathematics, and not arithmetic,
>>>was that division isn't defined over the set of integers.
>
>
>>Then how come my book on number theory has an entire chapter
>>on it? (Chapter 2 of "Number Theory and Its History" by
>>Oystein Ore.)
>
>
> Clearly, we're using different books:-).
I also have "Number Theory: A Programmer's Guide" by Mark Herkommer. It
talks about integer division in chapter 2 as well. What book are you
using anyway?
> I think we can agree that there are two possible approaches:
> division is defined over the set of integers, but the definition
> results in an operation which has different properties than
> division over the set of real numbers, or division is defined,
> period, and if a set does not support it, then it is not defined
> over that set.
Um, division *is* defined over the set of integers.
> Generally, what I've seen is that when the definition is
> different, there is a tendancy to prefer different operators:
> modular addition over an interval of integers is different from
> integer/real addition, and is usually represented by a distinct
> symbol, a plus character in a circle.
Which is why some programming languages use a distinct symbol for
integer division. That C/C++ uses '/' to represent both integer division
and floating-point division is a problem with C/C++, not with integer
division.
> IMHO, whatever approach you take, there are two things you can
> say concerning computer arithmetic:
>
> -- regardless of the type, it makes some compromizes with
> regards to what we expect -- I expect 1/3 and 2/3 to result
> in different values, for example, and
If you have an implementation of rational numbers at your disposal, you
can not only be guaranteed that 1/3 and 2/3 are different, but that
(1/3)*2 is *exactly* equal to 2/3.
> -- coping with these differences is several orders of magnitude
> easier in the case of integral values than in the case of
> floating point.
>
> In sum, it's a general problem, affecting all machine
> arithmetic, but it is simple to manage for the int's, and
> incredibly difficult for floating point values.
Floating-point math makes a very specific compromise about exactness in
order to preserve certain properties about precision in a way that is
easy to implement in hardware. The compromise that floating-point math
makes is *not* something that permeates all machine arithmetic. To the
contrary, computers are very good at preserving exactness as long as
you're careful and as long as you don't need to numerically calculate a
transcendental. In this sense, floating-point math *is* categorically
different.
-thant
--
"If they can get you asking the wrong questions, they don't have to worry
about answers." -- Thomas Pynchon
Thant Tessman
> In article <1141344234.849852.108270
> @j33g2000cwa.googlegroups.com>, gre...@pacbell.net
> says...
>
> [ ... ]
>
>
>>Because the results of integer division across implementations are
>>always in agreement, while the corresponding results for floating point
>>division are not, we can conclude that integer values are always exact,
>>while floating point values are not.
>
>
> I'm sorry, but repeatable and exact are not synonymous.
But at the very least, any reasonable notion of "exact" implies
repeatability, wouldn't you say?
-thant
--
"Government is a broker in pillage, and every election is sort of an advance
auction sale of stolen goods." -- H.L. Mencken
kevin cline
Matthias Hofmann wrote:
> The reason why I need to compare these flaoting point values for equality
> is, that sometimes there might be more than on type of resource with the
> same priority. If this is true, then the price decides: If two priorities
> compare equal, the computer is supposed to buy the cheaper type of resource.
I avoid this sort of discrete logic for continuous quantities.
Suppose A has priority -1.001 and costs $100, while B has priority
1.000 and costs $0.01. Should A still be chosen, or would it be better
to expend resources on B first?
I would define a value function that blends priority and price is some
reasonable way.
Thant Tessman
> Greg Herlihy wrote:
>>If multiplication is defined over the set of integers, then
>>division - being its inverse - must be defined as well. And
>>clearly 2 multiplied by 2 is defined, so 4 divided by 2 is as
>>well.
>
>
> Why?
>
> If division is defined over the set of integers, it is not the
> inverse of multiplication, because there is no inverse of
> multiplication for integers (anymore than there is an inverse of
> addition for natural numbers).
Given:
a = qb+r
where a, b, q, and r are integers, and where b is not zero, and where r
can be any positive integer from zero to b-1, then the quotient of a/b
is q, and the remainder is r. (There's an even better definition that's
a bit more careful with the sign of r, but the point is that integer
division *is* very clearly defined.)
> An IEEE number represents a value in a specific, finite set. It
> doesn't approximate anything what so ever. [...]
An IEEE number is not useful because it has an exact value. An IEEE
number is useful only because the exact value it does have is a useful
approximation of some real number. I still don't understand how this can
be considered a controversial statement.
[...]
-thant
Jerry Coffin
a...@standarddeviance.com says...
[ ... ]
> To the
> contrary, computers are very good at preserving exactness as long as
> you're careful and as long as you don't need to numerically calculate a
> transcendental. In this sense, floating-point math *is* categorically
> different.
Or, to put it more succinctly, it's categorically
different except when it's not.
Discrete math and real math both use infinite sets of
numbers, so there's no way any computer can possibly
represent all of the possibilities from either set. In
this sense, floating point math and integer math are
categorically identical.
--
Later,
Jerry.
The universe is a figment of its own imagination.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Bob Bell
> Greg Herlihy wrote:
> > kanze wrote:
> >> Thant Tessman wrote:
> >>> kanze wrote:
>
> >>> In integer math, 1 divided by 3 is 0. Period. At least
> >>> in this case, there is no compromise in the way integer
> >>> math works in C with the way integer math works according
> >>> to mathematicians.
>
> >> Not the mathematicians I know. What I learned, when I got
> >> to the level it was called mathematics, and not arithmetic,
> >> was that division isn't defined over the set of integers.
>
> > If multiplication is defined over the set of integers, then
> > division - being its inverse - must be defined as well. And
> > clearly 2 multiplied by 2 is defined, so 4 divided by 2 is as
> > well.
>
> Why?
>
> If division is defined over the set of integers, it is not the
> inverse of multiplication, because there is no inverse of
> multiplication for integers (anymore than there is an inverse of
> addition for natural numbers).
If I can butt in for a second here, you're talking about whether an
operation is open or closed over a set. Multiplication is closed over
the set of integers; two integers, when multiplied, will yield another
integer. Division is not closed over the set of integers: dividing two
integers can yield a result that is not an integer. Just like addition
is closed over the set of natural numbers, but subtraction is not.
Another such pair of operations is squaring and square root. Squaring
is closed over natural numbers, integers, and real numbers. Square root
is not closed over any of those sets.
This is not quite the same as saying that an operation is or is not
defined, but it is relevant to the discussion.
Bob
Matthias Hofmann
news:1141326055....@v46g2000cwv.googlegroups.com...
> See http://www.boost.org/libs/rational/rational.html
>
> You deal with rational fractions so a library that provides rational
> numbers suits your requirements exactly. floats and doubles don't.
Seems like I should make myself familiar with the boost library! :-) I
already implemented my algorithm using the epsilon method now, and it seems
like it works fine. But I will remember boost's rational class for next
time, thanks anyway for the link! ;-)
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
wa...@stoner.com
Jerry Coffin wrote:
> In article <1141318337.435279.265700
> @z34g2000cwc.googlegroups.com>, wa...@stoner.com says...
>
> [ ... ]
>
> > If you use epsilon, you get cases where
> > a < b
> > b < c
> > c < a
>
> If so, whoever's implemented the comparison has screwed
> up completely, and none of what's being implemented works
> right at all.
>
> It is possible for:
>
> a == b
> b == c
> a < c
>
> But the inequalities you've shown above simply can't
> happen.
Sure they can, when (as in this example), epsilon is applied to the
first part of a two-step test.
MH Wrote:
> struct { double priority; int price; } ResourceInfo; [sic]
>
> // Returns true if a < b.
> bool CompareResources( ResourceInfo a, ResourceInfo b )
> { return ( equal( a.priority, b.priority ) ) ?
> ( a.price < b.price ) : ( a.priority < b.priority ); }
Assuming this implementation of "equal"
bool equal(double x, double y)
{
const double epsilon = 0.5;
return abs(x-y)<epsilon;
}
Given:
ResourceInfo a = { 1.3, 1 };
ResourceInfo b = { 1, 2 };
ResourceInfo c = { 0.7, 3 };
You get
a < b // equal(a.priority,b.priority) && a.price < b.price
b < c // equal(b.priority,c.priority) && b.price < c.price
c < a // !equal(c.priority,a.priority) && c.priority <
a.priority
Matthias Hofmann
news:du86uc$4rd$1...@news.xmission.com...
> >>The point is that as long as your calculations don't overflow, integers
> >>in C really do model mathematical integers. [*]
> >
> >
> > #include <iostream>
> >
> > int main() {
> > int x = -1;
> > unsigned y = 0;
> >
> > if (x > y)
> > std::cout << "I'm not sure I agree.";
> > return 0;
> > }
>
> Argh! Even I qualified my statement with a footnote. (And "unsigned"
> isn't an integer. It's a whole number (or non-negative integer if you
> prefer). That C/C++ allows the programmer to compare them with the '>'
> operator is merely another example of BAD DESIGN.)
What does the C++ Standard say about comparing a signed integer with an
unsigned one?
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
John G Harris
kanze <ka...@gabi-soft.fr> writes
<snip>
>If division is defined over the set of integers, it is not the
>inverse of multiplication, because there is no inverse of
>multiplication for integers (anymore than there is an inverse of
>addition for natural numbers).
<snip>
The long division algorithm that used to be taught to schoolchildren
produces a quotient and a remainder. It is still called division even
though the result is a std::pair<int> in C++ terms.
John
--
John Harris
Andrew Koenig
news:du86uc$4rd$1...@news.xmission.com...
>Hell, even:
>
> a*b*c == c*b*a
>
> isn't guaranteed to hold, and I'm not even sure you're allowed to rely on:
>
> a*b == b*a
You are in IEEE floating-point, and also in every floating-point system I've
ever used.
Note that I haven't used the CDC 6600, which tended to be sloppy about such
details.
Nevertheless, I would be surprised to find any floating-point hardware in
widespread use
today in which addition and multiplication are not commutative.
Thant Tessman
[...]
> Discrete math and real math both use infinite sets of
> numbers, so there's no way any computer can possibly
> represent all of the possibilities from either set. In
> this sense, floating point math and integer math are
> categorically identical.
A rational number can be represented exactly given enough memory. An
irrational number can't (except symbolically) no matter how much memory
you have. This is the categorical difference to which I was referring.
Of course it's true that we can't evaluate *every* equation involving
*rational* numbers (because our time and space is limited), but there is
*no* problem involving irrational numbers that can be solved numerically
without giving up precision. The difference is between being able to
solve *some* problems with complete accuracy and being able to solve
*no* problems with complete accuracy. See the difference?
-thant
John G Harris
<fra...@robinton.demon.co.uk> writes
>In article <JQfU4pKR...@jgharris.demon.co.uk>, John G Harris
><ne...@nospam.demon.co.uk> writes
>>A nine-year old would think it means quotient zero, remainder 1.
>>
>>A 16-year old would think it means 0.33333333333333333... .
>
>And both would be only partially correct. As the first chapter of
>Bentley's Programming Pearls points out, before answering a question you
>should enquire why the querient needs an answer. Because only then can
>you reliably help.
Which is what I said in the bit you snipped.
John
--
John Harris
Jerry Coffin
a...@standarddeviance.com says...
[ ... ]
> An IEEE number is not useful because it has an exact value. An IEEE
> number is useful only because the exact value it does have is a useful
> approximation of some real number. I still don't understand how this can
> be considered a controversial statement.
It can be considered controversial because it's wrong. An
IEEE floating point number can be useful for holding
precise values. First of all, with restrictions on the
real numbers you represent, you can be certain the
numbers are represented exactly.
Second, IEEE floating point is often useful for
representing integers. On many C and C++ implementation
the built-in type that supports the widest range of
integers is a floating point type. For one example of
putting this to use, see factor.c at snippets.org.
--
Later,
Jerry.
The universe is a figment of its own imagination.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Jerry Coffin
a...@standarddeviance.com says...
[ ... ]
> Remember, this whole thread was about the ability to compare values for
> equality. I suggest that any attempt to pin down the meaning of equality
> is doomed without some kind of understanding of exactness--an
> understanding of exactness that is *not* captured by floating-point
> math.
Here's the real crux of the matter. You're trying to
define equality in a way that most people never need,
want or care about. Floating point is used primarily to
represent measurements. If you want to measure equality
based on an understanding of exactness, then the answer
to the original question becomes trivial:
bool isEqual(whatever, whatever) { return false; }
This is, of course, utterly useless in practice for the
simple reason that most people most of the time simply
don't want to know about _exactly_ equal -- they care
about things being equal to some level of tolerance
(which is often only implied). Floating point that
supports 15 to 20 digits of precision is often FAR more
than people need, want, or care about -- in particular,
it typically maintains all the precision that was present
in the original measurements, and anything beyond that is
utterly superfluous.
Now, it is possible that the OP was/is using floating
point in an inapplicable situation. If what you really
want is oriented toward counting rather than measuring,
then you _might_ be better off with integer math -- but
even that's not entirely a given. Just for example,
consider that there's a range within which double's can
represent integers precisely -- and that range is often
larger than for any explicitly integer type on the same
implementation.
[ ... ]
> I would have thought this was a pretty simple point to make, and lack of
> "exactness" would seem to be a pretty appropriate word to describe why
> it is that floating-point numbers don't satisfy these conditions and
> integers do, but programming in C or C++ for too long can apparently
> really screw up people's thinking on the topic.
If you think all comparisons should be exact, you're
clearly the one spending too much time at the computer.
I'd suggest a trip to your local bar to get a reminder of
what the real world is like. As a bit of advice, if a
woman gives you her phone number, please god don't try to
exceed the limits of a double in telling her how soon
you're going to call...
--
Later,
Jerry.
The universe is a figment of its own imagination.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Seungbeom Kim
>
> For some unspecified meaning of "exact values". The only useful meaning
> of that term is values that can be represented exactly in the floating
> point representation being used. With a decimal floating-point
> representation, 0.1 can be represented exactly. Integers have similar
> (although simpler) problems:
>
> unsinged int i = 65536
> printf("%u\n", i);
>
> The value displayed by the call to printf (as well as the value held in
> i) depends on the precision of the integer type.
We don't call that the "precision" of an integer type; it's the "range".
Precision means how close an approximation can get to the true value it
tries to approximate; in other words, how fine grids we have.
For integers, there's no approximation; either it's in range and
representable exactly, or out of range and not representable.
> On many systems it will be 65536. On others it will be 0.
That's simply because conversion to an unsigned integer type is defined
as an modulo operation. For a signed integer type, if the result goes
out of range we say an overflow occurred, but it's a little weird to say
it was not precise enough or it didn't have enough precision.
>> 1 multiplied by 9 equals 9 exactly for integer values,
>
> And 32768+32768 may or many not equal 65536 exactly for integer values.
--
Seungbeom Kim
Thant Tessman
> In article <du9qd8$6qo$1...@news.xmission.com>,
> a...@standarddeviance.com says...
>
> [ ... ]
>
>
>>An IEEE number is not useful because it has an exact value. An IEEE
>>number is useful only because the exact value it does have is a useful
>>approximation of some real number. I still don't understand how this can
>>be considered a controversial statement.
>
>
> It can be considered controversial because it's wrong. An
> IEEE floating point number can be useful for holding
> precise values. First of all, with restrictions on the
> real numbers you represent, you can be certain the
> numbers are represented exactly.
The kind of numbers I use floating-point math to represent are things
like sqrt(2) and cos(pi/6). You can be certain that these numbers are
*not* represented exactly. Yes, sometimes floating-point operations
won't lose precision, but that's not what they were designed for.
Elsewhere:
> If you think all comparisons should be exact, you're
> clearly the one spending too much time at the computer.
I have *never* said that all comparisons should be exact. I have merely
tried to point out that there is a valid notion of exactness that isn't
captured by IEEE floating-point numbers (because they were never
designed to do that). I brought up cryptology before. In that situation,
I want to know that two numbers are equal with *far* more precision than
the 15 or 20 digits supported by floating-point math. In fact, I want to
know *exactly* whether they are equal or not. And when I'm doing math
symbolically, I certainly do care about the fact that cos(pi/6) is
*exactly* equal to sqrt(3)/2 for example. It's not that people use
floating-point math because they don't care about exactness. It's that
when people don't care about exactness, they use floating-point math.
[...]
-thant
Francis Glassborow
wa...@stoner.com writes
>Francis Glassborow wrote:
>> In article <1141318337.4...@z34g2000cwc.googlegroups.com>,
>> wa...@stoner.com writes
>> >This might be better or worse in terms of game play. However it has
>> >the advantage that
>> > a < b && b < c
>> >guarantees
>> > a < c
>> >and in many contexts that is useful. If your equivalence classes (and
>> >other relations) are not transitive, you will see existing algorithms
>> >(std::sort) crash.
>>
>> Would you care to give a single example where your assertion holds
>
>My assertion that std::sort will crash is based on 25.3/3, which I
>believe says that if the comparison function is not a strict weak
>ordering the behavior is undefined (of course that might not be a
>crash, but it will be if you are lucky).
And I assert that '<' applied to a built-in floating point type in C++
does induce a strict ordering.
>
>My assertion that introducing epsilon can induce a circular-less-than
> a<b && b<c && c<a
>is shown by example in my reply to JC (assuming that makes it past the
>moderator).
Well I have not seen that post, but I am pretty confident that any such
example is necessarily flawed.
a<b => b-a = d1 where d1 is positive
b<c => c-b = d2 where d2 is positive
c-a = (c - b) + (b - a);
= d2 + d1;
=> a < c;
Now I know that in computer terms some of the subtractions and the
addition only provide approximate answers, however for both floating
point and signed integer types (where overflow is undefined behaviour)
there is AFAIK, no way in which the sum of two positive values however
small (or large) will result in a negative value.
If you know better, provide an example.
--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects
Francis Glassborow
wa...@stoner.com writes
>Assuming this implementation of "equal"
> bool equal(double x, double y)
> {
> const double epsilon = 0.5;
> return abs(x-y)<epsilon;
> }
>
>Given:
>
>ResourceInfo a = { 1.3, 1 };
>ResourceInfo b = { 1, 2 };
>ResourceInfo c = { 0.7, 3 };
>
>You get
> a < b // equal(a.priority,b.priority) && a.price < b.price
> b < c // equal(b.priority,c.priority) && b.price < c.price
> c < a // !equal(c.priority,a.priority) && c.priority <
>a.priority
And most of us know that if there are TWO criteria that you can get
circular cases, but now you are not comparing floating point values but
something else which includes a pair of doubles.
--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects
Matthias Hofmann
news:8puA0QOf...@robinton.demon.co.uk...
> In article <1141392477.4...@j33g2000cwa.googlegroups.com>,
> wa...@stoner.com writes
> >Assuming this implementation of "equal"
> > bool equal(double x, double y)
> > {
> > const double epsilon = 0.5;
> > return abs(x-y)<epsilon;
> > }
> >
> >Given:
> >
> >ResourceInfo a = { 1.3, 1 };
> >ResourceInfo b = { 1, 2 };
> >ResourceInfo c = { 0.7, 3 };
> >
> >You get
> > a < b // equal(a.priority,b.priority) && a.price < b.price
> > b < c // equal(b.priority,c.priority) && b.price < c.price
> > c < a // !equal(c.priority,a.priority) && c.priority <
> >a.priority
>
>
> And most of us know that if there are TWO criteria that you can get
> circular cases, but now you are not comparing floating point values but
> something else which includes a pair of doubles.
You made me nervous... But I have verified that this circular case cannot
lead to an endless loop in my implementation of the sorting algorithm.
However, wa...@stoner.com is right in as much as the sorting may depend on
the order in which the elements are processed.
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Matthias Hofmann
news:MPG.1e72369a9...@news.sunsite.dk...
> Just for example,
> consider that there's a range within which double's can
> represent integers precisely -- and that range is often
> larger than for any explicitly integer type on the same
> implementation.
This is exactly - you know what I mean ;-) - the case in my algorithm: I am
using a sum of integers, and the sum may, in rare cases, exceed the range of
an integer. That's why I store the sum in a double.
By the way, while I was writing this post I noticed a mistake in my source
code:
unsigned long a, b, c;
...
double total = a + b + c;
As far as I know C++, the expression "a + b + c" will not be promoted to
type double until the assignment. Therefore, I might still get an overflow.
I have now changed the type of a, b and c to double, in order to prevent
that problem.
Someone mentioned boost::rational in another post of this thread. I was just
wondering wether it uses double internally to represent the numerator and
denominator in order to make possible a larger range of representable
values. What I found is the following, which provides interesting
information about the precision of such a class:
http://www.boost.org/libs/rational/rational.html#Limited-range%20integer%20t
ypes
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Jerry Coffin
a...@standarddeviance.com says...
[ ... ]
> A rational number can be represented exactly given enough memory. An
> irrational number can't (except symbolically) no matter how much memory
> you have. This is the categorical difference to which I was referring.
> Of course it's true that we can't evaluate *every* equation involving
> *rational* numbers (because our time and space is limited), but there is
> *no* problem involving irrational numbers that can be solved numerically
> without giving up precision. The difference is between being able to
> solve *some* problems with complete accuracy and being able to solve
> *no* problems with complete accuracy. See the difference?
No, because there is no difference.
In floating point, you can represent some, but not all,
rational numbers exactly.
In a rational class, you can represent some, but not all,
rational numbers exactly.
Some, but not all, problems can be solved with perfect
accuracy using floating point.
Some, but not all, problems can be solved with perfect
accuracy using rationals.
What we have here is clearly not a qualitative difference
but a quantitative one. Both can do some things
perfectly, but neither can do anywhere close to all of
them perfectly.
BTW, you're also incorrect about irrational numbers
requiring a symbolic represented perfectly in a finite
amount of memory. Consider the way we represented
rational numbers as repeating decimals back in school
(warning: fixed-width font needed for things to line up
below):
_
1 1/3 = 1.3
At least for the moment, I'm going to assume that you'll
accept that as being a numeric rather than symbolic
representation. I realize it's not how a rational class
is typically written, but I think you'll agree that it's
one possible way of doing things, and that it really is
numeric rather than symbolic, true?
Using continued fractions, we can do the same thing with
many irrational numbers. The difference is that instead
of representing a repeating decimal, we represent a
repeating pattern in the continued fraction. For a well
known example from Knuth, the square root of 8/29, could
be represented as:
___________________
1 1 9 2 2 3 2 2 9 1 2
where the bar now represents a repeating pattern in the
continued fraction rather than a repeating decimal.
Given the importance you seem to attach to representing
as many numbers as possible exactly, this seems far
superior to any possible rational class.
In case you feel like studying continued fractions a bit
more, I think _Concrete Mathematics_ (by Graham, Knuth
and Patashnik) covers them quite nicely. TAOCP II has a
bit about them as well, but it mostly restricts itself to
what's relevant in analyzing Euclid's algorithm. Of
course, there are quite a few more references as well...
--
Later,
Jerry.
The universe is a figment of its own imagination.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Dilip
> In case you feel like studying continued fractions a bit
> more, I think _Concrete Mathematics_ (by Graham, Knuth
> and Patashnik) covers them quite nicely.
India's very own Srinivasa Ramanujan[1] did plenty of research on
Continued Fractions.
Sorry moderator -- I couldn't resist. Couldn't help mention with pride
a fellow country man's contribution. Feel free to ignore this post if
I am violating posting etiquette.
{Just do not make a habit of it, and learn the trick of inserting
something about C++ into such posts. -mod}
[1]
http://www-history.mcs.st-andrews.ac.uk/~history/Mathematicians/Ramanujan.html
Thant Tessman
[...]
> BTW, you're also incorrect about irrational numbers
> requiring a symbolic represented perfectly in a finite
> amount of memory. Consider the way we represented
> rational numbers as repeating decimals back in school
> (warning: fixed-width font needed for things to line up
> below):
> _
> 1 1/3 = 1.3
>
> At least for the moment, I'm going to assume that you'll
> accept that as being a numeric rather than symbolic
> representation. I realize it's not how a rational class
> is typically written, but I think you'll agree that it's
> one possible way of doing things, and that it really is
> numeric rather than symbolic, true?
I would have called this symbolic--along with continued fractions and
indeed any representation that has an explicit or imlied "..." in it. My
use of the term "symbolic" was an attempt to explicitly account for
exactly these kinds of solutions in the arguments I've been making. But
whether you want to call this kind of representation numeric or symbolic
is really beside the point. I only brought up "symbolic" representations
of numbers to emphasize that sometimes we do expect an answer with some
qality of "exactness" that floating-point numbers were never designed to
give us EVEN THOUGH floating-point numbers are regularly expected to
give us an answer that is useful. Ironically, in bringing up continued
fractions you demonstrate that even you really do understand this
difference.
As I said, the utility of floating-point numbers derives from the fact
that the "exact" values they do represent are a useful approximation of
some real number. Sometimes this exact value that a floating-point
number has just happens to be spot on. And maybe even in some hardware
implementations, more bits will be spent on a double's significand than
are spent on the native int type. But that's *not* what they were
designed for. They were designed to efficiently approximate the behavior
of real numbers AT THE EXPENSE of exactness. Anyone who programs using
C++ and needs big, exact integers really should build their own integer
type with the range they need. If they need a decimal type with very
specific rounding properties for accounting, they should build it. Et
cetera and so on. This is one of the few things C++ is genuinely good at.
[...]
> Given the importance you seem to attach to representing
> as many numbers as possible exactly, this seems far
> superior to any possible rational class.
I recently had occasion to do 3D graphics using a fixed point number
type. Tricky, but not at all impractical. "Representing as many numbers
as possible exactly" was *never* the important point. Knowing and
acknowledging the difference between an exact and an inexact calculation
was.
-thant
--
Those who kill people with car bombs are "terrorists"; those who kill
far more people with cluster bombs are the noble occupants of a
"quagmire." -- John Pilger
Matthias Hofmann
> In a rational class, you can represent some, but not all,
> rational numbers exactly.
Why? Because of the limited range of the numerator and the denominator? This
is a question of memory. Of course there is no such thing as unlimited
memory in theory, but in practice, you will get enough memory for the
numerator and the denominator of a rational class to be so large that it
won't fit on any piece of paper.
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
kwikius
> Someone mentioned boost::rational in another post of this thread. I was just
> wondering wether it uses double internally to represent the numerator and
> denominator in order to make possible a larger range of representable
> values. What I found is the following, which provides interesting
> information about the precision of such a class:
>
> http://www.boost.org/libs/rational/rational.html#Limited-range%20integer%20t
> ypes
FWIW boost::rational is designed for exact arithmetic on a limited
range rather than inexact arithmetic on an unlimited range
The maximum safe continuous range value of values -n : n for the
numerator or denominator that allow all operations(+-*/) notably
excluding pow to be carried out safely ,where integer_max is the max
positive value for the given integer_type of the rational is I think:
abs(n)
=static_cast<int>(
sqrt(static_cast<double>(std::numeric_limits<integer_type>::max())) / 4
);
where abs(n) works out at 11585 for a 32 bit int and 45 for a 16 bit
int. Not much range really!
regards
Andy Little
Jerry Coffin
online.net>, hof...@anvil-soft.com says...
> "Jerry Coffin" <jco...@taeus.com> schrieb im Newsbeitrag
> news:MPG.1e76117ca...@news.sunsite.dk...
>
> > In a rational class, you can represent some, but not all,
> > rational numbers exactly.
>
> Why? Because of the limited range of the numerator and the denominator? This
> is a question of memory. Of course there is no such thing as unlimited
> memory in theory, but in practice, you will get enough memory for the
> numerator and the denominator of a rational class to be so large that it
> won't fit on any piece of paper.
Sure -- you'll have plenty of memory to store the vast
majority of numbers you care about. OTOH, if you read
_Surreal Numbers_ (Knuth, yet again) you'll be reminded
that there are an awful lot of really big numbers out
there. I don't expect to own a computer anytime soon that
has enough memory to represent Super K directly in
rational form.
We can represent many numbers exactly. In fact, we can
represent far more numbers exactly than almost anybody
cares about. At the same time, as a percentage of all
rational numbers, it works out to precisely zero.
>From a practical viewpoint, it's far more than most
people ever care about, but from a theoretical viewpoint,
it's none at all. And exactly the same is true of
floating point numbers.
--
Later,
Jerry.
The universe is a figment of its own imagination.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]