Any way to correct the round off errors?

[G.S.-2]

Hello everyone,

When subtracting in Erlang: 0.92915-0.92945 we should get -0.0003 but Erlang
gives: -2.9999999999996696e-4   (when doing 92915-92945 Erlang gives -30 so
that's ok).

Anyway to make make it give -0.0003 ?, and in general make it give more
accurate answers?

Regards,
-Gene

[Jayson Vantuyl-2]

For the record, I just tested the same math in Python and Ruby.  Same  
result.  Java probably would as well.  They all represent real numbers  
as IEEE 754 floating point numbers.

The error you're seeing is because the fractions are represented as  
binary fractions.  The only way you're going to get "precise" numbers  
is to use fixed-point arithmetic.

Keep in mind that accurate is in the eye of the beholder.  While you  
want to represent 3/10000 (which would be more accurate with base-10  
fixed point arithmetic), if you wanted something more like 1/65536,  
floating point would be dead-on accurate, but fixed point base-10  
would have error.

Here's a partial discussion that may be of use.  I probably should put  
implementing a decimal module on my list of things to do, though,  
because this is hardly a solved problem (and would be extra useful for  
handling money values).

http://www.trapexit.org/forum/viewtopic.php?p=44093

On Sep 20, 2009, at 4:35 AM, G.S. wrote:

> Hello everyone,
>
> When subtracting in Erlang: 0.92915-0.92945 we should get -0.0003  
> but Erlang
> gives: -2.9999999999996696e-4   (when doing 92915-92945 Erlang gives  
> -30 so
> that's ok).
>
> Anyway to make make it give -0.0003 ?, and in general make it give  
> more
> accurate answers?
>
> Regards,
> -Gene

--
Jayson Vantuyl
[hidden email]

[Lev Walkin]

G.S. wrote:
> Hello everyone,
>
> When subtracting in Erlang: 0.92915-0.92945 we should get -0.0003 but Erlang
> gives: -2.9999999999996696e-4   (when doing 92915-92945 Erlang gives -30 so
> that's ok).
>
> Anyway to make make it give -0.0003 ?, and in general make it give more
> accurate answers?

Your computer hardware cannot represent 0.0003.

[vlm@nala:~]> cc -o c c.c && ./c
-0.000300
-0.00029999999999999997
[vlm@nala:~]> cat c.c
#include <stdio.h>

int main() {
        double d = -0.0003;
        printf("%f\n", d);
        printf("%.20f\n", d);
}
[vlm@nala:~]>


So, Erlang does not give you less accurate numbers.
Erlang just gives you a differently formatted decimal
representation of a binary number which can't be 0.0003.

--
vlm

________________________________________________________________
erlang-questions mailing list. See http://www.erlang.org/faq.html
erlang-questions (at) erlang.org

[Zoltan Lajos Kis]

Lev Walkin wrote:

> G.S. wrote:
>> Hello everyone,
>>
>> When subtracting in Erlang: 0.92915-0.92945 we should get -0.0003 but
>> Erlang
>> gives: -2.9999999999996696e-4   (when doing 92915-92945 Erlang gives
>> -30 so
>> that's ok).
>>
>> Anyway to make make it give -0.0003 ?, and in general make it give more
>> accurate answers?
>
> Your computer hardware cannot represent 0.0003.
>
> [vlm@nala:~]> cc -o c c.c && ./c
> -0.000300
> -0.00029999999999999997
> [vlm@nala:~]> cat c.c
> #include <stdio.h>
>
> int main() {
>     double d = -0.0003;
>     printf("%f\n", d);
>     printf("%.20f\n", d);
> }
> [vlm@nala:~]>
>
>
> So, Erlang does not give you less accurate numbers.
> Erlang just gives you a differently formatted decimal
> representation of a binary number which can't be 0.0003.
>

It's not the computer hardware, but the representation used for floating
point numbers...
You can come up with your own library of arithmetic functions where you
represent decimals as you wish. Of course you will have to trade
performance for the desired accuracy. Java for example has BigDecimals
for this cause:

 >java Zed
-0.00030

-------------

import java.math.BigDecimal;

class Zed {
  public static void main(String[] args) {
    BigDecimal x = new BigDecimal("0.92915");
    BigDecimal y = new BigDecimal("0.92945");

    System.out.println( x.subtract(y) );
  }
}



________________________________________________________________
erlang-questions mailing list. See http://www.erlang.org/faq.html
erlang-questions (at) erlang.org

[Richard Kelsall]

> When subtracting in Erlang: 0.92915-0.92945 we should get -0.0003 but Erlang
> gives: -2.9999999999996696e-4   (when doing 92915-92945 Erlang gives -30 so
> that's ok).
>
> Anyway to make make it give -0.0003 ?, and in general make it give more
> accurate answers?

That's an interesting question. The other replies tell us it's a 64 bit
Double floating point representation :

http://en.wikipedia.org/wiki/Double_precision_floating-point_format

which has, according to Wikipedia, "about 16 decimal digits" of
precision from the 52 bits. Their example is correct up to 16 digits :

0.33333333333333331482
                  *
   1234567890123456

but yours is only correct up to 13 digits :

2.9999999999996696e-4
              *
1 234567890123456

so we probably shouldn't trust more than 12 digits of precision because
each calculation will lose some precision from the end of the number.
Different calculations will lose different amounts of precision and
very long sequences of calculations could reduce the number of correct
digits below 12.

You might think it would be nice to have every calculation keep a record
in the double of how many digits we can trust. If we did this the output
routine could give the exact answer to your calculation. But this would
be very difficult to calculate and would consume processor power at
every step. So instead floating point routines rely on the programmer
to know about floating point accuracy and you always have to round the
output appropriately. If you round that answer to 12 digits it is
exactly correct.

In general always use a number representation that can cope with numbers
much bigger and with much more accuracy than you are expecting because
bugs in this area are nasty.


Richard.



________________________________________________________________
erlang-questions mailing list. See http://www.erlang.org/faq.html
erlang-questions (at) erlang.org

[Witold Baryluk]

Dnia 2009-09-20, nie o godzinie 15:02 +0100, Richard Kelsall pisze:

> > When subtracting in Erlang: 0.92915-0.92945 we should get -0.0003 but Erlang
> > gives: -2.9999999999996696e-4   (when doing 92915-92945 Erlang gives -30 so
> > that's ok).
> >
> > Anyway to make make it give -0.0003 ?, and in general make it give more
> > accurate answers?
>
> That's an interesting question. The other replies tell us it's a 64 bit
> Double floating point representation :
>
> http://en.wikipedia.org/wiki/Double_precision_floating-point_format
>
> which has, according to Wikipedia, "about 16 decimal digits" of
> precision from the 52 bits. Their example is correct up to 16 digits :
>
> 0.33333333333333331482
>                   *
>    1234567890123456
>
> but yours is only correct up to 13 digits :
>
> 2.9999999999996696e-4
>               *
> 1 234567890123456

Wikipedia says that it have about 16 decimal digits (52 or 53 binary
digits), but it says nothing about how many of them are correct.
Information about 16 digits is only providad because ie. printing more
than 16 decimal digits doesn't provide any more information (rest of
digits after 53 is just zeros, and after converting them to decimal they
just some "random" digits, completly insignificant [after converting
back to binary they are smaller than 2^-53 anyway, so efectively 0.0).

>
> so we probably shouldn't trust more than 12 digits of precision because
> each calculation will lose some precision from the end of the number.
Substraction (and addition) can lose  any number of digits you wish.


> Different calculations will lose different amounts of precision and
> very long sequences of calculations could reduce the number of correct
> digits below 12.
Yep.

> You might think it would be nice to have every calculation keep a record
> in the double of how many digits we can trust.
It is called interval methods. They are very robust. Can be connected
with other techniques for fast and accurate (with 100% certainity)
calculations.

>  If we did this the output
> routine could give the exact answer to your calculation. But this would
> be very difficult to calculate and would consume processor power at
> every step. So instead floating point routines rely on the programmer
> to know about floating point accuracy and you always have to round the
> output appropriately. If you round that answer to 12 digits it is
> exactly correct.
>
> In general always use a number representation that can cope with numbers
> much bigger and with much more accuracy than you are expecting because
> bugs in this area are nasty.

It all depends what you want. Floating point number are just tricky.

both 0.92915 and 0.92945 are already not representable as binary
floating point numbers:

> io:format("~.30f~n", [0.92915]).
0.929150000000000031442000000000
>
5> io:format("~.30f~n", [0.92945]).
0.929449999999999998401000000000
ok



If you want something which calculates correctly in decimal number, use
integers multiplied with some 10^k power. It is called fixed point
arithmetic.


--
Witold Baryluk

[Masklinn]

On 20 Sep 2009, at 17:22 , Witold Baryluk wrote:
>
> If you want something which calculates correctly in decimal number,  
> use
> integers multiplied with some 10^k power. It is called fixed point
> arithmetic.
Or use a decimal floating-point library such as gmp.

________________________________________________________________
erlang-questions mailing list. See http://www.erlang.org/faq.html
erlang-questions (at) erlang.org

[Richard Kelsall]

Witold Baryluk wrote:
>> so we probably shouldn't trust more than 12 digits of precision because
>> each calculation will lose some precision from the end of the number.
> Substraction (and addition) can lose  any number of digits you wish.
>
I would be horrified if I added two doubles

0.111111111111 +
0.111111111111

and got

0.225745048327

I have no idea what the IEEE standard specifies, but I can't imagine
anybody ever implementing or using a version that gave this answer.
I would expect at least twelve significant digits of precision.

0.2222222222228765767

But if I added these two doubles

0.111111111111 +
0.000000000000111111111111

I wouldn't be surprised to get

0.111111111111343786587698

which gives the right answer to 12 significant digits, but loses all
of the significant digits in the second number.The same for subtraction.


Richard.

________________________________________________________________
erlang-questions mailing list. See http://www.erlang.org/faq.html
erlang-questions (at) erlang.org

[Witold Baryluk]

Dnia 2009-09-20, nie o godzinie 18:06 +0200, Masklinn pisze:
> On 20 Sep 2009, at 17:22 , Witold Baryluk wrote:
> >
> > If you want something which calculates correctly in decimal number,  
> > use
> > integers multiplied with some 10^k power. It is called fixed point
> > arithmetic.
> Or use a decimal floating-point library such as gmp.

Sure. But considering that Erlang already have arbitrary precision
integers, writing few functions for add/sub/mul/div isn't very hard :)
It will be more portable than linking to gmp, :) Still operations will
need to be called explicitly, because Erlang doesn't have operator
overloading. ;)


--
Witold Baryluk

[Witold Baryluk]

Dnia 2009-09-20, nie o godzinie 17:08 +0100, Richard Kelsall pisze:

> Witold Baryluk wrote:
> >> so we probably shouldn't trust more than 12 digits of precision because
> >> each calculation will lose some precision from the end of the number.
> > Substraction (and addition) can lose  any number of digits you wish.
> >
> I would be horrified if I added two doubles
>
> 0.111111111111 +
> 0.111111111111
>
> and got
>
> 0.225745048327
>
> I have no idea what the IEEE standard specifies, but I can't imagine
> anybody ever implementing or using a version that gave this answer.
> I would expect at least twelve significant digits of precision.
>
> 0.2222222222228765767
>
> But if I added these two doubles
>
> 0.111111111111 +
> 0.000000000000111111111111
>
> I wouldn't be surprised to get
>
> 0.111111111111343786587698
>
> which gives the right answer to 12 significant digits, but loses all
> of the significant digits in the second number.The same for subtraction.
>
>
> Richard.

Maybe i written not clearly. I was thinking more about such situation:

> 0.111111111111 - 0.111111111113.
-1.9999973899231804e-12
-0.000000000001999997389923180435
>

It have only one correct significant decimal digit.


--
Witold Baryluk

[Richard Kelsall]

Witold Baryluk wrote:
> Maybe i written not clearly. I was thinking more about such situation:
>
>> 0.111111111111 - 0.111111111113.
> -1.9999973899231804e-12
> -0.000000000001999997389923180435
>
> It have only one correct significant decimal digit.
>

You are quite right. I hadn't thought of that one.


Richard.

________________________________________________________________
erlang-questions mailing list. See http://www.erlang.org/faq.html
erlang-questions (at) erlang.org

[Masklinn]

On 20 Sep 2009, at 18:12 , Witold Baryluk wrote:

> Dnia 2009-09-20, nie o godzinie 18:06 +0200, Masklinn pisze:
>> On 20 Sep 2009, at 17:22 , Witold Baryluk wrote:
>>> If you want something which calculates correctly in decimal number,
>>> use
>>> integers multiplied with some 10^k power. It is called fixed point
>>> arithmetic.
>> Or use a decimal floating-point library such as gmp.
>
> Sure. But considering that Erlang already have arbitrary precision
> integers, writing few functions for add/sub/mul/div isn't very hard :)

Arbitrary precision integers are quite different beasts (and easier to  
handle) than arbitrary precision floats. Most languages with native  
arbitrary precision integers (python, ruby, Haskell's Integer type, …)  
tend to relegate arbitrary precision floats to libraries, either  
stdlib or third-party, and pretty much systematically rely on IEEE754  
floating-points natively (though they might have fraction types  
between integer and reals).

> It will be more portable than linking to gmp, :)
Not necessarily (gmp is quite damn portable), and it would be much  
harder to handle correctly. FWIW, Python's decimal module is 2500  
lines of pure python.
________________________________________________________________
erlang-questions mailing list. See http://www.erlang.org/faq.html
erlang-questions (at) erlang.org

[Witold Baryluk]

Dnia 2009-09-20, nie o godzinie 19:00 +0200, Masklinn pisze:

> On 20 Sep 2009, at 18:12 , Witold Baryluk wrote:
> > Dnia 2009-09-20, nie o godzinie 18:06 +0200, Masklinn pisze:
> >> On 20 Sep 2009, at 17:22 , Witold Baryluk wrote:
> >>> If you want something which calculates correctly in decimal number,
> >>> use
> >>> integers multiplied with some 10^k power. It is called fixed point
> >>> arithmetic.
> >> Or use a decimal floating-point library such as gmp.
> >
> > Sure. But considering that Erlang already have arbitrary precision
> > integers, writing few functions for add/sub/mul/div isn't very hard :)
>
> Arbitrary precision integers are quite different beasts (and easier to  
> handle) than arbitrary precision floats.

I was talking about arbitrary precision integer arithmetic (or fixed
point arithmetic).

Linking to gmp is just additional requirement, which is unnecessary
given the fact that Erlang already have integer arithmetic.

Something like this will suffice:


-module(fpa).

add({X,F},{Y,F}) -> {X+Y,F}.
sub({X,F},{Y,F}) -> {X-Y,F}.
neg({X,F}) -> {-X,F}.
mul({X,F},{Y,F}) -> {(X*Y) div F, F}.
div({X,F},{Y,F}) -> {(X*F) div Y, F}.
fpa_to_float({X,F}) -> X / F.
float_to_fpa6(X) -> {trunc(1000000*X), 1000000}.



"Accurate" binary floating point arithmetic is completely different
story, and few order of magnitud harder, and still quite active research
area in numerical analysis.

--
Witold Baryluk

[Richard Kelsall]

Hynek Vychodil wrote:

> Interesting, but seems well for me.
>
> $ erl
> Erlang R13B01 (erts-5.7.2) [source] [smp:2:2] [rq:2] [async-threads:0]
> [hipe] [kernel-poll:false]
>
> Eshell V5.7.2  (abort with ^G)
> 1> 0.111111111111 + 0.111111111111.
> 0.222222222222
> 2> 0.111111111111 - 0.111111111111.
> 0.0
> 3> 0.111111111111 + 0.11111111111.
> 0.222222222221
> 4> 0.111111111111 - 0.11111111111.
> 1.0000056338554941e-12

Yes, as far as I know Erlang is working perfectly. I was only speaking
hypothetically. Sorry for the noise.


Richard.

________________________________________________________________
erlang-questions mailing list. See http://www.erlang.org/faq.html
erlang-questions (at) erlang.org

[Richard O'Keefe]

On Sep 20, 2009, at 11:35 PM, G.S. wrote:

> Hello everyone,
>
> When subtracting in Erlang: 0.92915-0.92945 we should get -0.0003  
> but Erlang
> gives: -2.9999999999996696e-4   (when doing 92915-92945 Erlang gives  
> -30 so
> that's ok).
>
> Anyway to make make it give -0.0003 ?, and in general make it give  
> more
> accurate answers?

Erlang *DID* give you the most accurate answer possible.
Here is a little C program.

m% cat zoo.c
#include <stdio.h>

int main(void) {
     double const x = 0.92915;
     double const y = 0.92945;

     printf("0.92915           =  %.20f\n", x);
     printf("          0.92945 =  %.20f\n", y);
     printf("0.92915 - 0.92945 = %.20f\n", x - y);
     return 0;
}

m% cc zoo.c
m% a.out
0.92915           =  0.92915000000000003144
           0.92945 =  0.92944999999999999840
0.92915 - 0.92945 = -0.00029999999999996696

The problem is that the numbers 0.92915 an 0.92945
CANNOT BE REPRESENTED EXACTLY IN BINARY FLOATING-POINT.
There's a new standard for decimal floating-point,
which I believe is supported in shipping versions of
the z/Series and POWER machines, and it will take a lot
of the nasty surprise out of things like this.

The answer you got involved four steps where round-off
error can occur:
        decimal -> binary
        decimal -> binary again
        subtraction
        binary -> decimal
Giving any answer than what Erlang gave would be giving
WRONG answers.

If you want to *print* the result to a lower precision,
so that the effects of round-off error are (sometimes)
(partially) hidden (if you are lucky), that's easy.
The interactive top level will already print this number
as -3.00000e-4.  You can use vaguely C-like formats such
as io:fwrite("~.6g", [-0.00029999999999996696]).

Note that this doesn't change what the answer *is* (it's
already as good as you have any right to expect), it
just changes *how it is displayed*.



________________________________________________________________
erlang-questions mailing list. See http://www.erlang.org/faq.html
erlang-questions (at) erlang.org

[Richard O'Keefe]

On Sep 21, 2009, at 4:08 AM, Richard Kelsall wrote:

> Witold Baryluk wrote:
>>> so we probably shouldn't trust more than 12 digits of precision  
>>> because
>>> each calculation will lose some precision from the end of the  
>>> number.
>> Substraction (and addition) can lose  any number of digits you wish.
> I would be horrified if I added two doubles
>
> 0.111111111111 +
> 0.111111111111
>
> and got
>
> 0.225745048327

Yes, but you missed the point.  Those two numbers have the
same sign.  Witold Baryluk was talking about subtraction.
Adding two numbers of opposite signs does subtraction.
If you have x+y+e and x+z+f, where x is the "common" part
of two similar numbers, y and z are the true differences,
and e and f are errors, then
        (x+y) - (x+z) = y-z
but (x+y+e) - (x+z+f) = y-z + e-f
and the errors  e, f that were small compared with x may
be extremely large compared with y-z.

Read for example http://www.cs.princeton.edu/introcs/91float/
specifically the section beginning "Catastrophic cancellation.
Devastating loss of precision when small numbers are computed
from large numbers by addition or subtraction."

> I have no idea what the IEEE standard specifies,

Well, shouldn't you _find out_?  I mean, before using something
as weird (but widespread) as floating point arithmetic,
shouldn't you take the trouble to find out what it is *supposed*
to do?  The IEEE 754 standard is small and tolerably clear;
there are drafts and summaries and review articles about it
all over the web.

> but I can't imagine
> anybody ever implementing or using a version that gave this answer.

They don't.  Nobody ever suggested it would.

The original example subtracts two numbers with similar values.
Any fixed-width floating point system ever built is going
to have trouble with that.  IEEE floating-point arithmetic
was designed with exceptional care and a demand for good
behaviour even when that conflicted with speed.



________________________________________________________________
erlang-questions mailing list. See http://www.erlang.org/faq.html
erlang-questions (at) erlang.org

[Masklinn]

On 21 Sep 2009, at 03:50 , Richard O'Keefe wrote:
>
> The IEEE 754 standard is small and tolerably clear;
> there are drafts and summaries and review articles about it
> all over the web.

First and foremost being Goldberg's "What Every Computer Scientist  
Should Know About Floating-Point Arithmetic" (http://docs.sun.com/source/806-3568/ncg_goldberg.html 
) which is often considered the most basic knowledge requirement  
before any discussion of IEEE-754 floats.

________________________________________________________________
erlang-questions mailing list. See http://www.erlang.org/faq.html
erlang-questions (at) erlang.org

[Dave Smith-23]

Sorry for reviving this old thread, but I missed it on the first pass and
wanted to add my 2 cents.

When most people talk of IEEE-754, they are referring to  IEEE-754-1985
which which encompasses single and double precision floating points, which
are both binary FP formats. Erlang's floating point type is the double
precision binary.

IEEE-754-2008 defines a much broader set of formats which includes 4 binary
FP formats:

binary16  (half precision)
binary32  (single precision)
binary64  (double precision)
binary128 (quad precision)

and 3 decimal FP formats:

decimal32
decimal64
decimal 128

In addition there are the so-called interchange formats that are independent
of machine architecture.

The binary formats provide good precise values, but as has been pointed out,
not all decimal values are represented in these formats.  For scientific
applications and applications where precise unrounded values are required,
the binary formats are appropriate. For business applications where
predictable rounded values are required, the decimal formats are
appropriate.  To get the results you are looking for you should use one of
the decimal formats.

Erlang does not support any decimal format natively, however, it can be
supported in libraries.  A couple of years ago I wrote a decimal linked-in
driver that is backed by the IBM AlphaWorks DecNumber library.  Calulations
are done in decimal128 and the interface type is platform independent.  Find
it here:

http://github.com/dsmith-to/decimal

The library is very rough, but all the basic operations have been tested.  I
appologize, but the Makefile only works on mac-os-x.

--DS


2009/9/21 Masklinn <[hidden email]>

> On 21 Sep 2009, at 03:50 , Richard O'Keefe wrote:
>
>>
>> The IEEE 754 standard is small and tolerably clear;
>> there are drafts and summaries and review articles about it
>> all over the web.
>>
>
> First and foremost being Goldberg's "What Every Computer Scientist Should
> Know About Floating-Point Arithmetic" (
> http://docs.sun.com/source/806-3568/ncg_goldberg.html) which is often
> considered the most basic knowledge requirement before any discussion of
> IEEE-754 floats.
>
>
> ________________________________________________________________
> erlang-questions mailing list. See http://www.erlang.org/faq.html
> erlang-questions (at) erlang.org
>
>