To get the accurate value of 1 - 0.999999999999999 ,how to implement the python algorithm ？

[iMath]

To get the accurate value of 1 - 0.999999999999999 ,how to implement the python algorithm ？
BTW ，Windows’s calculator get the accurate value ，anyone who knows how to implement it ?

 

[Ulrich Eckhardt]

Am 08.10.2012 16:07, schrieb iMath:

To get the accurate value of 1 - 0.999999999999999 ,how to implement the python algorithm ？

Algorithms are generally language-agnostic, so what is your question

BTW ，Windows’s calculator get the accurate value ，anyone who knows how to implement it ?

You should use a library that handles arbitrary-precision floating point
numbers, Python's built-in floating point type corresponds to C's double
type and that is typically a IEEE float, which means a limited
precision. Just search the web for one. If you really want to do it
yourself, you could leverage the fact that Python's integral type has a
dynamic size, so that it can represent numbers with more than the
typical 32 or 64 bits width.

BTW: If this is not a homework question, you should ask much more
specifically. My anwers are intentionally vague in order to not spoil
you the learning effect.

Cheers!

Uli

 

[Dave Angel]

To get the accurate value of 1 - 0.999999999999999 ,how to implement the python algorithm ？
BTW ，Windows’s calculator get the accurate value ，anyone who knows how to implement it ?

Windows calculator is an application, not a programming language. Like
all applications, it has to deal with the finite accuracy of the
underlying processor and language, and choose an algorithm that will
please its users.

The Pentium chip (and its equivalents from AMD), used by Windows
machines and most others, has about 18 digits of accuracy in its binary
floating point math. However, being binary, the data has to be
converted from decimal to binary (when the user types it in) and binary
to decimal (when displaying it). Either of those conversions may have
quantization errors, and it's up to the program to deal with those or
other inaccuracies.

If you subtract two values, either of which may have quantization
errors, and they are quite close, then the apparent error is
magnified. Out of your 18 digits internal accuracy, you now have only
about 2.

Therefore many programs more concerned with apparent accuracy will
ignore the binary floating point, and do their work in decimal. That
doesn't eliminate calculation errors, but only quantization errors.
That makes the user think he is getting more accuracy than he really is.

Since that seems to be your goal, I suggest you look into the Decimal
class, locating in the stdlib decimal.

import decimal
a = decimal.Decimal(4.3)
print(a)

5.0999999999999996447286321199499070644378662109375

Note that you still seem to have some "error" since the value 4.3 is a binary float, and has already been quantized. If you want to avoid the binary stuff entirely, try going directly from string to Decimal.

b = decimal.Decimal("5.1")
print(b)

5.1

Back to your original contrived example,

c = decimal.Decimal("1.0")
d = decimal.Decimal("0.999999999999999")
print(c-d)

1E-15

The Decimal class has the disadvantage that it's tons slower on any modern machine I know of, but the advantage that you can specify how much precision you need it to use. It doesn't eliminate errors at all, just one class of them.

e = decimal.Decimal("3.0")
print(c/e)

0.3333333333333333333333333333

That of course is the wrong answer. The "right" answer would never stop printing. We still have a finite number of digits.

print(c/e*e)

0.9999999999999999999999999999

"Fixing" this is subject for another lesson, someday.

 

[Chris Angelico]

import decimal
a = decimal.Decimal(4.3)
print(a)

5.0999999999999996447286321199499070644378662109375

Ah, the delights of copy-paste

The Decimal class has the disadvantage that it's tons slower on any modern machine I know of...

Isn't it true, though, that Python 3.3 has a completely new
implementation of decimal that largely removes this disadvantage?

ChrisA

 

[Dave Angel]

Ah, the delights of copy-paste

Isn't it true, though, that Python 3.3 has a completely new
implementation of decimal that largely removes this disadvantage?

ChrisA

I wouldn't know, I'm on 3.2. However, I sincerely doubt if it's within
a factor of 100 of the speed of the binary float, at least on
pentium-class machines that do binary float in microcode. A dozen years
or so ago, when the IEEE floating point standard was still being formed,
I tried to argue the committee into including decimal in the standard
(which they did much later). Had it been in the standard then, we MIGHT
have had decimal fp on chip as well as binary. Then again, the standard
was roughly based on the already-existing Intel 8087, so maybe it was
just hopeless.

I guess it's possible that for some operations, the cost of the
byte-code interpreter and function lookup, etc. might reduce the
apparent penalty. Has anybody done any timings?

 

[Chris Angelico]

I wouldn't know, I'm on 3.2. However, I sincerely doubt if it's within
a factor of 100 of the speed of the binary float, at least on
pentium-class machines that do binary float in microcode. A dozen years
or so ago, when the IEEE floating point standard was still being formed,
I tried to argue the committee into including decimal in the standard
(which they did much later). Had it been in the standard then, we MIGHT
have had decimal fp on chip as well as binary. Then again, the standard
was roughly based on the already-existing Intel 8087, so maybe it was
just hopeless.

I guess it's possible that for some operations, the cost of the
byte-code interpreter and function lookup, etc. might reduce the
apparent penalty. Has anybody done any timings?

Try this, from python-dev list:

http://mail.python.org/pipermail/python-dev/2012-September/121832.html

It's not as fast as float, but it sure gives a good account for itself.

ChrisA

 

[Terry Reedy]

I wouldn't know, I'm on 3.2. However, I sincerely doubt if it's within
a factor of 100 of the speed of the binary float, at least on

import timeit as tt
tt.repeat("float('1.0')-float('0.9999999999')") [0.6856039948871151, 0.669049830953858, 0.668688006423692]
tt.repeat("Decimal('1.0')-Decimal('0.9999999999')", "from decimal

import Decimal")
[1.3204655578092428, 1.286977575486688, 1.2893188292009938]

tt.repeat("a-b", "a = 1.0; b=0.9999999999") [0.06100386171601713, 0.044538539999592786, 0.04451548406098027]
tt.repeat("a-b", "from decimal import Decimal as D; a = D('1.0'); b

= D('0.9999999999')")
[0.14685526219517442, 0.12909696344064514, 0.12646059371189722]

A factor of 3, as S. Krah, the cdecimal author, claimed

 

[Dave Angel]

I wouldn't know, I'm on 3.2. However, I sincerely doubt if it's within
a factor of 100 of the speed of the binary float, at least on

import timeit as tt
tt.repeat("float('1.0')-float('0.9999999999')") [0.6856039948871151, 0.669049830953858, 0.668688006423692]
tt.repeat("Decimal('1.0')-Decimal('0.9999999999')", "from decimal

import Decimal")
[1.3204655578092428, 1.286977575486688, 1.2893188292009938]

tt.repeat("a-b", "a = 1.0; b=0.9999999999") [0.06100386171601713, 0.044538539999592786, 0.04451548406098027]
tt.repeat("a-b", "from decimal import Decimal as D; a = D('1.0');

b = D('0.9999999999')")
[0.14685526219517442, 0.12909696344064514, 0.12646059371189722]

A factor of 3, as S. Krah, the cdecimal author, claimed

I concede the point. But I was "sincere" in my doubt.

What I'm curious about now is 1) how much the various operators vary in
that 3:1 ratio and 2) how much the overhead portions are using of that
time.

I have to assume that timeit.repeat doesn't count the time spent in its
second argument, right? Because converting a string to a Decimal should
be much faster than converting one to float. But what about the
overhead of eval(), or whatever it uses? Is the "a-b" converted to byte
code just once? Or is it recompiled each time through tje loop?

I have to admit not spending much time in timeit(); I usually end up
timing things with my own loops. So i'd really like to understand how
overhead is figured.

 

[Steven D'Aprano]

Ah, the delights of copy-paste


Isn't it true, though, that Python 3.3 has a completely new
implementation of decimal that largely removes this disadvantage?

Yes. It's blazingly fast: up to 120 times faster than the pure Python
version, and within an order of magnitude of the speed of binary floats:

[steve@ando ~]$ python3.3 -m timeit -s "x, y = 1001.0, 978.0"

"x+y-(x/y)**4"

1000000 loops, best of 3: 0.509 usec per loop

[steve@ando ~]$ python3.3 -m timeit -s "from decimal import Decimal"

-s "x, y = Decimal(1001), Decimal(978)" "x+y-(x/y)**4"

100000 loops, best of 3: 3.58 usec per loop


Without hardware support, Decimal will probably never be quite as fast as
binary floats, but its fast enough for all but the most demanding needs.