Floating-point precision in Tcl 8.0
John Ousterhout
About a month ago there was a discussion about how floating-point precision
should be handled in Tcl 8.0, triggered by an article from George Howlett
suggesting that the 8.0 beta releases have too much precision, resulting in
counter-intuitive results. In this message I'm going to describe what we've
decided to do for the final 8.0 release. If there is some fatal flaw with
this scheme that hasn't already been discussed, please let me know ASAP;
otherwise what you see below will be in the release.
1. When the value of a floating-point object is converted back to a
string, only 12 digits will be used instead of 17 as in the beta releases.
This will result in rounding, so that 1.4 will appear as 1.4, not
1.3999999999999999. The choice of 12 digits is a compromise: a smaller
number of digits would lose more information, but a larger number of
digits means that accumulated rounding error during arithmetic could
cause the value not to print cleanly. If you want to get the full 17
digits of precision, you'll have to use "format %.17g" instead of using
the implicit object conversion. However, in Tcl 8.0 it's likely that the
format command won't have been converted to an object command yet, so this
approach may not be available until Tcl 8.1.
For comparison, Tcl 7.6 printed only 6 digits by default, but you could set
the variable tcl_precision to request more digits. The tcl_precision
variable isn't supported anymore in Tcl 8.0. Thus the default behavior
of Tcl 8.0 is better than the default in Tcl 7.6 but it will be more work
in Tcl 8.0 to get "full precision" than in Tcl 7.6.
2. The comparison operators in expressions (==, !=, <, >, <=, and >=)
use "fuzzy comparison" for floating-point numbers. This means that two
numbers are considered to be equal they are within 1 part in 1.0e-12 of
each other. More precisely, a and b are considered equal if
(abs(a-b)/(abs(a) + abs(b)) < .5e-12
This means, for example, that 8.0 >= 8.00000000000001. This approach
means that code like the following loop does what you'd expect:
for {set x .1} {$x < 1.4} {set x [expr $x + .1]} {...}
If you want a full-precision comparison, you can get it by reorganizing
the expression to compare against 0. For example, instead of
if {$x < 1.4} ...
say instead
if {($x - 1.4) < 0} ...
Comparisons against 0 are always exact, by definition from the above formula.
With this approach, Tcl 8.0 will have default behavior that's more precise
than Tcl 7.6, but you'll have to do extra work to get "full" precision: you
can't just set the tcl_precision variable.
We hope that the combination of these two techniques will provide
(a) behavior that is intuitive to people who aren't floating-point experts,
(b) a reasonable default level of precision (better than Tcl 7.6),
(c) escapes that can be used to get full precision where it is needed.
Peter.DeRijk
Viktor Dukhovni (vik...@yoyodyne.ics.uci.edu) wrote:
: In <5sa9j7$hio$1...@engnews2.Eng.Sun.COM> ous...@tcl.eng.sun.com (John Ousterhout) writes:
: >About a month ago there was a discussion about how floating-point precision
: >should be handled in Tcl 8.0, triggered by an article from George Howlett
: >suggesting that the 8.0 beta releases have too much precision, resulting in
: >counter-intuitive results. In this message I'm going to describe what we've
: >decided to do for the final 8.0 release. If there is some fatal flaw with
: >this scheme that hasn't already been discussed, please let me know ASAP;
: >otherwise what you see below will be in the release.
: In the ensuing discussion, someone posted references to papers
: on printing and scanning floating point numbers. The summary was
: that one print floating numbers in such a way that "expr 1.1" returns the
: expected result, with no loss of precision, because the printed value
: is equal to the default output of "1.1000000000000001" with no loss of
: precision. The suggested approach solves the problem with mangling
: of text widget line.pos indices by expr, reported on this group, results
: in intuitive output, and has sensible semantics.
: As for rounding errors, anyone expecting fixed point semantics
: from floating point numbers is the author of buggy code, there is no cure
: for imprecision of floating point numbers. The proposed semantics break
: the carefully designed IEEE standard, resulting in surprising behaviour
: and inconsistent results from "string" vs. "object" implementations of
: commands (as noted by Mark Diekhans), and inconsistent results for
: mathematically equivalent expressions (e.g. x == y iff (x-y) == 0).
: Also "string" implementations of floating point functions will necessarily
: incur round off errors at the 12th significant digit, again easily
: accumulating to "unexpected" errors in with point computations.
: .....
Here we are starting the discussion again. Tcl is intended to be a
(very) high level scripting. 99% of the people using Tcl do not care
about the 12th or 17th significant digit. They do want
% expr 1.1+1
to produce 2.1 as a result, and not 2.1000000000000001.
The 2.1000000000000001 as a result is only comprehensible by someone
who knows about the internal representation of floating point numbers
in computers on a very low level. Being a very high level language, Tcl should
to hide these things. For the level at which Tcl is intended (and mostly used)
2.1000000000000001 is a wrong result.
Peter De Rijk
--
Peter De Rijk der...@uia.ua.ac.be
<a href="http://rrna.uia.ac.be/~peter/personal/peter.html">Peter</a>
To achieve the impossible, one must think the absurd.
to look where everyone else has looked, but to see what no one else has seen.
Martin Shepherd
der...@hgins.uia.ac.be (Peter.DeRijk) writes:
> Here we are starting the discussion again. Tcl is intended to be a
> (very) high level scripting.
TCL means different things to different people. I personally use it as
a user-interface glue language for C programs. My C code involves a
lot of floating point arithmetic, so I am very put off by the idea
that we will now loose precision to tacky glue. For example, if Tcl8.0
does get kludged as reported, I won't be able to safely check the
validity of floating point arguments in Tcl before passing them to the
C layer.
In addition to this, I think that the idea of hand-holding naive users
such that they learn to ignore cumulative rounding errors is seriously
flawed. At some point the approximations will break down and they
won't know what to do. Mungala Raman has already spelled out the
dangers of this better than I can, so I'll just say that I concur with
his arguments.
A way to pacify both camps has been suggested before, one that
involves rendering the textual representation with the least number of
significant digits that when read back reproduces the original binary
representation. This preserves precision while yielding human readable
numbers where possible.
Martin Shepherd (m...@astro.caltech.edu)
Paul Eggert
der...@hgins.uia.ac.be (Peter.DeRijk) writes:
> 99% of the people using Tcl do not care about the 12th or 17th significant
> digit. They do want
> % expr 1.1+1
> to produce 2.1 as a result, and not 2.1000000000000001.
But my proposal addressed that problem. Here it is again:
When converting a double value to a string,
convert to the smallest number of digits such that
converting back to double yields the original value again.
Under this proposal, 1.1+1 _does_ print 2.1.
So far, nobody has presented any technical criticism of this proposal,
and yet John Ousterhout seems to be going with another method that has
some severe numerical problems. I'm puzzled as to why this more
numerically honest approach wasn't taken.
Junio Hamano
egg...@twinsun.com (Paul Eggert) writes:
> But my proposal addressed that problem. Here it is again:
>
> When converting a double value to a string,
> convert to the smallest number of digits such that
> converting back to double yields the original value again.
>
> Under this proposal, 1.1+1 _does_ print 2.1.
>
> So far, nobody has presented any technical criticism of this proposal,
> and yet John Ousterhout seems to be going with another method that has
> some severe numerical problems. I'm puzzled as to why this more
> numerically honest approach wasn't taken.
One technical criticism I can imagine somebody would come up
with against this proposal is that it is expensive to implement
it. I did a little measurement and found out that a naive
implementation of the proposal by Paul Eggert takes about as 1.4
times as long, compared to the numerically correct (i.e. always
use %.17g) version, and as 2.8 times as long compared to the
compromised (i.e. use %.12g, sacrificing precision) version
proposed by John Ousterhout. At the same time, John
Ousterhout's proposal includes a more expensive (in addition to
being sometimes incorrect) implementation of comparison
operations, which by my measurement takes as 2.2 times as long
compared to the numerically correct (i.e. exact floating point
comparison) version. The code and its output is attached to the
end of this message. The measurement was done on Sun Ultra 1
(143MHz) running SunOS 5.5.1, with `gcc -O'.
Since the beauty of object interface in Tcl 8.0 is to keep
operations efficient when they are applied to the natural
representation of objects, I think making double->string
conversion 1.4 times (even 2.8 times) more expensive is fairly
small price to pay in order to keep the arithmetic comparison
operator from becoming 2.2 times more expensive. Use of many
comparisons inside of a loop would be legitimate, but one should
not be keep doing double to string conversion over and over in a
loop, unless the conversion is used for output, in which case
conversion performance does not matter anymore.
If we consider the correctness, the argument to favor the
``%.12g plus fuzzy comparison'' proposal becomes even weaker. I
hope Tcl core team would reconsider John Ousterhout's decision.
#!/bin/sh
cat <<\EOF >Makefile
# Tcl_PrintDouble and fuzzy comparison performance demonstration
# $Id: Makefile,v 1.1 1997/08/08 06:02:41 junio Exp $
CC= gcc
CFLAGS= -g -O -Wall -ansi -pedantic -Wall -W -Wtraditional -Wid-clash-31
I= -I.
u= rm -f $@ &&
x= >$@ || { rm -f $@; exit 1; }
default:: float fuzzy
uname -a
time ./fuzzy 0
time ./fuzzy 1
time ./float 0
time ./float 1
time ./float 2
./float 3
install:: default
clean::
rm -f *.[aos] *~ core a.out fuzzy float
.c.o:
$(CC) $I $(CFLAGS) -c $<
EOF
cat <<\EOF >float.c
/* Tcl_PrintDouble Performance Comparison */
/* $Id: float.c,v 1.1 1997/08/08 06:02:24 junio Exp $ */
#include <stdio.h>
#define UCHAR(c) ((unsigned char) (c))
#include <ctype.h>
/* The version in tcl8.0b2 */
void
Tcl_PrintDouble_0 (double value, char *dst)
{
register char *p;
sprintf(dst, "%.17g", value);
/*
* If the ASCII result looks like an integer, add ".0" so that it
* doesn't look like an integer anymore. This prevents floating-point
* values from being converted to integers unintentionally.
*/
for (p = dst; *p != 0; p++) {
if ((*p == '.') || (isalpha( UCHAR (*p)))) {
return;
}
}
p[0] = '.';
p[1] = '0';
p[2] = 0;
}
/* The version proposed by JO for tcl8.0 */
void
Tcl_PrintDouble_1 (double value, char *dst)
{
register char *p;
sprintf(dst, "%.12g", value);
/*
* If the ASCII result looks like an integer, add ".0" so that it
* doesn't look like an integer anymore. This prevents floating-point
* values from being converted to integers unintentionally.
*/
for (p = dst; *p != 0; p++) {
if ((*p == '.') || (isalpha( UCHAR (*p)))) {
return;
}
}
p[0] = '.';
p[1] = '0';
p[2] = 0;
}
/* The version proposed by PRE */
void
Tcl_PrintDouble_2 (double value, char *dst)
{
register char *p;
double test;
sprintf(dst, "%.15g", value);
sscanf (dst, "%lf", &test);
if (test != value) {
sprintf(dst, "%.16g", value);
sscanf (dst, "%lf", &test);
if (test != value)
sprintf(dst, "%.17g", value);
}
/*
* If the ASCII result looks like an integer, add ".0" so that it
* doesn't look like an integer anymore. This prevents floating-point
* values from being converted to integers unintentionally.
*/
for (p = dst; *p != 0; p++) {
if ((*p == '.') || (isalpha( UCHAR (*p)))) {
return;
}
}
p[0] = '.';
p[1] = '0';
p[2] = 0;
}
/* Statistics and correctness for Tcl_PrintDouble_2 */
int count15 = 0;
int count16 = 0;
int count17 = 0;
void
Tcl_PrintDouble_3 (double value, char *dst)
{
register char *p;
double test;
char ouster[20];
int which;
sprintf (ouster, "%.12g", value);
sprintf(dst, "%.15g", value);
sscanf (dst, "%lf", &test);
if (test != value) {
sprintf(dst, "%.16g", value);
sscanf (dst, "%lf", &test);
if (test != value) {
which = 17;
count17++;
sprintf(dst, "%.17g", value);
sscanf (dst, "%lf", &test);
} else {
which = 16;
count16++;
}
} else {
which = 15;
count15++;
}
if (strcmp (dst, ouster))
printf ("%d: %s %s\n", which, dst, ouster);
/*
* If the ASCII result looks like an integer, add ".0" so that it
* doesn't look like an integer anymore. This prevents floating-point
* values from being converted to integers unintentionally.
*/
for (p = dst; *p != 0; p++) {
if ((*p == '.') || (isalpha( UCHAR (*p)))) {
return;
}
}
p[0] = '.';
p[1] = '0';
p[2] = 0;
}
int
main (int ac, char **av)
{
void (*pdfunc)(double, char *) = 0;
char buf[128];
double val, dbase;
int count, limit, base;
if ((ac != 2) || (av[1][0] < '0') || ('3' < av[1][0])) {
fprintf (stderr, "usage: %s [0|1|2|3]\n", av[0]);
exit (1);
}
limit = 10000;
switch (av[1][0]) {
case '0': pdfunc = Tcl_PrintDouble_0; break;
case '1': pdfunc = Tcl_PrintDouble_1; break;
case '2': pdfunc = Tcl_PrintDouble_2; break;
case '3': pdfunc = Tcl_PrintDouble_3; limit = 10; break;
}
for (base = 0, dbase = 1; base < 17; base++, dbase *= 10.0) {
for (count = 0; count < limit; count++) {
val = dbase + (double) count / (double) limit;
(*pdfunc) (val, buf);
}
}
if (av[1][0] == '3') {
printf ("15 %d (%.2f%%), 16 %d (%.2f%%), 17 %d (%.2f%%)\n",
count15, 100.0 * count15 / (count15+count16+count17),
count16, 100.0 * count16 / (count15+count16+count17),
count17, 100.0 * count17 / (count15+count16+count17));
}
exit (0);
}
EOF
cat <<\EOF >fuzzy.c
/* Fuzzy comparison performance demonstration */
/* $Id: fuzzy.c,v 1.1 1997/08/08 06:02:56 junio Exp $ */
#include <stdio.h>
/* The version proposed by JO for tcl8.0 */
int
compare_fuzzy (double a, double b)
{
return abs (a-b) / (abs (a) + abs (b)) < .5e-12;
}
/* Traditional version */
int
compare_exact (double a, double b)
{
return a == b;
}
int
main (int ac, char **av)
{
int (*compare)(double, double) = 0;
double val, dbase;
int count, limit, base;
if ((ac != 2) || (av[1][0] < '0') || ('1' < av[1][0])) {
fprintf (stderr, "usage: %s [0|1]\n", av[0]);
exit (1);
}
limit = 100000;
switch (av[1][0]) {
case '0':
compare = compare_fuzzy; break;
case '1':
compare = compare_exact; break;
}
for (base = 0, dbase = 1.0; base < 17; base++, dbase *= 10.0) {
for (count = 0; count < limit; count++) {
val = dbase + (double) count / limit;
(*compare) (val, val);
}
}
exit (0);
}
EOF
cat <<\EOF >make.out
uname -a
SunOS dew 5.5.1 Generic_103640-08 sun4u sparc SUNW,Ultra-1
time ./fuzzy 0
real 2.4
user 2.4
sys 0.0
time ./fuzzy 1
real 1.1
user 1.1
sys 0.0
time ./float 0
real 9.6
user 9.5
sys 0.0
time ./float 1
real 4.7
user 4.7
sys 0.0
time ./float 2
real 13.3
user 13.2
sys 0.0
./float 3
15: 100000000000.1 100000000000
15: 100000000000.2 100000000000
15: 100000000000.3 100000000000
15: 100000000000.4 100000000000
15: 100000000000.5 100000000000
15: 100000000000.6 100000000001
15: 100000000000.7 100000000001
15: 100000000000.8 100000000001
15: 100000000000.9 100000000001
15: 1000000000000 1e+12
15: 1000000000000.1 1e+12
15: 1000000000000.2 1e+12
15: 1000000000000.3 1e+12
15: 1000000000000.4 1e+12
15: 1000000000000.5 1e+12
15: 1000000000000.6 1e+12
15: 1000000000000.7 1e+12
15: 1000000000000.8 1e+12
15: 1000000000000.9 1e+12
15: 10000000000000 1e+13
15: 10000000000000.1 1e+13
15: 10000000000000.2 1e+13
15: 10000000000000.3 1e+13
15: 10000000000000.4 1e+13
15: 10000000000000.5 1e+13
15: 10000000000000.6 1e+13
15: 10000000000000.7 1e+13
15: 10000000000000.8 1e+13
15: 10000000000000.9 1e+13
15: 100000000000000 1e+14
16: 100000000000000.1 1e+14
16: 100000000000000.2 1e+14
16: 100000000000000.3 1e+14
16: 100000000000000.4 1e+14
16: 100000000000000.5 1e+14
16: 100000000000000.6 1e+14
16: 100000000000000.7 1e+14
16: 100000000000000.8 1e+14
16: 100000000000000.9 1e+14
17: 1000000000000000.1 1e+15
17: 1000000000000000.2 1e+15
17: 1000000000000000.2 1e+15
17: 1000000000000000.4 1e+15
17: 1000000000000000.5 1e+15
17: 1000000000000000.6 1e+15
17: 1000000000000000.8 1e+15
17: 1000000000000000.8 1e+15
17: 1000000000000000.9 1e+15
15 152 (89.41%), 16 9 (5.29%), 17 9 (5.29%)
EOF
John Ousterhout
In article <ramEEI...@netcom.com>, r...@netcom.com (Munagala V. S. Ramanath) writes:
|> ...
|>
|> This appears to be a bad idea because it destroys the idea, firmly
|> embedded in most programmers minds from years of experience with a
|> wide variety of programming languages, that == is an equivalence
|> relation.
|>
|> With this fuzziness, it is no longer transitive: a==b, b==c but
|> we could well have a != c. Similarly, the reasonable expectation
|> that <= and >= are partial orders is undercut since we may have
|> a <= b and b <= c but a > c.
|>
|> In short, it wreaks havoc with commonly understood guarantees and
|> invites far more bugs which will be _very_ difficult to find.
I'm afraid the properties you long for never existed in the first place.
Basic laws of mathematics are already broken in any floating-point
implementation, due to the fixed precision available and the resulting
roundoff errors. For example, (1.4 + 0.7 - 0.6 - 0.1) won't necessarily
equal 1.4 under normal floating-point arithmetic. This seems to contradict
the basic laws of mathematics! Any floating-point system will suffer from
some surprises like this; our goal for Tcl 8.0 is to avoid surprises in
the simple cases. The Tcl 8.0 approach actually makes many things (such as
the example above) behave more intuitively than they would with "precise"
arithmetic.
One way to think about what we've done is that we've taken the least
significant 12 bits of floating-point numbers and turned them into guard
bits. They aren't visible when you print floating-point numbers or when
you compare them, but they participate in all internal calculations. In
this sense they are better than the guard bits kept in hardware, which
are fewer in number and have shorter lifetimes. In the worst case, the
Tcl 8.0 approach is as good as a floating-point system with 12 decimal
digits of precision (somewhere between single and double precision), but
expert programmers can get even more precision out if they want.
John Ousterhout
In article <5sagvd$5...@yoyodyne.ics.uci.edu>, vik...@yoyodyne.ics.uci.edu (Viktor Dukhovni) writes:
|> ...
|>
|> In the ensuing discussion, someone posted references to papers
|> on printing and scanning floating point numbers. The summary was
|> that one print floating numbers in such a way that "expr 1.1" returns the
|> expected result, with no loss of precision, because the printed value
|> is equal to the default output of "1.1000000000000001" with no loss of
|> precision. The suggested approach solves the problem with mangling
|> of text widget line.pos indices by expr, reported on this group, results
|> in intuitive output, and has sensible semantics.
We considered this approach and eventually decided against it. The main
problem is its complexity: this gets us into the business of writing
floating-point conversion routines, which is complicated and platform-
specific; it would take months to iron out all of the porting problems. It
also only solves half of the problem: we still need to do something about
floating-point comparison. The approach we chose is more uniform, in that
it uses (roughly) the same precision for conversions and for comparisons.
|> You specifically note that "format" is not yet an "object" command,
|> leading to unavoidable loss of precision in double to string conversion.
Fortunately Bryan Surles found time yesterday to convert "format" to an
object command, so this won't be a problem after all.
Martin Shepherd
ous...@tcl.eng.sun.com (John Ousterhout) writes:
> In article <5sagvd$5...@yoyodyne.ics.uci.edu>, vik...@yoyodyne.ics.uci.edu (Viktor Dukhovni) writes:
> |> ...
> |> In the ensuing discussion, someone posted references to papers
> |> on printing and scanning floating point numbers. The summary was
> |> that one print floating numbers in such a way that "expr 1.1" returns the
> |> expected result, with no loss of precision, because the printed value
> |> is equal to the default output of "1.1000000000000001" with no loss of
> |> precision....
>
> We considered this approach and eventually decided against it. The main
> problem is its complexity: this gets us into the business of writing
> floating-point conversion routines, which is complicated and platform-
> specific; it would take months to iron out all of the porting
> problems.
If my interpretation of the C standard is correct, this has already
been done in advance, so it doesn't require any more work than using
printf("%.17g\n") did.
The following is what the standard says about the definition of the
DBL_DIG macro in float.h:
The number of decimal digits such that any floating-point number
with DBL_DIG decimal digits can be rounded into a floating-point
number with DBL_MANT_DIG radix FLT_RADIX digits and back again
without change to the DBL_DIG decimal digits.
Where "DBL_MANT_DIG radix FLT_RADIX digits" refers to the number of
bits in a double precision variable.
I read this to mean that one can print any double precision number
with as few digits as possible, using:
#include <float.h>
sprintf(buffer, "%.*g\n", (int) DBL_DIG, 1.0/2.5);
and then read the number back using atof(buffer) to recover the
original binary representation.
Note that DBL_DIG is 15 for IEEE-754 doubles, so the reason that Tcl
currently prints ragged looking numbers is simply because the adopted
17 characters is two characters more than is needed. Thus while Tcl
currently prints 1.0/2.5 as:
0.40000000000000002
The above sprintf() results in:
0.4
Using DBL_DIG is portable to machines that don't use IEEE-754 doubles,
whereas the choice of an arbitrary precision such as 12, is always
going to have to represent the most pessimistic case and a
correspondingly unjustifiable loss of binary precision.
For those few systems that still use K&R compilers, you could add
something like the following to tcl8.0/compat/float.h:
#ifndef DBL_DIG
#ifdef ... /* A special case machine that doesn't use IEEE-754 */
#define DBL_DIG ...
#else
#define DBL_DIG 15 /* Assume IEEE-754 doubles */
#endif
I have posted about this once before, so I am curious as to why an
arbitrary precision was still chosen instead of using DBL_DIG. What
does a precision of 12 gain you over using DBL_DIG?
Martin Shepherd (m...@astro.caltech.edu)
Przemek Klosowski
Martin Shepherd <m...@goblin.caltech.edu> writes:
>
> ous...@tcl.eng.sun.com (John Ousterhout) writes:
> > |> on printing and scanning floating point numbers. The summary was
> > |> that one print floating numbers in such a way that "expr 1.1" returns the
> > |> expected result, with no loss of precision, because the printed value
> > |> is equal to the default output of "1.1000000000000001" with no loss of
> > |> precision....
> >
> > We considered this approach and eventually decided against it. The main
> > problem is its complexity: this gets us into the business of writing
>
> If my interpretation of the C standard is correct, this has already
> been done in advance, so it doesn't require any more work than using
> printf("%.17g\n") did.
>
I am not an expert on portability, so I don't know if Martin's proposal is
practical; however, I would like to register my vote against the 12-bit solution.
As I have written before, my favorite would have been an infinite precision/rational
arithmetic ('high level arithmetic for a high level language'); however, I
admit that it may be too much effort to implement.
--
przemek klosowski <prz...@nist.gov> (301) 975-6249
NIST Center for Neutron Research (bldg. 235), E111
National Institute of Standards and Technology
Gaithersburg, MD 20899, USA
Shimpei Yamashita
Martin Shepherd <m...@goblin.caltech.edu> writes:
>der...@hgins.uia.ac.be (Peter.DeRijk) writes:
>> Here we are starting the discussion again. Tcl is intended to be a
>> (very) high level scripting.
>
>TCL means different things to different people. I personally use it as
>a user-interface glue language for C programs. My C code involves a
>lot of floating point arithmetic, so I am very put off by the idea
>that we will now loose precision to tacky glue. For example, if Tcl8.0
>does get kludged as reported, I won't be able to safely check the
>validity of floating point arguments in Tcl before passing them to the
>C layer.
<AOL>Me too!</AOL>
I have to agree with this. Tcl playing games with floating point
accuracy will make it a lot less viable to people who do need
numerical accuracy, particularly in the scientific field.
I'm currently working on a program that uses Tcl as a front end for
managing radio astronomy data. I haven't finished working out the
impact of this decision by the Tcl team on my program, but I can
already see that I would have to "hide" more parts of the program's
internals (i.e. the parts that handle very precise data) from Tcl than
I had planned to, severely reducing the "scriptability" of the
program. I hope it doesn't come down to that.
If Dr. Ousterhout is still convinced that the proposed behavior is
better for the majority of people, would it be at all possible for Tcl
8.0 to support both behaviors, turned on or off by a variable?
--
Shimpei Yamashita <http://www.patnet.caltech.edu/%7Eshimpei/>
Jonathan Cook
I am not a floating-point guru, but this proposal of fuzzy relational
operators seems to be opening a huge Pandora's box of potential
problems. While floating point and its operators are a digital
approximations to continuous numbers, at least they're consistent. I
can, say, sort a sequence of FP numbers and be assured of the
transitive relations. No longer with the proposal below; it
separates the representation (FP) and the relations in a bad way,
especially since all other operators are still operating on
the (FP) representation.
I don't think applying a (somewhat) arbitrary fudge factor of .5e-12
insulates most or even many users from thinking about FP, and the
most it would do is give a false sense of correctness. And it certainly
opens the door to many other problems. To have to fight the language
to get "correct" results (the compare-to-0 out) seems counter-
productive.
JonCook.
Tom Tromey
[ discussion of Paul Eggert's suggested approach to printing FP ]
John> We considered this approach and eventually decided against it.
John> The main problem is its complexity: this gets us into the
John> business of writing floating-point conversion routines, which is
John> complicated and platform- specific; it would take months to iron
John> out all of the porting problems.
I haven't investigated the suggested approach enough to know if this
is true. I will note that if you don't care about performance then
you can do it purely with the standard functions: just take the
initial string repr and chop digits off the end until you find one
that doesn't convert back to double precisely.
I have no real reason to believe a more efficient method couldn't be
found.
Are there systems you care about that don't do IEEE math? If they are
relatively obscure, then let various people on the net champion the
porting process.
John> It also only solves half of the problem: we still need to do
John> something about floating-point comparison. The approach we
John> chose is more uniform, in that it uses (roughly) the same
John> precision for conversions and for comparisons.
I disagree that anything needs to be done about comparison when the
more numerically precise approach is adopted. Why should anything
need to be done? What are the losing cases?
Beyond that, using fuzzy comparisons seems like a bad idea. It's true
that FP numbers aren't real numbers (in the mathematical sense). But
it is also true that the FP numbers are ordered (modulo Inf and NaN).
Fuzzy comparisons destroy this.
Tom
--
tro...@cygnus.com Member, League for Programming Freedom
Heribert Dahms
In <5sff58$e...@gap.cco.caltech.edu> shi...@socrates.caltech.edu writes:
: If Dr. Ousterhout is still convinced that the proposed behavior is
: better for the majority of people, would it be at all possible for Tcl
: 8.0 to support both behaviors, turned on or off by a variable?
I guess no, otherwise we could just keep the tcl_precision variable.
Bye, Heribert (da...@ifk20.mach.uni-karlsruhe.de)
Paul Eggert
Martin Shepherd <m...@goblin.caltech.edu> writes:
>I read this to mean that one can print any double precision number
>with as few digits as possible, using:
> #include <float.h>
> sprintf(buffer, "%.*g\n", (int) DBL_DIG, 1.0/2.5);
>and then read the number back using atof(buffer) to recover the
>original binary representation.
No, in general you need more than DBL_DIG digits. This is because
DBL_DIG gives the limit on the size of text strings, such that
converting a string to double and then back to string gives you
the same value again. But what's wanted here is the reverse:
we want to convert a double to a string and then back again
without losing information. In the worst case, this requires
a slightly longer string than DBL_DIG; it can require up to
ceil (log10 (FLT_RADIX ** DBL_MANT_DIG))
digits. For IEEE 754 double, DBL_DIG is 15, but the above
expression evaluates to 17, which is why Tcl 8.0b2 uses 17.
Please see my article <news:5sgeem$b66$1...@shade.twinsun.com>
for a more detailed description of this, and for an easy way to print
numbers accurately without having Tcl 8.0b2's problems of noise digits
at the ends of numbers.
Laurent Demailly
This post has 2 sections you can skip to the next part if you feel you
already know everything about FP numbers...) :
Generalities
------------
My programming experience (and remaining memories from basic CS courses)
taught me (sometimes the hard way) that there is no point in using == for
floating points number comparisons (in C) because it is almost guaranteed
to fail when you don't expect it because of rounding errors on the
last bit(s).
Instead I painfully learned to use comparison within a relative
+/-epsilon range, if I understand well John proposal, it is to make
the common programmers' life easy by doing that *necessary* epsilon
fuzzy comparison for them in TCL, which to me seems a really good thing.
(and not only because John is my boss :p)
If you still want your comparison to fail randomly (which is
a real bug source IMO) because of roundoff errors but getting
your "equivalence relation", you can always use
[string compare [format %.17g $x1] [format %.17g $x2]]
this is semantically equivalent to x1 == x2 in C for 2
double's (but obviously slower and uglier, but again you
should not ever need to do that, maybe something for
the future would be to define "-eq" and so on operators
for people who think they know what they are doing and
want an 'exact' comparison).
I would like to see an example of something that would break
with the new scheme, not just theoretical objections (which are
valid, but just don't apply I think) : ie the scheme is not
"beautiful" to our mathematical mind but it sure does help a
lot the poor programmer stuck on a computer using a fixed and finite
number of bits for "real" numbers.
Specific comment
----------------
[...]
> Consider one possible scenario: procedures A1 finds that x1 == x2,
> and passes x2 to A2 which finds x2 == x3 and passes x3 on to A3
> and so on. At the end of this chain, there is a reasonable
> expectation that xn == x1 in procedure An but may not in fact be
> the case.
If you use an == like in C, procedure A1 would have a random
result (because round off errors) so the chance that A1*A2*A3
is true is probably 0 : it would be bad programming to try that
on numbers.
Now if you do that with the new tcl scheme, "==" means
"so close than you can use one instead of the other in another operation"
but yes, obviously that relation is not more transitive than the == was.
"close to" does not compose well with numerous repetitions
> To cope with this, the entire population of TCL programmers will
> have to retrain their minds to a new and unfamiliar reality: that
> == is no longer an equivalence relation.
> It is not that the proposed scheme is inherently bad; it is bad
> because it is so severely at variance with programmer experience of
> floating point numbers.
I think that the experienced programmers will be happy to
see that they don't have to re-implement epsilon floating
point numbers comparison and that it's part of the language.
And I think inexperienced programmers will enjoy that
working on floating points will behave like they could innocently
expect. Ok, if they start doing recursive composition of operators,
or maybe very intensive or complex computations, they'll have
to understand the floating points mechanism anyway, or they'll
get unexpected results, it is just that Tcl tries to set
the "have to worry about floating point" trigger above most
applications uses, instead of forcing *every* programmer to deal
with it. Why that ? because it is not only programmers
but also *users* that are are going to write small piece of Tcl
code (like set v [expr $v+.1] ; if {$v == 1.1 } ... and those guys
really don't event want to hear about why the true result
is 1.1000000000000001 for v=1, they really want to see 1.1 !)
Note: I am speaking for myself only in that post, not for SunScript
--
Laurent Demailly (dl) * Sun labs * SunScript - Tcl/Tk team
Paul Eggert
>> problem is its complexity: this gets us into the business of writing
>> floating-point conversion routines, which is complicated and platform-
>> specific; it would take months to iron out all of the porting problems.
But it's not complicated! And it's not platform-specific!
At the end of this message is a portable little routine that converts
floating-point numbers to minimal text strings without losing information.
This routine uses only facilities guaranteed by the C Standard,
and it's easy to port to pre-ANSI systems if that's important to you.
Yes, there are very complicated ways to speed up this conversion,
but you needn't to worry about implementing them,
as this method is fast enough for Tcl.
This is the first I've seen of Ousterhout's objection;
otherwise, I would have written earlier.
If the Tcl implementers thought that complexity was the main problem
with this approach, then I urge them to reconsider:
it needn't be complicated at all!
#include <float.h>
#include <math.h>
#include <stdlib.h>
#if FLT_RADIX == 2 && DBL_MANT_DIG == 53
# define doubleDigitsMax() 17 /* Speed up IEEE 754, the most common case. */
#else
int
doubleDigitsMax()
{
return (int) ceil(log10(pow(FLT_RADIX, DBL_MANT_DIG)));
}
#endif
void
convertDoubleToString (d, p)
double d;
char *p;
{
int digits = DBL_DIG;
do {
sprintf(p, "%.*g", digits, d);
} while (digits++ < doubleDigitsMax() && atof(p) != d);
}
Martin Shepherd
egg...@twinsun.com (Paul Eggert) writes:
> Martin Shepherd <m...@goblin.caltech.edu> writes:
> >I read this to mean that one can print any double precision number
> >with as few digits as possible, using:
> > #include <float.h>
> > sprintf(buffer, "%.*g\n", (int) DBL_DIG, 1.0/2.5);
> >and then read the number back using atof(buffer) to recover the
> >original binary representation.
>
> No, in general you need more than DBL_DIG digits. This is because
> DBL_DIG gives the limit on the size of text strings, such that
> converting a string to double and then back to string gives you
> the same value again. But what's wanted here is the reverse:
> we want to convert a double to a string and then back again
> without losing information....
Having spent this afternoon reading the Steele and White paper and
performing some simple experiments, I concur with this. I take back my
suggestion.
> Please see my article <news:5sgeem$b66$1...@shade.twinsun.com>
> for a more detailed description of this, and for an easy way to print
> numbers accurately without having Tcl 8.0b2's problems of noise digits
> at the ends of numbers.
I am interested in seeing this article, but our news server doesn't
have a copy of it, and I couldn't locate it through dejanews. Could
you please E-mail a copy to me (or repost it in comp.lang.tcl)?
Martin Shepherd (m...@astro.caltech.edu)
Martin Shepherd
egg...@twinsun.com (Paul Eggert) writes:
>ous...@tcl.eng.sun.com (John Ousterhout) writes:
>> We considered this approach and eventually decided against it. The main
>> problem is its complexity: this gets us into the business of writing
>> floating-point conversion routines, which is complicated and platform-
>> specific; it would take months to iron out all of the porting problems.
>
> But it's not complicated! And it's not platform-specific!
>...
>
> #include <float.h>
> #include <math.h>
> #include <stdlib.h>
#include <stdio.h>
>
> #if FLT_RADIX == 2 && DBL_MANT_DIG == 53
> # define doubleDigitsMax() 17 /* Speed up IEEE 754, the most common case. */
> #else
> int
> doubleDigitsMax()
> {
> return (int) ceil(log10(pow(FLT_RADIX, DBL_MANT_DIG)));
> }
> #endif
>
> void
> convertDoubleToString (d, p)
> double d;
> char *p;
> {
> int digits = DBL_DIG;
> do {
> sprintf(p, "%.*g", digits, d);
> } while (digits++ < doubleDigitsMax() && atof(p) != d);
> }
I vote for this. It is a bit slower than a direct sprintf(buf, "%.12g"),
but the slowdown is probably negligible compared to the time that it
takes to parse a Tcl expression in the first place.
Note that DBL_DIG turns up here as the minimum number of significant
figures that you need to try with %g. The resulting %g specifier will
omit trailing zeroes if fewer figures than this are actually
needed. FWIW, this observation was what prompted my earlier post. I
had written an algorithm similar to the one that Paul produced
above, only to discover that it always settled on %15g
(ie. DBL_DIG=15). After finding some rationale for this in the C
standard, I dumped my algorithm in favor of always using DBL_DIG
significant figures. It wasn't until hours after posting about this
that I discovered that numbers that start out with more than DBL_DIG
significant figures need more than DBL_DIG digits to represent them
accurately...
I hope that the Tcl team will seriously consider Paul's example
algorithm instead of adopting the ad hoc %.12g.
Martin Shepherd (m...@astro.caltech.edu)
Paul Eggert
Laurent Demailly <Laurent....@sun.com> writes:
> I painfully learned to use comparison within a relative +/-epsilon range,
> if I understand well John proposal, it is to make the common programmers'
> life easy by doing that *necessary* epsilon fuzzy comparison for them in TCL,
Did you learn to use fuzz when applying < and <= to floating point values?
That would have been very strange; I've never seen any numerical textbook
recommending that. But the proposal in Ousterhout's message would do this.
Why?
Also, did you learn to use a single universal value of epsilon for
comparing floating point values for approximate equality? That would
have been very strange as well. All the textbooks I've seen say that
such epsilons are application-dependent.
> I would like to see an example of something that would break
> with the new scheme,
Lots of things would break under the proposal in Ousterhout's message.
* As other people have pointed out, the Tcl numeric comparison rules
would differ from the C numeric comparison rules, and this gratuitous
incompatibility would confuse people.
* One fuzz factor would be used for comparing doubles, but a
different fuzz factor would be used for converting doubles to strings.
This would lead to confusion. E.g. 1.000000000005 would not compare
equal to 1.00000000001, but they would both convert to the same string.
Conversely, 0.9999999999995 would compare equal to 1, but they would
convert to two different strings. I don't think there's any efficient
way to make the two fuzz factors entirely consistent.
* Numeric comparison would use relative error, but for many
applications, relative error is inappropriate. For example,
if my data points represent latitude and longitude of airports
scattered around the globe, I should use absolute error, not relative
error, to determine whether an airplane with given coordinates is
``at'' an airport. If I use relative error, my tests will be
much pickier about airports near the equator or prime meridian, and
this will be incorrect (and the bug could well be hard to find).
* Here's another example. Suppose I have an application that reads
probability values, which must fall in the range 0..1 (inclusive).
I use <= to check that the values are in range. My check would
allow 1.000000000001 as a valid probability, and this could screw
up the rest of my code royally.
* Furthermore, with probabilities the values 0 and 1 are special;
it's entirely reasonable in floating point computations involving
probabilities, to check whether a value equals 0, or equals 1, since
such tests can be done exactly. But only the test against 0 would be
exact; the test against 1 would be approximate, and this would be
incorrect for an application that deals with probabilities.
There are other bad properties of that scheme but I'm not sure I
should spend more of my time (and yours) by describing them.
> I think that the experienced programmers will be happy to
> see that they don't have to re-implement epsilon floating
> point numbers comparison and that it's part of the language.
No, experienced programmers will be upset, since relative
floating point number comparison is often the wrong thing to do.
Worse, you're not even giving them control of the epsilon!
> it is not only programmers
> but also *users* that are are going to write small piece of Tcl
> code (like set v [expr $v+.1] ; if {$v == 1.1 } ... and those guys
> really don't event want to hear about why the true result
> is 1.1000000000000001 for v=1, they really want to see 1.1 !)
You're criticizing the behavior of Tcl 8.0b2,
Apparently you haven't seen my proposal for fixing 8.0b2's behavior,
which doesn't have the problems that I described above.
Nor does it have the specific problem that you mention.
Under my proposal, if v is 1, then
`set v [expr $v+.1] ; if {$v == 1.1 }'
will work as expected, and the result will print as 1.1.
Please see <news:5se3fo$5q0$1...@shade.twinsun.com>
and <news:5sgeem$b66$1...@shade.twinsun.com> for more details;
I can email them to you if they've missed your news server.
It's true that some naive programs will work under the proposal in
Ousterhout's message, and they won't work under my proposal; but
the reverse is also true, so I don't think this argument is decisive.
What's important is that the proposal in Ousterhout's message
sometimes gives _wrong answers_ about numbers, and this has several bad
consequences (some described above), and is hard to explain;
whereas my proposal is numerically honest and is easy to explain.
Munagala V. S. Ramanath
Laurent Demailly <Laurent....@sun.com> writes:
>This post has 2 sections you can skip to the next part if you feel you
>already know everything about FP numbers...) :
>Generalities
>------------
>My programming experience (and remaining memories from basic CS courses)
>taught me (sometimes the hard way) that there is no point in using == for
>floating points number comparisons (in C) because it is almost guaranteed
>to fail when you don't expect it because of rounding errors on the
>last bit(s).
That is the point: like you, almost all programmers have learned to
be wary when comparing floating point values. None have learned that
the relational operators may not be transitive; on the contrary ALL
have learned that in fact they are.
The collateral lesson to be learned, of course, is: Use == only when
rounding is not an issue and you NEED _exact_ equality. There are
many contexts where exact equality is appropriate: For example,
1. When working with 2D graphics algorithms on a pixel grid, you
often need something like (x >= 0.5) to determine whether to turn
on a pixel or not. The proposed introduction of fuzziness will
cause wrong pixels to be chosen.
2. When caching bitmaps generated from scaleable outline fonts, the
matrix used to generate the bitmap needs to be compared EXACTLY
because even the slightest change in the matrix can yield a
different bitmap.
>Instead I painfully learned to use comparison within a relative
>+/-epsilon range, if I understand well John proposal, it is to make
>the common programmers' life easy by doing that *necessary* epsilon
>fuzzy comparison for them in TCL, which to me seems a really good thing.
>(and not only because John is my boss :p)
It is unlikely that a single global fuzz factor will be widely
useful. Every domain needs its own. When working with dollars and
cents a tolerance of 0.001 might be sufficient; when working with
pixels, a tolerance of 0.5 may be acceptable. When working with
iterative methods where error may accumulate, it requires careful
analysis of both the algorithm and the range of data values to
choose a meaningful tolerance. The TCL proposal is thus both
useless and dangerous because it promotes a false sense of
security.
>If you still want your comparison to fail randomly (which is
>a real bug source IMO) because of roundoff errors but getting
>your "equivalence relation", you can always use
>[string compare [format %.17g $x1] [format %.17g $x2]]
>this is semantically equivalent to x1 == x2 in C for 2
>double's (but obviously slower and uglier, but again you
>should not ever need to do that, maybe something for
>the future would be to define "-eq" and so on operators
>for people who think they know what they are doing and
>want an 'exact' comparison).
I think a better solution, if there indeed is a problem, is
to implement fuzzy relational operators like ~==, ~!=, ~<, etc.
for those who feel the need for fuzzy non-transitive relationals.
>I would like to see an example of something that would break
>with the new scheme, not just theoretical objections (which are
>valid, but just don't apply I think) : ie the scheme is not
>"beautiful" to our mathematical mind but it sure does help a
>lot the poor programmer stuck on a computer using a fixed and finite
>number of bits for "real" numbers.
This is false help: it promotes an ersatz sense of security which
will cause more serious problems that it solves. As noted above,
the "poor programmer" has already learned the lessons of finite
precision numbers and will have to learn a whole new set.
There are numerous contexts where the proposed change could cause
severe problems: the simplest example is sorting. A bubble sort
which worked before will now break. How many of the other sorting
algorithms rely on transitivity ? Does quicksort ? heapsort ?
shellsort ? exchange sort ? Each one of these algorithms will have
to be examined to determine the effect of the new semantics.
Standard algorithms from textbooks cannot be directly transcribed
into tcl (something novice and expert alike are likely to do) since
suddenly the relationals have a new semantic twist.
Transitivity is not some ivory tower abstract math concept; it is
deeply and firmly embedded in legacy code, algorithms, and almost
all programmers minds. Programmers will rely on it subconsciously
because ALL programming languages guarantee it. For example, C++
allows operator overloading, so the relationals can be redefined
on a per class basis to be whatever you want. However, STL
(Standard Template Library -- part of the C++ Draft Standard)
specifically requires == to be an equivalence relation. The notion
is so fundamental that it is sheer folly to tinker with it.
This is what makes the tcl proposal so dangerous: it suddenly turns
every piece of existing tcl code into a land mine. The
aforementioned "poor programmer" has no way to detect and defuse
these mines. From time to time she will step on one and pay the
price of painful and costly debugging and recoding.
>Specific comment
>----------------
>[...]
>> Consider one possible scenario: procedures A1 finds that x1 == x2,
>> and passes x2 to A2 which finds x2 == x3 and passes x3 on to A3
>> and so on. At the end of this chain, there is a reasonable
>> expectation that xn == x1 in procedure An but may not in fact be
>> the case.
>If you use an == like in C, procedure A1 would have a random
>result (because round off errors) so the chance that A1*A2*A3
>is true is probably 0 : it would be bad programming to try that
>on numbers.
Far from being random, the result is very precise: whether the
two values being compared are in fact equal or not. I find the rest
of the sentence to be incomprehensible, so cannot respond to it.
>Now if you do that with the new tcl scheme, "==" means
>"so close than you can use one instead of the other in another operation"
>but yes, obviously that relation is not more transitive than the == was.
>"close to" does not compose well with numerous repetitions
Transitivity either holds or it does not. "More" or "less"
transitive is a novel notion. Relationals are frequently and --
this is important -- unconsciously "composed" in common programming
experience.
>> To cope with this, the entire population of TCL programmers will
>> have to retrain their minds to a new and unfamiliar reality: that
>> == is no longer an equivalence relation.
>> It is not that the proposed scheme is inherently bad; it is bad
>> because it is so severely at variance with programmer experience of
>> floating point numbers.
>I think that the experienced programmers will be happy to
>see that they don't have to re-implement epsilon floating
>point numbers comparison and that it's part of the language.
It is a rare "experienced programmer" indeed for whom a single
tolerance is universally satisfactory, who will be happy to see
existing sorting code broken, or happy to learn new paradigms for
numerical comparison with the attendant burden of having to
examine every algorithm in painstaking detail to assess its
reliance on transitivity.
>And I think inexperienced programmers will enjoy that
>working on floating points will behave like they could innocently
>expect. Ok, if they start doing recursive composition of operators,
>or maybe very intensive or complex computations, they'll have
>to understand the floating points mechanism anyway, or they'll
>get unexpected results, it is just that Tcl tries to set
>the "have to worry about floating point" trigger above most
>applications uses, instead of forcing *every* programmer to deal
On the contrary, it encourages unsafe practises such as using
floats as loop counters, sets the trigger MUCH lower in the sense
that elementary code such as sorting will no longer work.
>with it. Why that ? because it is not only programmers
>but also *users* that are are going to write small piece of Tcl
>code (like set v [expr $v+.1] ; if {$v == 1.1 } ... and those guys
Anyone who expects users (i.e. non-programmers) to be writing tcl
code is living in a dream world. Users typically find VCR's too
hard to use, find it difficult to cope with more than 1 button on a
mouse and reading README files excessively burdensome. I have no
hard data to support this of course but it is a near certainty that
the overwhelming majority of the tcl programmers are in fact
programmers, not naive end-users. It is a poor idea to cater to an
imaginary segment of the user population.
>really don't event want to hear about why the true result
>is 1.1000000000000001 for v=1, they really want to see 1.1 !)
The conclusion is unavoidable and will brook no palliation: There
are no redeeming qualities whatsoever for destroying transitivity of
relationals. It is an unmitigated disaster.
Ram
John Ousterhout
In article <5sgeem$b66$1...@shade.twinsun.com>, egg...@twinsun.com (Paul Eggert) writes:
|> ...
|> At the end of this message is a portable little routine that converts
|> floating-point numbers to minimal text strings without losing information.
|> This routine uses only facilities guaranteed by the C Standard,
|> and it's easy to port to pre-ANSI systems if that's important to you.
|>
|> Yes, there are very complicated ways to speed up this conversion,
|> but you needn't to worry about implementing them,
|> as this method is fast enough for Tcl.
|>
|> This is the first I've seen of Ousterhout's objection;
|> otherwise, I would have written earlier.
|> If the Tcl implementers thought that complexity was the main problem
|> with this approach, then I urge them to reconsider:
|> it needn't be complicated at all!
|>
This algorithm is not addressing the same problem that my proposed changes
for 8.0 address.
The "complicated and platform-dependent" algorithm I was referring to in my
posting is the one by Steele and White, which chooses on a value-by-value
basis the minimum number of digits to print to avoid losing any information
when the value is read back in again. The code above does something different.
In particular, it uses the same number of digits for all values on a given
machine, and for IEEE floating-point it does exactly the same thing as
Tcl 8.0b2. Although it is a modest improvement over the approach of 8.0b2
(it does a better job with platforms that don't use IEEE arithmetic) it
doesn't do anything to address the precision issues and counter-intuitive
behavior that motivated the changes I proposed. I believe it will still
print 1.4 as 1.39999999999..., no?
Laurent Demailly
> The collateral lesson to be learned, of course, is: Use == only when
> rounding is not an issue and you NEED _exact_ equality. There are
> many contexts where exact equality is appropriate: For example,
> 1. When working with 2D graphics algorithms on a pixel grid, you
> often need something like (x >= 0.5) to determine whether to turn
> on a pixel or not. The proposed introduction of fuzziness will
> cause wrong pixels to be chosen.
If you use "exact" comparison, you will choose the wrong pixel:
because "expr (1-0.3-0.2) >= 0.5"
returns 0 without fuzzy comparison, so you would effectively
assign the wrong pixel if you use your "exact" comparison, no ?
( (1-0.3-0.2) = 0.49999999999999994 which is unfortunately not >= 0.5
if we *don't* do fuzzy comparison)
I think only with fuzzy comparison you would be choosing the right one.
(for me "expr 1-.3-.2 >= .5" is 1 not 0)
> 2. When caching bitmaps generated from scaleable outline fonts, the
> matrix used to generate the bitmap needs to be compared EXACTLY
> because even the slightest change in the matrix can yield a
> different bitmap.
Again, this example is wrong:
If you want to do a memcmp(3) do a memcmp(),
If you want to compute the distance between your matrixes,
don't use == , use sigma( abs(Ai-Bi)) and compare that with
your threshold, but don't try to use == because you would
never cache anything.
> There are numerous contexts where the proposed change could cause
> severe problems: the simplest example is sorting. A bubble sort
> which worked before will now break. How many of the other sorting
I haven't seen a single real case yet. Here, why would it break ?
It won't break, it will just be faster by not trying to
move [expr 1-.3-.2] before 0.5 because they are the same for
all numerical purposes.
> algorithms rely on transitivity ? Does quicksort ? heapsort ?
> shellsort ? exchange sort ? Each one of these algorithms will have
> to be examined to determine the effect of the new semantics.
no harmful effects at all, unless the algorithm is not applicable
anyway to doubles if it depends on == 'working' for doubles (it is not,
never was).
> Standard algorithms from textbooks cannot be directly transcribed
> into tcl (something novice and expert alike are likely to do) since
> suddenly the relationals have a new semantic twist.
On the contrary, most algorithm will start to work for numbers while
they wouldn't if you used "==" "as is"
Again, if someone can come up with a real, non pathological
code that would break, I'll be happy to see it and change my mind.
Martin Shepherd
ous...@tcl.eng.sun.com (John Ousterhout) writes:
> In article <5sgeem$b66$1...@shade.twinsun.com>, egg...@twinsun.com (Paul Eggert) writes:
> |> ...
> |> At the end of this message is a portable little routine that converts
> |> floating-point numbers to minimal text strings without losing information.
> |> This routine uses only facilities guaranteed by the C Standard,
> |> and it's easy to port to pre-ANSI systems if that's important to
> |> you.
>...
> The "complicated and platform-dependent" algorithm I was referring to in my
> posting is the one by Steele and White, which chooses on a value-by-value
> basis the minimum number of digits to print to avoid losing any information
> when the value is read back in again. The code above does something
> different.
No, they do the same thing. The Steele and White algorithm just does
it faster.
> In particular, it uses the same number of digits for all values on a given
> machine,
No it doesn't. I assume that you are refering to the use of DBL_DIG in
%g? I tried to clarify this in my followup to Paul's post. Clearly I
failed. So I'll try again.
What printf("%.*g\n", DBL_DIG, 1.4) does, in effect, is round the
number to DBL_DIG significant places, then discard trailing zeroes
before printing it. The internal rounding is what resolves the 1.4
prints as 1.39999999... issue.
Where the Steele and White algorithm comes into its own is when the
number to be printed started out with more than DBL_DIG significant
figures. In this case the corrupting effect of binary truncation on
the final figures of the decimal representation, necessitate a more
sophisticated algorithm than simple rounding. Paul's function
addresses this problem by resorting to a try-it-and-see strategy when
DBL_DIG figures prove to be insufficient.
> and for IEEE floating-point it does exactly the same thing as
> Tcl 8.0b2.
No it doesn't.
> Although it is a modest improvement over the approach of 8.0b2
> (it does a better job with platforms that don't use IEEE arithmetic) it
> doesn't do anything to address the precision issues and counter-intuitive
> behavior that motivated the changes I proposed. I believe it will still
> print 1.4 as 1.39999999999..., no?
No it won't. To prove the point, I just wrote the following program to
test Paul's convertDoubleToString() function on my Sun:
int main(int argc, char *argv[])
{
double d = 1.4;
char buffer[100];
printf("Tcl8.02b puts [expr 1.4] -> %.17g\n\n", d);
convertDoubleToString(d, buffer);
printf("convertDoubleToString(1.4) -> %s\n", buffer);
return 0;
}
The results were:
Tcl8.02b puts [expr 1.4] -> 1.3999999999999999
convertDoubleToString(1.4) -> 1.4
Please at least give it a try before rejecting it out of hand.
Martin Shepherd (m...@astro.caltech.edu)
Tom Lane
>> severe problems: the simplest example is sorting. A bubble sort
>> which worked before will now break.
> I haven't seen a single real case yet. Here, why would it break ?
> It won't break, it will just be faster by not trying to
> move [expr 1-.3-.2] before 0.5 because they are the same for
> all numerical purposes.
Sorry, you failed to understand ram's complaint in the slightest.
The absolute killer problem with the Tcl comparison proposal is that
transitivity fails: if a == b and b == c, almost any programmer will
assume a == c. That is no longer a safe assumption.
The reason that this breaks sorting algorithms (as well as many
others) is that a usable sort algorithm does not compare every input
value to every other input; it assumes that the basic algebraic laws
of comparison hold, so that it can skip some comparisons.
If you really need it spelled out in words of one syllable,
here is an example. Let the first input value be 1.0 exactly.
Let each subsequent value be the previous value times
(1.0-1e-12), or whatever your epsilon is. Apply a bubblesort
to this array. It will make one pass through the array, find
that A[i] <= A[i+1] (fuzzily) at each pair, and report that
the array is already in sorted order. With a large enough
array, however, the later elements will be *grossly* smaller
than the earlier.
It is not acceptable to assert that such an array is in "good
enough" sorted order. For example, suppose I now try to use
binary search to locate an element of the array. Since A[1]
is larger than A[n] my search will probably report that *any*
input value is not a member of the array. This is not a "good
enough" answer, it is total program failure. And it is failure
of a method that works with 100% reliability in every other
programming language under the sun. You will not get far by
telling programmers that Tcl is OK and their code is wrong.
BTW, bubblesort will at least assure that adjacent array elements
are not obviously mis-sorted. A more sophisticated sort method,
such as quicksort or heapsort, might fail even that elementary
check, because it relies more heavily on the normal arithmetic
laws of comparison.
> Again, if someone can come up with a real, non pathological
> code that would break, I'll be happy to see it and change my mind.
I have seen people shoot themselves in the foot before, but I have
seldom watched them load, aim, and fire so deliberately and publicly.
I had hoped that Tcl 8 would be more usable for numerically-oriented
tasks because of the compiler and the support for binary numeric values.
Instead it looks like Tcl 8 will be quite untrustworthy for any purpose
involving numbers that are not exact integers. I guess I'd better go
start studying Java.
regards, tom lane
Paul Eggert
ous...@tcl.eng.sun.com (John Ousterhout) writes:
>The code ... uses the same number of digits for all values on a given
>machine, and for IEEE floating-point it does exactly the same thing as
>Tcl 8.0b2.
No it doesn't. Tcl 8.0b2 always uses %.17g. On an IEEE floating point host,
the code tries %.15g, and if this represents the result exactly it stops.
Otherwise it tries %.16g, and only if that fails does it fall back on %.17g.
%.15g can generate values with less than 15 digits.
> (it does a better job with platforms that don't use IEEE arithmetic)
Yes, the code should be portable to all floating point platforms.
>it doesn't do anything to address the precision issues and counter-intuitive
>behavior that motivated the changes I proposed. I believe it will still
>print 1.4 as 1.39999999999..., no?
No, it prints 1.4 as 1.4, and it prints 1.39999999999 as 1.39999999999.
It does the right thing without any fuss or fuzz.
Try it; you'll like it!
Will Morse
In article <m1iuxgx...@creche.cygnus.com>,
Tom Tromey <tro...@cygnus.com> wrote:
>[ discussion of Paul Eggert's suggested approach to printing FP ]
>
>John> We considered this approach and eventually decided against it.
>John> The main problem is its complexity: this gets us into the
>John> business of writing floating-point conversion routines, which is
>John> complicated and platform- specific; it would take months to iron
>John> out all of the porting problems.
>
>I haven't investigated the suggested approach enough to know if this
>is true. I will note that if you don't care about performance then
>you can do it purely with the standard functions: just take the
>initial string repr and chop digits off the end until you find one
>that doesn't convert back to double precisely.
>
>I have no real reason to believe a more efficient method couldn't be
>found.
>
>Are there systems you care about that don't do IEEE math? If they are
>relatively obscure, then let various people on the net champion the
>porting process.
In the petroleum exploration industry, the widely used
SEG-Y standard specifies "IBM" Floating Point, even though
very few systems in the petroleum industry are still IBM
370 architecture and most use IEEE. I would like to see
some flexibility in these regards, although the truth is
that I use Tcl for the GUI and call perl for most
computational tasks.
Will
--
# Copyright 1997 Will Morse. Internet repost/archive freely permitted.
# Hardcopy newspaper, magazine, etc. quoting requires permission.
#
# Gravity, # Will Morse
# not just a good idea, # Houston, Texas
# it's the law. # wi...@starbase.neosoft.com
#
# These are my views and do not necessarly reflect anyone else/
=========================================================================
By US Code Title 47, Sec.227(a)(2)(B), a computer/modem/printer
meets the definition of a telephone fax machine. By Sec.227(b)
(1)(C), it is unlawful to send any unsolicited advertisement to
such equipment, punishable by action to recover actual monetary
loss, or $500, whichever is greater, for EACH violation.
=========================================================================
Robin Becker
In article <uo9yb69...@netcom12.netcom.com>, Tom Lane
<t...@netcom.com> writes
>
>I have seen people shoot themselves in the foot before, but I have
>seldom watched them load, aim, and fire so deliberately and publicly.
>
>I had hoped that Tcl 8 would be more usable for numerically-oriented
>tasks because of the compiler and the support for binary numeric values.
>Instead it looks like Tcl 8 will be quite untrustworthy for any purpose
>involving numbers that are not exact integers. I guess I'd better go
>start studying Java.
>
> regards, tom lane
impossible.
Please let's use full accuracy wherever possible.
--
Robin Becker
B.Ste...@isode.com
In article <5sa9j7$hio$1...@engnews2.Eng.Sun.COM>,
ous...@tcl.eng.sun.com (John Ousterhout) wrote:
> each other. More precisely, a and b are considered equal if
> (abs(a-b)/(abs(a) + abs(b)) < .5e-12
> This means, for example, that 8.0 >= 8.00000000000001. This approach
> means that code like the following loop does what you'd expect:
> for {set x .1} {$x < 1.4} {set x [expr $x + .1]} {...}
> If you want a full-precision comparison, you can get it by reorganizing
> the expression to compare against 0. For example, instead of
> if {$x < 1.4} ...
> say instead
> if {($x - 1.4) < 0} ...
> Comparisons against 0 are always exact, by definition from the above formula.
> With this approach, Tcl 8.0 will have default behavior that's more precise
> than Tcl 7.6, but you'll have to do extra work to get "full" precision: you
> can't just set the tcl_precision variable.
This is far better than many other ways of fudging things would be, and
suggests that some thought has been put into the proposal. Those
numerical analysts who have looked at the design of floating point
arithmetic seem to agree: the system should satisfy as many regular,
simple, laws as possible. To an extent, exactly what those laws are
isn't all that important---they don't *need* to be what mathematicians
might expect, although mostly they will be. So rather than presenting
the proposal in terms of specific loops which will work as expected,
could you give a set of laws which the system will satisfy, and some
which it doesn't? For example, as far as I can see, it's not obvious
that (even excluding zero), inequalities will be transitive (symmetry
looks OK, and perhaps things are transitive---I haven't made a real
effort to check).
To an extent, you can be screwed by whatever the underlying system
provides you with, but some idea of what properties will be carried
through assuming the system uses IEEE would be good, since just about
every system does nowadays.
-------------------==== Posted via Deja News ====-----------------------
http://www.dejanews.com/ Search, Read, Post to Usenet
Paul Duffin
I also am not a floating point guru but it seems to me that the current
Ousterhout proposal makes trivial programs work but at the cost of
making anything more complicated impossible to write in Tcl.
The following is a summary of the arguments as I see them.
The string representation problem could easily be solved using the
Steele and White solution which while it is a little bit slower still
gives reasonable results. (The performance problem is not too much of
an issue now that we have Tcl_Objs as the string representation only
needs to be calculated once when the value changes). This proposal does
not stop people doing their own formatting to get the result they want
it just ensures that the implicit conversion is reasonable.
The comparison problem is something that ALL programmers encounter at
some time and never forget. Making the comparison routines fuzzy means
that NOBODY can do exact comparisons while leaving them exact at least
gives the people who want a fuzzy comparison the ability to do a fuzzy
comparison. Maybe the solution is to provide operators (I'd prefer
named operators e.g. almost_equal rather than any symbolic operator) to
make it easy for people who want to to do fuzzy comparisons and still
lets everyone else cope with the problem how they like it and under the
same conditions as almost all other languages.
As far as I can tell the consensus is for the Steele and White string
representation and normal non-fuzzy comparison operators with maybe some
built in mathematical functions for doing relative / absolute epsilon
comparisons.
I have only seen arguments against the current proposal (none in
support) of it so it is not really a problem for people writing simple
scripts, they have to learn to cope with it whatever language they code
in.
If the current proposal is implemented then the tcl community will be
split into two, those who want the exact comparisons will produce a
patch which will put them back into the base. This will mean that tcl
extensions which rely on the different behaviours will not work
together.
If however the current proposal is changed to the consensus (as I see
it) then those people who want to write simple tcl programs will learn
to cope with the situation (they are probably not the sort of people
who will want to patch the base just to get fuzzy comparison) and
everyone else will be happy.
--
Paul Duffin
DT/6000 Development Email: pdu...@hursley.ibm.com
IBM UK Laboratories Ltd., Hursley Park nr. Winchester
Internal: 7-246880 International: +44 1962-816880
Martin Shepherd
Tom Lane <t...@netcom.com> writes:
>...
> I had hoped that Tcl 8 would be more usable for numerically-oriented
> tasks because of the compiler and the support for binary numeric
> values.
Me too.
> Instead it looks like Tcl 8 will be quite untrustworthy for any purpose
> involving numbers that are not exact integers. I guess I'd better go
> start studying Java.
You might want to wait a bit. As far as I know, short of writing your
own formatting class, there is no way in Java to display a floating
point number with a specified number of significant figures.
Maybe its time to take another look at Python.
Martin Shepherd (m...@astro.caltech.edu)
Will Morse
I would just like to say that it is refreshing to find
postings in this newsgroup that are NOT related to CGI
or saying "nyah-nyah my language is better." but focus
on real Tcl/Tk issues.
Thank you to all who have contributed, even if we all
don't necessarily agree.
Jonathan Cook
Martin Shepherd (m...@goblin.caltech.edu) wrote:
: Tom Lane <t...@netcom.com> writes:
: >...
: > I had hoped that Tcl 8 would be more usable for numerically-oriented
: > tasks because of the compiler and the support for binary numeric
: > values.
: Me too.
Me three.
Another post about the lack of "slick environments" like in VB got
me wondering...
Since this proposal (for fuzzy relational ops) was made to keep the
unclean masses from dealing with the vagaries of FP,
And since VB has probably two to three orders of magnitude of unclean
masses programming it as compared to Tcl (the poster of "slick
environments" made the reference to hiring BA/Psychology programmers),
Can anyone tell us what VB does, and how it explains/addresses FP
in its manual?
If FP comparisons are a problem for the unclean masses, you can bet
it will be addressed either in what VB does or in the manual. We have
here an instant user survey that can tell us if there is *any* basis
for going down this path.
Remember, I'm only talking about fuzzy relational ops, not the printing
stuff.
To whoever has the resources to check out VB, thanks ahead of time.
JonCook.
Viktor Dukhovni
In <5so5mh$2...@nntpb.cb.lucent.com> g...@mhcnet.lucent.com (George A. Howlett) writes:
>The first issue, I think we can all agree upon.
>The way Tcl prints floating point numbers needs to be fixed. Tcl 8.0's
>".17g" format gives non-intuitive results.
...
>Fix this and I think most of us will be happy.
Amen.
>The second issue has to do with the fact that code that used to work
>in Tcl 7.6 will now fail in 8.0.
...
>The first problem is that to really do the calculator model right, you
>have to give up too much precision. My suggestion fixes too few cases
>to be worth the loss of precision. It's better to let the programmer
>fix things where the tolerances of the problem are known.
> set count 0
> for { set i 0.1 } { $i <= 2.50001 } { set i [expr $i + 0.1] } {
> incr count
> }
>Judging from the responses I've seen, it appears that handling finite
>arithmetic in this way is (in some fashion) well understood.
Right on! Since it was George who started the whole
thread, and even he is now in favour of dropping fuzzy comparison,
does the Sun team yet agree that they are swimming against the tide?
Let's print numbers smarter, and let the programmer worry about
the fuzz in his floating point numbers...
--
Viktor.
Felix Lee
urm. this is what I'd like to be true.
1. [expr "1.1"] == "1.1"
2. exactly one of these relationships is true for any $a and $b:
$a < $b
$a == $b
$b < $a
3. set s ".111111111111111111111111111111111111"
[expr $s] == $s
4. set s "1111111111111111111111111111111111111"
[expr $s] == $s
--
George A. Howlett
There are really two separate issues here. Thanks to Paul Eggert for
clearing the waters.
The first issue, I think we can all agree upon.
The way Tcl prints floating point numbers needs to be fixed. Tcl 8.0's
".17g" format gives non-intuitive results.
% expr 1.0 + 0.1
1.1000000000000001
% expr 1.2 - 0.1
1.0999999999999999
I originally had suggested to format using ".15g" because it was quick
and simple change. But Paul Eggert's suggestion of using Guy Steele's
and Jon White's approach ("How to Print Floating-Point Numbers
Accurately" [Proc. ACM SIGPLAN '90, pp. 92-101].) is right on target.
David Gay's free implementation on can be found on netlib. The URL is
http://plan9.bell-labs.com/netlib/fp/dtoa.c.gz
Fix this and I think most of us will be happy.
------
The second issue has to do with the fact that code that used to work
in Tcl 7.6 will now fail in 8.0.
set count 0
for { set i 0.1 } { $i <= 2.5 } { set i [expr $i + 0.1] } {
incr count
}
In Tcl 7.6, the loop would iterate 25 times, in Tcl 8.0 it now
iterates 24 times.
This is a common problem: how to deal with a computer's finite
representation of numbers.
I suggested to using a "calculator" model, where there is both an
external representation for numbers (the one the user sees) and an
internal one. The actual internal representation is bigger than the
external.
Calculators are designed this way to hide away the problems of finite
arithmetic. For example, take the square root of 3, square it, and
subtract 3 (((3^0.5)^2)-3). On most calculators, the answer is 0.
Try this with xcalc and you get something else.
I suggested a slightly smaller external representation, moving machine
epsilon up to 1e-15. [John's plan to limit the precision (1e-12) of
comparisons is along the same vein.]
Machine Epsilon
IEEE Double ~2.22e-16
John 1e-12
gah 1e-15
Well, (taking John's suggestion) I bounced this idea off some bona
fide numeric experts. And they were in agreement. It's a bad idea.
The first problem is that to really do the calculator model right, you
have to give up too much precision. My suggestion fixes too few cases
to be worth the loss of precision. It's better to let the programmer
fix things where the tolerances of the problem are known.
set count 0
for { set i 0.1 } { $i <= 2.50001 } { set i [expr $i + 0.1] } {
incr count
}
Judging from the responses I've seen, it appears that handling finite
arithmetic in this way is (in some fashion) well understood.
The most persuasive point to me was that people always want more, not
less, precision. "80 bits isn't good enough, I need 81". So any loss
of precision (no matter what reason) might deter people from using
Tcl.
I think it would be a great solution if Tcl had hooks that allowed an
extended precision package to slip right in. But right now I'm
willing to settle for fixing the binary to string conversion of
numbers.
--gah
Paul Eggert
ous...@tcl.eng.sun.com (John Ousterhout) writes:
>If you want a full-precision comparison, you can get it by reorganizing
>the expression to compare against 0. For example, instead of
> if {$x < 1.4} ...
>say instead
> if {($x - 1.4) < 0} ...
This method works in systems that have IEEE floating point, but it is
not portable to IBM floating point, VAX floating point, or any other
widely used floating point system that I know of.
It works with IEEE because IEEE has gradual underflow and denormalized
numbers at the smallest exponent level. With IEEE, if A<B, then A-B<0.
But with VAX, IBM, etc., you can have two numbers A and B such that A<B
but A-B==0, because the exponent underflows when you do the subtraction.
Furthermore, some IEEE hosts operate in a nonstandard, ``fast'' mode
which uses IEEE format for numbers but does not support gradual underflow.
The method described above will not work on these quasi-IEEE hosts either.
So this proposal does not allow any convenient, portable way to get
true comparison.
D. M. H. Walker
George A. Howlett wrote:
> set count 0
> for { set i 0.1 } { $i <= 2.5 } { set i [expr $i + 0.1] } {
> incr count
> }
The real problem is that Tcl does not have the right precision. In the
above code the programmer is either assuming infinite precision, or else
fixed point. Infinite precision will always work, but is expensive to
implement. A fixed point model requires a different precision for each
situation, and only the programmer knows for sure.
My vote is to round sensibly for printing, but to leave all other
arithmetic at their full precision. This may break some old code, but
as with the change for octal numbers, it is probably best in the long
run. If you are not going to provide infinite precision, it is best to
provide a standard model, in this case the IEEE standard.
One additional reason for sticking with a standard is that I often
prototype things in Tcl. If they are too slow, then I convert to C or
C++. Numerical codes are a prime example of code that can be too slow.
If the math is the same, conversion is usually straightforward. But if
the math is different, I would be forced to always use the "compare
against 0" escape to ensure that the results would be the same when
translated over.
To echo George's feedback from numerical analysts, when I was working at
Digital in 1980, they looked at making "no brainer" arithmetic, and
found that they would need very large precision, dozens of digits, to
handle nearly all business math problems without error. The lower-cost
answer was to provide packages that did the math correctly. In other
words, it is too expensive to provide the unwashed masses with a padded
math room, and they would rather not have one anyway.
Munagala V. S. Ramanath
ous...@tcl.eng.sun.com (John Ousterhout) writes:
>OK, I think I get it. I hereby raise an electronic white flag on the issue
>of floating-point precision. First, a couple of concessions:
>- The idea of fuzzy comparisons seems to be a bad idea. The compelling
> example to me is the loss of transitivity and its affect on algorithms
> such as sorting.
I think I hear a collective sigh of relief ... .
As a general principle, I would suggest casting a sceptical eye
upon any idea that causes divergence from C/C++ behaviour. This is
not to say that that behaviour is ideal and that variances should
never occur, but another poster has pointed out that he frequently
prototypes in TCL and migrates the slow parts to C. The ease of
this migration is after all one of the significant strengths of TCL
and, I suspect, a lot of TCL programmers operate this way (I
certainly do).
So any variation from C behaviour makes this fluid migration of
code across the C/TCL boundary more difficult and detracts from a
very substantial strength of TCL.
Ram
Robin Becker
In article <5so31b$j...@bubba.NMSU.Edu>, Jonathan Cook
<jc...@cs.nmsu.edu> writes
and within my DLL's they appear to be so. There's a formatting function
for string conversions and if you stuff a double into a cell Excel seems
to make a good guess of how to accept & format it. FP comparisons are
done with the actual IEEE 64 bit representation there's no Fuzz. The
excel docs don't say much about anything as you'ld expect, but there may
be more in the online stuff. My dlls communicate as expected, but I save
the FPU control word and set it up with
_control87(_PC_64,_MCW_PC);_control87(0,_EM_INVALID|_EM_ZERODIVIDE);
as these set up highest accuracy and turn on divide and use of NAN error
trapping; the default compile flags don't seem to do this for me with
VC++ 4.0. On leaving the DLL I'm careful to restore so's not to disturb
things. As far as I can tell VBA's use of doubles is the same as C's.
--
Robin Becker
John Ousterhout
OK, I think I get it. I hereby raise an electronic white flag on the issue
of floating-point precision. First, a couple of concessions:
- The idea of fuzzy comparisons seems to be a bad idea. The compelling
example to me is the loss of transitivity and its affect on algorithms
such as sorting.
- I was wrong when I said that Paul Eggert's conversion algorithm behaves
the same as Tcl 8.0b2: I didn't see the iteration in the conversion
procedure, which tries several precisions. However, I'm still a little
uncomfortable with that approach, partly on efficiency grounds and
partly because I'm not sure I completely understand it (is it truly
identical in behavior to the Steele and White algorithm, for example?).
So, I propose to back off from the changes I proposed last week and revert
to something very similar to what's in Tcl 7.6:
- No fuzzy comparisons: all internal calculations use full precision.
- When converting from floating to string, use %.12g by default, but
support the tcl_precision variable as in Tcl 7.6 so people that need
more precision can get it.
This ends up identical to Tcl 7.6 except that (a) the default precision
increases from 6 to 12 digits (the number 6 was chosen out of efficiency
considerations, but we don't do conversions as often in Tcl 8.0 so we
should be able to afford more precision) and (b) there will be fewer
conversions overall because the Tcl 8.0 object system allows values to
remain in floating form longer, so there will be less rounding due to
conversions.
Using the Steele and White algorithm for conversion is an interesting
possibility for the future, but it would be a non-trivial change and I'm
not comfortable making it this late in the 8.0 release cycle (we should
FCS within about a week).
Tom Lane
ous...@tcl.eng.sun.com (John Ousterhout) writes:
> - No fuzzy comparisons: all internal calculations use full precision.
> - When converting from floating to string, use %.12g by default, but
> support the tcl_precision variable as in Tcl 7.6 so people that need
> more precision can get it.
This sounds good. Thanks for listening.
> Using the Steele and White algorithm for conversion is an interesting
> possibility for the future, but it would be a non-trivial change and I'm
> not comfortable making it this late in the 8.0 release cycle (we should
> FCS within about a week).
Please do think about it for next time --- but I agree it's a bit late
in the cycle to consider it for 8.0.
regards, tom lane
Heribert Dahms
In <5sq5ba$mn0$1...@engnews2.Eng.Sun.COM> ous...@tcl.eng.sun.com writes:
: - No fuzzy comparisons: all internal calculations use full precision.
Wise decision.
: - When converting from floating to string, use %.12g by default, but
: support the tcl_precision variable as in Tcl 7.6 so people that need
: more precision can get it.
Or less, I guess, to get the previous default: set tcl_precision 6
Bye, Heribert (da...@ifk20.mach.uni-karlsruhe.de)
B.Ste...@isode.com
In article <ramEEt...@netcom.com>,
r...@netcom.com (Munagala V. S. Ramanath) wrote:
> As a general principle, I would suggest casting a sceptical eye
> upon any idea that causes divergence from C/C++ behaviour. This is
> not to say that that behaviour is ideal and that variances should
A skeptical eye, certainly, but such changes shouldn't be ruled out. The
motivation for the proposed change (to avoid printing out silly numbers
like 0.999999999999999 when 1 would be just as accurate, and the same for
comparisons) strikes me as entirely worthy, and worth doing (for 8.1,
perhaps). The catch is, the changes should make Tcl no worse than C, in
some sense or other. I'm also glad that John recognises the importance
of such things as transitivity: getting floating point right is hard, and
it's usually the best idea to go for satisfying lots of nice mathematical
laws.
As an example of what Tcl could do which would be incompatible with C,
but quite K00L: it could extend the number stack, adding arbitrary size
integers (using some free implementation of mp, assuming there is one (in
BSD4.4?)), and throw in rationals too. That would be fun. You'd need to
work out what to do with combinations of operators and things, but this
is all standard stuff and has been done before (in CL, Scheme, etc.) An
easier change would be to allow complex floating point numbers. That
would be nice for some people.
Martin Shepherd
ous...@tcl.eng.sun.com (John Ousterhout) writes:
>...
> - I was wrong when I said that Paul Eggert's conversion algorithm behaves
> the same as Tcl 8.0b2: I didn't see the iteration in the conversion
> procedure, which tries several precisions. However, I'm still a little
> uncomfortable with that approach, partly on efficiency grounds and
> partly because I'm not sure I completely understand it (is it truly
> identical in behavior to the Steele and White algorithm, for
> example?).
It has to be identical for numbers that were originally typed in with
<= DBL_DIG significant figures (such as 0.4). For longer input
sequences, the "correct" result is unknowable because some information
on the figures after DBL_DIG is lost during truncation of the
underlying binary number. In such cases there is a finite range of
decimal numbers that when read back will produce the same binary
number. When Steele and White's algorithm is applied to such
pathological cases, it arbitrarily chooses the decimal number that
lies closest to the binary number. Similarly, it seems to me that any
implementation of %.xxg that doesn't output the closest decimal
number, within xx significant figures, is broken.
To provide more solid evidence I decided to run David Gay's public
implementation of the Steele and White algorithm against Paul Eggert's
iterative algorithm. I pulled over David Gay's dtoa.c and g_fmt.c
files. I compiled dtoa.c and g_fmt.c on a Sparc Ultra I using:
cc -c dtoa.c -DIEEE_MC68k
cc -c g_fmt.c
I then got hold of a copy of Paul's convertDoubleToString() and threw
together the following test program:
#include <stdio.h>
int doubleDigitsMax(void);
void convertDoubleToString(double d, char *p);
char *g_fmt(register char *b, double x);
int main(int argc, char *argv[])
{
char eggert[80]; /* The buffer to pass to convertDoubleToString() */
char gray[80]; /* The buffer to pass to g_fmt() */
int i;
for(i=1; i<argc; i++) { /* For each command-line argument */
double d = atof(argv[i]); /* Get the next number to format */
convertDoubleToString(d, eggert); /* Try Paul's iterative approach */
g_fmt(gray, d); /* Try Steele and White's method */
/* Display the results */
printf("%-19s %-19.17g %-19s %-19s\n", argv[i], d, eggert, gray);
};
return 0;
}
I ran this program on a selection of numbers. Here are the results:
What I typed %-19.17g Paul Eggert David Gay
------------------- ------------------- ------------------- ------------------
0.1 0.10000000000000001 0.1 .1
0.12 0.12 0.12 .12
0.123 0.123 0.123 .123
0.1234 0.1234 0.1234 .1234
0.12345 0.12345 0.12345 .12345
0.123456 0.123456 0.123456 .123456
0.1234567 0.1234567 0.1234567 .1234567
0.12345678 0.12345678 0.12345678 .12345678
0.123456789 0.123456789 0.123456789 .123456789
0.1234567890 0.123456789 0.123456789 .123456789
0.12345678901 0.12345678901 0.12345678901 .12345678901
0.123456789012 0.123456789012 0.123456789012 .123456789012
0.1234567890123 0.12345678901230001 0.1234567890123 .1234567890123
0.12345678901234 0.12345678901234 0.12345678901234 .12345678901234
0.123456789012345 0.123456789012345 0.123456789012345 .123456789012345
0.1234567890123456 0.12345678901234559 0.1234567890123456 .1234567890123456
0.12345678901234567 0.12345678901234566 0.12345678901234566 .12345678901234566
0.4 0.40000000000000002 0.4 .4
0.41 0.40999999999999998 0.41 .41
0.411 0.41099999999999998 0.411 .411
0.4111 0.41110000000000002 0.4111 .4111
0.41111 0.41110999999999998 0.41111 .41111
0.411111 0.411111 0.411111 .411111
0.4111111 0.41111110000000001 0.4111111 .4111111
0.41111111 0.41111111 0.41111111 .41111111
0.411111111 0.41111111099999997 0.411111111 .411111111
0.4111111111 0.41111111109999998 0.4111111111 .4111111111
0.41111111111 0.41111111110999998 0.41111111111 .41111111111
0.411111111111 0.41111111111100002 0.411111111111 .411111111111
0.4111111111111 0.41111111111109999 0.4111111111111 .4111111111111
0.41111111111111 0.41111111111110998 0.41111111111111 .41111111111111
0.411111111111111 0.41111111111111098 0.411111111111111 .411111111111111
0.4111111111111111 0.41111111111111109 0.4111111111111111 .4111111111111111
0.41111111111111111 0.41111111111111109 0.4111111111111111 .4111111111111111
0.3 0.29999999999999999 0.3 .3
0.39 0.39000000000000001 0.39 .39
0.399 0.39900000000000002 0.399 .399
0.3999 0.39989999999999998 0.3999 .3999
0.39999 0.39999000000000001 0.39999 .39999
0.399999 0.39999899999999999 0.399999 .399999
0.3999999 0.39999990000000002 0.3999999 .3999999
0.39999999 0.39999999000000003 0.39999999 .39999999
0.399999999 0.39999999899999999 0.399999999 .399999999
0.3999999999 0.39999999990000001 0.3999999999 .3999999999
0.39999999999 0.39999999999000002 0.39999999999 .39999999999
0.399999999999 0.39999999999899999 0.399999999999 .399999999999
0.3999999999999 0.39999999999989999 0.3999999999999 .3999999999999
0.39999999999999 0.39999999999998997 0.39999999999999 .39999999999999
0.399999999999999 0.39999999999999902 0.399999999999999 .399999999999999
0.3999999999999999 0.39999999999999991 0.3999999999999999 .3999999999999999
0.39999999999999999 0.39999999999999997 0.39999999999999997 .39999999999999997
And the negative of the above numbers (format="%-20s%-20.17g%-20s%-20s\n"):
-0.1 -0.10000000000000001-0.1 -.1
-0.12 -0.12 -0.12 -.12
-0.123 -0.123 -0.123 -.123
-0.1234 -0.1234 -0.1234 -.1234
-0.12345 -0.12345 -0.12345 -.12345
-0.123456 -0.123456 -0.123456 -.123456
-0.1234567 -0.1234567 -0.1234567 -.1234567
-0.12345678 -0.12345678 -0.12345678 -.12345678
-0.123456789 -0.123456789 -0.123456789 -.123456789
-0.1234567890 -0.123456789 -0.123456789 -.123456789
-0.12345678901 -0.12345678901 -0.12345678901 -.12345678901
-0.123456789012 -0.123456789012 -0.123456789012 -.123456789012
-0.1234567890123 -0.12345678901230001-0.1234567890123 -.1234567890123
-0.12345678901234 -0.12345678901234 -0.12345678901234 -.12345678901234
-0.123456789012345 -0.123456789012345 -0.123456789012345 -.123456789012345
-0.1234567890123456 -0.12345678901234559-0.1234567890123456 -.1234567890123456
-0.12345678901234567-0.12345678901234566-0.12345678901234566-.12345678901234566
-0.4 -0.40000000000000002-0.4 -.4
-0.41 -0.40999999999999998-0.41 -.41
-0.411 -0.41099999999999998-0.411 -.411
-0.4111 -0.41110000000000002-0.4111 -.4111
-0.41111 -0.41110999999999998-0.41111 -.41111
-0.411111 -0.411111 -0.411111 -.411111
-0.4111111 -0.41111110000000001-0.4111111 -.4111111
-0.41111111 -0.41111111 -0.41111111 -.41111111
-0.411111111 -0.41111111099999997-0.411111111 -.411111111
-0.4111111111 -0.41111111109999998-0.4111111111 -.4111111111
-0.41111111111 -0.41111111110999998-0.41111111111 -.41111111111
-0.411111111111 -0.41111111111100002-0.411111111111 -.411111111111
-0.4111111111111 -0.41111111111109999-0.4111111111111 -.4111111111111
-0.41111111111111 -0.41111111111110998-0.41111111111111 -.41111111111111
-0.411111111111111 -0.41111111111111098-0.411111111111111 -.411111111111111
-0.4111111111111111 -0.41111111111111109-0.4111111111111111 -.4111111111111111
-0.41111111111111111-0.41111111111111109-0.4111111111111111 -.4111111111111111
-0.3 -0.29999999999999999-0.3 -.3
-0.39 -0.39000000000000001-0.39 -.39
-0.399 -0.39900000000000002-0.399 -.399
-0.3999 -0.39989999999999998-0.3999 -.3999
-0.39999 -0.39999000000000001-0.39999 -.39999
-0.399999 -0.39999899999999999-0.399999 -.399999
-0.3999999 -0.39999990000000002-0.3999999 -.3999999
-0.39999999 -0.39999999000000003-0.39999999 -.39999999
-0.399999999 -0.39999999899999999-0.399999999 -.399999999
-0.3999999999 -0.39999999990000001-0.3999999999 -.3999999999
-0.39999999999 -0.39999999999000002-0.39999999999 -.39999999999
-0.399999999999 -0.39999999999899999-0.399999999999 -.399999999999
-0.3999999999999 -0.39999999999989999-0.3999999999999 -.3999999999999
-0.39999999999999 -0.39999999999998997-0.39999999999999 -.39999999999999
-0.399999999999999 -0.39999999999999902-0.399999999999999 -.399999999999999
-0.3999999999999999 -0.39999999999999991-0.3999999999999999 -.3999999999999999
-0.39999999999999999-0.39999999999999997-0.39999999999999997-.39999999999999997
As expected, the two implementations give the same results (apart from
the arbitrary decision of whether to display a 0 before the decimal
point).
> So, I propose to back off from the changes I proposed last week and revert
> to something very similar to what's in Tcl 7.6:
>
> - No fuzzy comparisons: all internal calculations use full precision.
Excellent.
> - When converting from floating to string, use %.12g by default, but
> support the tcl_precision variable as in Tcl 7.6 so people that need
> more precision can get it.
OK. This sounds like a good compromise. I look forward to seeing Tcl8.0.
Martin Shepherd (m...@astro.caltech.edu)
Richard A. O'Keefe
ous...@tcl.eng.sun.com (John Ousterhout) writes:
>I'm afraid the properties you long for never existed in the first place.
>Basic laws of mathematics are already broken in any floating-point
>implementation, due to the fixed precision available and the resulting
>roundoff errors.
But amongst the basic laws that are _not_ broken we find the ordering
relations. Modulo NaNs, which I would expect Tcl to catch and report
as errors (and that is allowed by the IEEE standards), the IEEE floating
point numbers, the VAX floating point numbers, the IBM/370 floating
point numbers, all form perfectly respectable total orders with well-
behaved order relations.
See the well-known book by Kulish and Miranker on computer arithmetic.
>For example, (1.4 + 0.7 - 0.6 - 0.1) won't necessarily
>equal 1.4 under normal floating-point arithmetic. This seems to contradict
>the basic laws of mathematics!
Yes. That's *WHY* trying to hide it is a bad idea.
Indeed, it's why truncating at the 12th decimal place is a truly excellent
way to make things WORSE.
Amongst other things, consider that
set a 1.4
set b 0.7
set c 0.6
set d 0.1
[expr (($a + $b) - $c) - $d]
will give one result, but
[expr [expr [expr $a + $b] - $c] - $d]
will give another, if the chopping is done as the last step of expr.
There are only two really satisfactory ways to handle floating
point arithmetic.
1. Provide _exactly_ the arithmetic of the underlying machine,
with one method of doing arithmetic and getting the most accurate
answers and another method of doing arithmetic and getting pretty
strings. You *really* don't want to be feeding prettified strings
back into arithmetic.
2. Implement decimal floating point arithmetic, so that decimals are
represented exactly and all Tcl platforms produce exactly the same
answers. I note that Pascal-XSC, a programming language designed
for experimentation with interval arithmetic, provides decimal
floating point only. This will of course be slower than native
floating point, but it _will_ be less surprising WITHOUT introducing
extra errors.
>Any floating-point system will suffer from
>some surprises like this; our goal for Tcl 8.0 is to avoid surprises in
>the simple cases.
I note that in the 1990(?) paper about Tcl, there were four major
assumptions that guided the design of Tcl. Tcl was such a wonderful
tool, and so brilliantly successful, that these assumptions were
rapidly invalidated. Any programming language where people write
10 000 line scripts doesn't need kluges that make the 'simple cases'
surprising at the price of making the slightly less simple cases
EXTREMELY surprising.
>The Tcl 8.0 approach actually makes many things (such as
>the example above) behave more intuitively than they would with "precise"
>arithmetic.
That example would do much much better with decimal floating point
(ideal if it conformed to IEEE 854), without needing _any_ such kluges.
Look, I once worked on a programming language where we swiped a bit of
precision out of floating point numbers. IT WAS A DREADFUL MISTAKE and
made life much more difficult for us later on when we had to retrofit
_proper_ floating point numbers.
>One way to think about what we've done is that we've taken the least
>significant 12 bits of floating-point numbers and turned them into guard
>bits.
Yeah, except that doesn't quite work.
>They aren't visible when you print floating-point numbers or when
>you compare them, but they participate in all internal calculations. In
>this sense they are better than the guard bits kept in hardware, which
>are fewer in number and have shorter lifetimes.
IEEE arithmetic requires 3 guard bits and that is enough to produce
best-possible approximations.
>In the worst case, the
>Tcl 8.0 approach is as good as a floating-point system with 12 decimal
>digits of precision (somewhere between single and double precision),
Dr Ousterhout, you are a *brilliant* language designer who has produced
*exactly* the tool I wanted. I now count every year when I _could_ have
learned Tcl/Tk and didn't as wasted. At last I have a programming
language for doing GUIs and stuff that is almost as simple to use as
Interlisp-D was in 1985, and with less historical baggage, it is in some
ways a lot cleaner. But I don't know anything about your numerical
analysis background. Maybe you are as fantastic at that as you are at
tool design. But I for one would _really_ like somebody of the calibre
of Kahan or Cody to comment on this scheme. So far, I have not figured
out _what_ your rounding rules are, and not knowing that, I can't tell
_what_ axioms your proposed arithmetic will satisfy (and there are quite
a lot of axioms that VAX and IEEE floating point do satisfy, very useful
ones), and without knowing that, I don't know _what_ surprises there will
be. If you have actually managed to figure out a way of chopping back
floating number numbers so as to produce simple decimal approximations
AND reduce surprises, then that's a major breakthrough, and you deserve
another earned PhD.
One thing I do know is that with your fuzzy comparisons, sorting WILL be
extremely surprising. Not may be, WILL be. Have you studied the APL2
draft standard? I believe it's still available on-line (which is where
I got my copy). APL provides *user-settable* comparison tolerance, set
by
)FUZZ ct
or []CT <- ct
and the user can select no fuzz. Because of comparison tolerance, the
APL sorting primitives (grade up and grade down) are not simply related
to the comparison primitives. And that relationship is usually _why_
one sorts.
--
Four policemen playing jazz on an up escalator in the railway station.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.
Martin Shepherd
o...@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes:
> LYING to the users is ALWAYS wrong.
> If you really want to eliminate surprises of this sort, the only
> honest way to do it is to provide decimal floating point.
Maybe so, but by doing so you would loose compatibility with C
doubles. That would be a distaster for those of us who use Tcl as a
user-interface glue language for their C programs.
Martin Shepherd (m...@astro.caltech.edu)
Richard A. O'Keefe
Laurent Demailly <Laurent....@sun.com> writes:
>Instead I painfully learned to use comparison within a relative
>+/-epsilon range, if I understand well John proposal, it is to make
>the common programmers' life easy by doing that *necessary* epsilon
>fuzzy comparison for them in TCL, which to me seems a really good thing.
>(and not only because John is my boss :p)
Yeah, but the problem is that the right value for epsilon depends
very strongly on what you are doing. There is *NO* fixed value of
epsilon that will be right for all uses. This is why APL's fuzzy
comparions are based on a USER-SETTABLE comparison tolerance.
Has anyone else here used VM/PROLOG? It had the property of using
fuzzy comparison. It was very unfortunate, because comparing things
for equality is _essential_ in a logic programming language. Things
*BROKE* in mysterious ways.
>If you still want your comparison to fail randomly (which is
>a real bug source IMO) because of roundoff errors but getting
In any reasonable floating point arithmetic, there is a large set
of numbers (integer/power of two, for a rather wide range of
numerator) where +, -, and * are exact. Indeed, if I want to count
more than 2**31 things, it makes perfect sense for me to put the
number in a C double, increment and decrement by 1.0, AND TO USE
== TO TEST FOR EQUALITY, because within this range and for this set
of operations there *ISN'T ANY* roundoff error. If, on the other
hand, you steal 12 bits out of the numbers, you chop the useful
portable-across-PC/Mac/modern-UNIX-platform range of intgers from
+/- 2**53 (15 digits) to +/- 2**41 (12 digits).
The IEEE standard and the C standard provide exact remainder
operations, so it is perfectly possible to implement 'div' and 'mod'
for these numbers as well.
For non-IEEE arithmetics, the range of numbers where this works is
typically smaller, but not a lot smaller. In the absence of guaranteed
64-bit integer arithmetic, using doubles to count with is a useful and
guaranteed safe technique, AS LONG AS THE COMPARISON OPERATORS ARE NOT
TAMPERED WITH.
>I would like to see an example of something that would break
>with the new scheme, not just theoretical objections (which are
>valid, but just don't apply I think) : ie the scheme is not
>"beautiful" to our mathematical mind but it sure does help a
>lot the poor programmer stuck on a computer using a fixed and finite
>number of bits for "real" numbers.
Four things have been mentioned so far.
1. The link between sorting and comparison will be snapped.
2. The built in comparison tolerance will be WRONG most of the time.
3. Doubles _can_ safely be used to get 'wider' integers that work
*perfectly*, but that will break if comparison is tampered with.
4. Passing scientific data through TCL will introduce errors.
This will make things likt BLT significantly less attractive.
>> Consider one possible scenario: procedures A1 finds that x1 == x2,
>> and passes x2 to A2 which finds x2 == x3 and passes x3 on to A3
>> and so on. At the end of this chain, there is a reasonable
>> expectation that xn == x1 in procedure An but may not in fact be
>> the case.
>If you use an == like in C, procedure A1 would have a random
>result (because round off errors)
Wrong. Anyone who talks about 'random' in this context obviously
doesn't have a clue about floating point arithmetic. == in floating
point arithmetic *is* transitive and *does* have safe uses.
>I think that the experienced programmers will be happy to
>see that they don't have to re-implement epsilon floating
>point numbers comparison and that it's part of the language.
As an experienced programmer who took a fair amount of numerical
analysis, let me tell you, *NO*. I will simply draw the conclusion
"I dare not trust my numbers to Tcl."
Note: there is absolutely no reason why fuzzy comparison couldn't be
ADDED to the language WITHOUT breaking anything. Simply have
fuzzy -fuzz => report the current fuzz
fuzzy -fuzz X => set the fuzz to X, report old fuzz
fuzzy E1 R E2 => => test if E1 R E2 (with set fuzz)
fuzzy E1 R E2 -fuzz X => test if E1 R E2 (with fuzz X)
Also note that you need TWO versions of fuzzy equality if you are going
to take it seriously. See Knuth volume 2.
>And I think inexperienced programmers will enjoy that
>working on floating points will behave like they could innocently
>expect.
There is no such animal.
The closest you could get to that would be to implement decimal floating
point, which could indeed be done.
>because it is not only programmers
>but also *users* that are are going to write small piece of Tcl
>code (like set v [expr $v+.1] ; if {$v == 1.1 } ... and those guys
>really don't event want to hear about why the true result
>is 1.1000000000000001 for v=1, they really want to see 1.1 !)
LYING to the users is ALWAYS wrong.
If you really want to eliminate surprises of this sort, the only
honest way to do it is to provide decimal floating point.
--
Martin Shepherd
Tom Lane <t...@netcom.com> writes:
> Martin Shepherd <m...@goblin.caltech.edu> writes:
> > ous...@tcl.eng.sun.com (John Ousterhout) writes:
> >> [Does Paul Eggert's algorithm behave the same as Steele&White?]
>
> > As expected, the two implementations give the same results (apart from
> > the arbitrary decision of whether to display a 0 before the decimal
> > point).
>
> However, it should be noted that Paul's method depends on the correctness
> of the local C library's implementation of both printing and reading
> floats.
True, but you could say that about a lot of other parts of Tcl that
rely on the sanity of the C library. If a C library is that broken,
then you will probably have more problems than strange looking
numbers.
>...
> The only real objection to S&W is that it would bulk up the Tcl
> distribution a little more ... but Tcl is already a pretty large
> package, and S&W isn't that much more code.
Agreed. David Gay's free implementation is self contained and only
2810 lines in total. I don't see anything in its copyright notice that
would prevent Sun from including it in Tcl.
> IIRC, Paul recommended his method only as an easy-to-implement
> substitute for S&W. Since we're no longer talking about trying
> to shoehorn a quick answer into Tcl 8.0, it seems to me that there
> is enough time and reason to Do It Right for 8.1.
I personally don't mind one way or the other, but obviously the more
efficient and portable method would be preferable in the long
run. Unfortunately, it isn't clear to me which method actually
satisfies these goals.
To get some idea of the relative speeds of the algorithms I did a
simple test on a quiescent Sparc Ultra 1, running Solaris 2.5.1. I
compiled both S&W implementations with the same optimization level
(-O), then wrote a main() function that formatted a specified number
10000 times, first using sprintf(%.17g), then using David Gay's
g_fmt(), and finally using Paul Eggert's convertDoubleToString(). I
bracketed each loop with calls to clock() and used this to determine
the elapsed cpu time per formatting call. Some results are shown
below. Times are in microseconds:
The that was formatted. sprintf(%.17g) DoubleToString() g_fmt()
0 6 6 2
1 35 24 4
2 16 19 4
3 16 19 4
0.4 56 20 13
0.3 57 21 11
0.399 57 21 22
0.3999 57 21 26
0.399999 57 21 36
0.39999999 59 25 45
0.3999999999 57 25 56
0.399999999999 57 24 67
0.39999999999999 57 25 78
0.399999999999999 57 25 85
0.3999999999999999 57 108 89
0.39999999999999999 57 133 96
The above results are obviously specific to the platform that I ran
the test on, but they do show that the choice of algorithm isn't quite
as obvious as one might expect. In this case, g_fmt() is faster than
ConvertDoubleToString() for integers, and for numbers with more than
15 significant figures. ConvertDoubleToString() is significantly
faster than g_fmt() for numbers with between 6 and 15 significant
figures. Both techniques are significantly slower than %.17g for
numbers that require more than 15 significant figures.
Martin Shepherd (m...@astro.caltech.edu)
Tom Lane
Martin Shepherd <m...@goblin.caltech.edu> writes:
> ous...@tcl.eng.sun.com (John Ousterhout) writes:
>> [Does Paul Eggert's algorithm behave the same as Steele&White?]
> As expected, the two implementations give the same results (apart from
> the arbitrary decision of whether to display a 0 before the decimal
> point).
However, it should be noted that Paul's method depends on the correctness
of the local C library's implementation of both printing and reading
floats. I'd feel a lot more comfortable with a self-contained S&W
subroutine. Getting the same behavior on all platforms would be
more probable IMHO.
The only real objection to S&W is that it would bulk up the Tcl
distribution a little more ... but Tcl is already a pretty large
package, and S&W isn't that much more code.
IIRC, Paul recommended his method only as an easy-to-implement
substitute for S&W. Since we're no longer talking about trying
to shoehorn a quick answer into Tcl 8.0, it seems to me that there
is enough time and reason to Do It Right for 8.1.
regards, tom lane
Viktor Dukhovni
>As expected, the two implementations give the same results (apart from
>the arbitrary decision of whether to display a 0 before the decimal
>point).
And Paul's alogorithm is portable, hence it should it implemented
as soon as practical. Whether this is 8.0 or 8.0p1 or 8.1 is up to the
Sun team I guess...
>> - When converting from floating to string, use %.12g by default, but
>> support the tcl_precision variable as in Tcl 7.6 so people that need
>> more precision can get it.
>OK. This sounds like a good compromise. I look forward to seeing Tcl8.0.
Actually I find the back peddaling on tcl_precision surprising,
John gave very good reasons why tcl_precision is a bad idea, and they
still apply. If full precision is used in arithmetic operations and
comparisons why not in string conversion.
If [expr {1.1 + 0.1 == 1.2}] is false, why should
expr {1.1 + 0.1} print as 1.2. It only seems to add confusion. Why
can't we have the old 8.0b2 behaviour if it is too late for Paul's proposal.
--
Viktor.
Paul Eggert
Tom Lane <t...@netcom.com> writes:
>As the [Steele&White] paper pointed out, *lots* of standard
>libraries fail to print or read floats with full accuracy.
Yes, and there's an entertaining table in the Burger and Dybvig paper.
They tested the double-to-text conversion of several major Unix variants.
Four variants (Digital Unix V3.2C, HP-UX A.09.05, IRIX 5.3, and IRIX64
6.1) were fast but buggy; three (Linux 1.3.32, SunOS 4.1.3, and SunOS
5.5) had no apparent bugs but were slow; and only one (AIX 3.2) was
both fast and apparently bug-free. IBM has had a lot of experience
with floating-point....
>Few people would tolerate a C library whose qsort() sometimes didn't
>sort correctly. But a printf() or atof() that sometimes gets the
>low order digits wrong is much less likely to be noticed, let alone
>fixed promptly.
Perhaps; but if people don't care about low-order-digit bugs in printf
or atof, they won't care about any bugs in the code I'm proposing
either, since it will be buggy only in the same low-order digits.
Bob De Wolf
Richard A. O'Keefe wrote:
>
> There are only two really satisfactory ways to handle floating
> point arithmetic.
>
> 1. Provide _exactly_ the arithmetic of the underlying machine,
> with one method of doing arithmetic and getting the most accurate
> answers and another method of doing arithmetic and getting pretty
> strings. You *really* don't want to be feeding prettified strings
> back into arithmetic.
>
Makes perfect sense to me. Therefore, since the underlying machine
works in binary, expr should return a binary representation of the
floating point number. For example: dbl:<hex value>. When subsequent
expr commands interpret this string they get the exact result produced
by the previous expr. When format is used, it too can convert the
number properly.
But what if the programmer outputs the number without formatting? For
example:
puts "$num"
He gets that awfull hex value. Maybe there is a way around this.
Tom Lane
Martin Shepherd <m...@goblin.caltech.edu> writes:
> Tom Lane <t...@netcom.com> writes:
>> However, it should be noted that Paul's method depends on the correctness
>> of the local C library's implementation of both printing and reading
>> floats.
> True, but you could say that about a lot of other parts of Tcl that
> rely on the sanity of the C library. If a C library is that broken,
> then you will probably have more problems than strange looking
> numbers.
I beg to differ. As the S&W paper pointed out, *lots* of standard
libraries fail to print or read floats with full accuracy. The state
of practice hasn't improved much since then, for some reason :-(.
Few people would tolerate a C library whose qsort() sometimes didn't
sort correctly. But a printf() or atof() that sometimes gets the
low order digits wrong is much less likely to be noticed, let alone
fixed promptly.
BTW, thanks for the info on relative speeds. Quite interesting.
regards, tom lane
Donal K. Fellows
[ I'm not quite sure where the best place to insert my comments on all
this in this thread are - let's try here ]
Having thought about this issue, the property that I want preserved
above _all_ others (i.e. no matter what the cost to the novice
programmer) is that if I have a C double, pass it through Tcl where it
gets converted to a string for internal reasons, and then convert it
back to a double, I should get _exactly_ the same bit pattern (for
non-exceptional values - someone who knows more than me about
infinities and NaNs caan say what is best there :^)
Like this, I'd be able to expect the following code to give the
obvious result:
proc foo {args} {expr {[lindex $args 0]-sqrt(3)}}
set bar [expr sqrt(5)]
puts [expr {[foo $bar x] - [eval foo "$bar x"]}]
I shouldn't get different results (Assuming that I've got the quoting
right)from the same routine depending on whether I call it with eval
or not! If this isn't true, then one of the major principles of Tcl
has just been completely violated.
What happens in [format ...] is wholly unconnected with this.
Donal.
--
Donal K. Fellows http://r8h.cs.man.ac.uk:8000/ (SAY NO TO COMMERCIAL SPAMS!)
fello...@man.ac.uk Dept. Comp. Sci, Univ. Manchester, U.K. +44-161-275-6137
The at symbol in my email address may have been shifted one word right
to deter spam-bots. Sorry for any inconvenience this causes you.
Paul Eggert
Here's a patch to Tcl 8.0 that implements the Steele & White idea
that I suggested earlier:
When converting a double value to a string,
convert to the smallest number of digits such that
converting back to double yields the original value again.
I suggested this too late for inclusion in Tcl 8.0,
but I hope the idea can be used into a later release.
Unlike the code sketch I posted earlier, this patch is fully integrated
with Tcl, is portable to pre-ANSI-C compilers and hosts without <math.h>,
and comes with documentation. If you set tcl_precision to 0, you get
the new behavior. (Also, tcl_precision now defaults to 0.)
This patch also fixes a bug with printing small numbers that
I reported earlier.
===================================================================
RCS file: doc/tclvars.n,v
retrieving revision 8.0
retrieving revision 8.0.0.1
diff -c -r8.0 -r8.0.0.1
*** doc/tclvars.n 1997/08/14 15:37:55 8.0
--- doc/tclvars.n 1997/08/18 06:18:29 8.0.0.1
***************
*** 273,285 ****
.VS
This variable controls the number of digits to generate
when converting floating-point values to strings. It defaults
! to 12.
! 17 digits is ``perfect'' for IEEE floating-point in that it allows
double-precision values to be converted to strings and back to
! binary with no loss of information. However, using 17 digits prevents
! any rounding, which produces longer, less intuitive results. For example,
\fBexpr 1.4\fR returns 1.3999999999999999 with \fBtcl_precision\fR
! set to 17, vs. 1.4 if \fBtcl_precision\fR is 12.
.RS
All interpreters in a process share a single \fBtcl_precision\fR value:
changing it in one interpreter will affect all other interpreters as
--- 273,288 ----
.VS
This variable controls the number of digits to generate
when converting floating-point values to strings. It defaults
! to 0, which means to generate the fewest number of digits such
! that converting the string back to floating-point yields the
! original number. If it is set to a positive value, exactly
! that many digits are generated.
! 17 digits is also ``perfect'' for IEEE floating-point in that it allows
double-precision values to be converted to strings and back to
! binary with no loss of information. However, using 17 digits can generate
! noise digits, which produces longer, less intuitive results. For example,
\fBexpr 1.4\fR returns 1.3999999999999999 with \fBtcl_precision\fR
! set to 17, vs. 1.4 if \fBtcl_precision\fR is 0.
.RS
All interpreters in a process share a single \fBtcl_precision\fR value:
changing it in one interpreter will affect all other interpreters as
===================================================================
RCS file: generic/tclUtil.c,v
retrieving revision 8.0
retrieving revision 8.0.0.1
diff -c -r8.0 -r8.0.0.1
*** generic/tclUtil.c 1997/08/13 00:07:17 8.0
--- generic/tclUtil.c 1997/08/18 06:18:29 8.0.0.1
***************
*** 16,21 ****
--- 16,68 ----
#include "tclInt.h"
#include "tclPort.h"
+ #ifdef TCL_NO_MATH
+ # define fabs(x) ((x)<0 ? -(x) : (x))
+ #else
+ # include "tclMath.h"
+ #endif
+
+ /* The C Standard says that <float.h> must define DBL_DIG,
+ DBL_MANT_DIG, DBL_MIN, and FLT_RADIX. On platforms that don't
+ conform to the C Standard, guess IEEE. */
+
+ #ifndef NO_FLOAT_H
+ #include <float.h>
+ #endif
+
+ #ifndef DBL_DIG
+ #define DBL_DIG 15
+ #endif
+ #ifndef DBL_MANT_DIG
+ #define DBL_MANT_DIG 53
+ #endif
+ #ifndef DBL_MIN
+ #define DBL_MIN 2.2250738585072014e-308
+ #endif
+ #ifndef FLT_RADIX
+ #define FLT_RADIX 2
+ #endif
+
+ /*
+ * Define an upper bound on the number of decimal digits needed to
+ * express a float without losing information.
+ */
+ #if FLT_RADIX == 2 && DBL_MANT_DIG == 53
+ /* The usual case: IEEE floating point. */
+ # define DOUBLE_DIGITS_BOUND 17
+ #else
+ #ifdef TCL_NO_MATH
+ /* A very sloppy but valid bound. */
+ # define DOUBLE_DIGITS_BOUND (2 * DBL_DIG)
+ #else
+ /*
+ * The general case. We'd prefer to use this formula always,
+ * but many compilers can't optimize it to an integer constant.
+ */
+ # define DOUBLE_DIGITS_BOUND ((int) ceil(log10(pow(FLT_RADIX, DBL_MANT_DIG))))
+ #endif
+ #endif
+
/*
* The following values are used in the flags returned by Tcl_ScanElement
* and used by Tcl_ConvertElement. The value TCL_DONT_USE_BRACES is also
***************
*** 46,57 ****
* NOTE: these variables are not thread-safe.
*/
! static char precisionString[10] = "12";
/* The string value of all the tcl_precision
* variables. */
! static char precisionFormat[10] = "%.12g";
! /* The format string actually used in calls
! * to sprintf. */
/*
--- 93,105 ----
* NOTE: these variables are not thread-safe.
*/
! static char precisionString[10] = "0";
/* The string value of all the tcl_precision
* variables. */
! static char precisionFormat[10] = "";
! /* Empty if precisionString is zero;
! * otherwise, the format string actually
! * used in calls to sprintf. */
/*
***************
*** 2458,2464 ****
{
char *p;
! sprintf(dst, precisionFormat, value);
/*
* If the ASCII result looks like an integer, add ".0" so that it
--- 2506,2525 ----
{
char *p;
! if (*precisionFormat) {
! sprintf(dst, precisionFormat, value);
! } else {
! /*
! * Convert using the minimum number of digits that do not lose info.
! * We could just start by trying 1 digit and working our way up,
! * but this is slow. If the number is normalized,
! * start with DBL_DIG digits, since this won't generate extra digits.
! */
! int digits = fabs(value) < DBL_MIN ? 1 : DBL_DIG;
! do {
! sprintf(dst, "%.*g", digits, value);
! } while (digits++ < DOUBLE_DIGITS_BOUND && atof(dst) != value);
! }
/*
* If the ASCII result looks like an integer, add ".0" so that it
***************
*** 2551,2564 ****
value = "";
}
prec = strtoul(value, &end, 10);
! if ((prec <= 0) || (prec > TCL_MAX_PREC) || (prec > 100) ||
(end == value) || (*end != 0)) {
Tcl_SetVar2(interp, name1, name2, precisionString,
flags & TCL_GLOBAL_ONLY);
return "improper value for precision";
}
TclFormatInt(precisionString, prec);
! sprintf(precisionFormat, "%%.%dg", prec);
return (char *) NULL;
}
--- 2612,2629 ----
value = "";
}
prec = strtoul(value, &end, 10);
! if ((prec < 0) || (prec > TCL_MAX_PREC) || (prec > 100) ||
(end == value) || (*end != 0)) {
Tcl_SetVar2(interp, name1, name2, precisionString,
flags & TCL_GLOBAL_ONLY);
return "improper value for precision";
}
TclFormatInt(precisionString, prec);
! if (prec == 0) {
! precisionFormat[0] = 0;
! } else {
! sprintf(precisionFormat, "%%.%dg", prec);
! }
return (char *) NULL;
}
lvi...@cas.org
According to <B.Ste...@isode.com>:
:In article <ramEEt...@netcom.com>,
: r...@netcom.com (Munagala V. S. Ramanath) wrote:
:
:> As a general principle, I would suggest casting a sceptical eye
:> upon any idea that causes divergence from C/C++ behaviour. This is
:> not to say that that behaviour is ideal and that variances should
:
:A skeptical eye, certainly, but such changes shouldn't be ruled out. The
I would think there would be room for the following. Have the core
remain as true to C as possible - both for promoting the movement of
code _to C_ and in support of the wrapping of legacy C libraries into
Tcl commands. However, some of the folk here who have passionate needs
for alternate floating point representation could develop an extension
to provide a new kind of Tcl floating point data variable type, which
then could provide those needing unique representations the means to
obtain this alternate but valid behavior.
:easier change would be to allow complex floating point numbers. That
:would be nice for some people.
Indeed, having a nice arbitrary digit size math package for the folk
who are trying to do something funky in Tcl would be nice, though
I can't imagine why someone would be doing numeric analysis in Tcl -
perhaps under Tcl 8 it becomes more cost effective...
--
Larry W. Virden INET: lvi...@cas.org
<URL:http://www.teraform.com/%7Elvirden/> <*> O- "We are all Kosh."
Unless explicitly stated to the contrary, nothing in this posting should
be construed as representing my employer's opinions.
Paul Eggert
fell...@cs.man.ac.uk (Donal K. Fellows) writes:
> proc foo {args} {expr {[lindex $args 0]-sqrt(3)}}
> set bar [expr sqrt(5)]
> puts [expr {[foo $bar x] - [eval foo "$bar x"]}]
> I shouldn't get different results from the same routine
> depending on whether I call it with eval or not!
In Tcl 8.0, you unfortunately do get different results: even though
`foo $bar x' and `eval foo "$bar x"' yield the same string (namely
0.504017169931, assuming IEEE floating point), their internal values
differ, and `puts' outputs -2.10054196259e-13.
However, with the Steele&White-inspired floating point patch for Tcl
8.0 that I posted yesterday in <news:5t8rbk$sue$1...@shade.twinsun.com>,
both expressions yield the string 0.5040171699309126. This string has
all the information present in the internal value, and `puts' outputs
0.0 as expected.
Munagala V. S. Ramanath
lvi...@cas.org writes:
>Indeed, having a nice arbitrary digit size math package for the folk
>who are trying to do something funky in Tcl would be nice, though
There are free libraries available to handle the basic arithmetic. For
example, a rather nice one that uses some fast algorithms is the 'calc'
package by David I. Bell (db...@canb.auug.org.au) comes as part of a
'calculator' package but the library is usable on its own as well (last
I heard it was on ftp.uu.net/pub/calc). Note that this 'calc' is not to
be confused with the emacs 'calc' written in elisp by Dave Gillespie.
Someone just needs to do the integration with TCL.
Ram
Dr Bruce Stephens
lvi...@cas.org writes:
> According to <B.Ste...@isode.com>:
> :In article <ramEEt...@netcom.com>,
> :easier change would be to allow complex floating point numbers. That
> :would be nice for some people.
>
> Indeed, having a nice arbitrary digit size math package for the folk
> who are trying to do something funky in Tcl would be nice, though
> I can't imagine why someone would be doing numeric analysis in Tcl -
> perhaps under Tcl 8 it becomes more cost effective...
I think it would probably be daft. On the other hand, using languages
for prototyping is common, and there's surely potential for complex
numbers, if not arbitrary precision arithmetic, in Tk.