Re: FAQ 4.2 Why is int() broken?

On 2008-07-28 17:56, szr <szrRE@xxxxxxxxxxxxxxx> wrote:
Peter J. Holzer wrote:
On 2008-07-28 06:12, Jürgen Exner <jurgenex@xxxxxxxxxxx> wrote:
"szr" <szrRE@xxxxxxxxxxxxxxx> wrote:
Peter J. Holzer wrote:
Please get it into your head that extra precision *does* *not*
solve this problem. To express 1/10 in binary you need an infinite
number of digits, just like you need an infinite number of digits
to express 1/3 in decimal.

Maybe you meant to write something else, as 1/10 is 0.1 and does not
require an infinite number of digits;

Yes, it does.

It doesn't, but I didn't write that. I wrote it takes an infinite
number of *binary* digits.

In binary, 1/10 is 0.00011001100110011...


For some reason I thought that applied to decimal expresses that
repeated infinately, like 1/3 => .3333..., not decimals with a fixed
number of dibits, which 1/0 => 0.1 is:

$ perl -e 'my $x = 1/10; print unpack("b64", pack("d", $x)), "\n"'
0101100110011001100110011001100110011001100110011001110111111100
<--><--><--><--><--><--><--><--><--><--><--><-->

Um, the repeating pattern is clearly visible here. The pattern is
broken on the left side because of rounding (you printed the pattern in
little endian, so the least significant digit is on the left and the,
er, binary point is just to the right of the rightmost ">" I made).



$ perl -e 'my $x = 1/2; print unpack("b64", pack("d", $x)), "\n"'
0000000000000000000000000000000000000000000000000000011111111100

$ perl -e 'my $x = 1/4; print unpack("b64", pack("d", $x)), "\n"'
0000000000000000000000000000000000000000000000000000101111111100

$ perl -e 'my $x = 1/8; print unpack("b64", pack("d", $x)), "\n"'
0000000000000000000000000000000000000000000000000000001111111100

1/2, 1/4, 1/8 are all exactly representable in binary, because they are
integral multiples of powers of two. 1/10 is not, because it is not an
integral multiple of powers of two. 1/3 is not representable in decimal
because it is not an integral multiple of a power of 10. And 1/2 is not
representable in base-15 because it is not an integral multiple of a
power of 15 (but 1/3 and 1/5 are). For any given base, there are always
only a small (but infinite :-)) number of fraction which are
representable in that base.


it needs just one decimal digit

Irrelevant because your typical computer does not use decimal numbers
but binary numbers, just like Peter said.

Actually, I didn't write what "a typical computer" uses, just what
happens when a binary system is used (which is what perl uses on most
(all?) platforms - COBOL uses normally uses decimal).

Even among different types of computers floating point calculations are
not all done the same. For instance, I have a graphing calculator, which
is essentially tiny computer with a 6 MHz cpu and yet it can do many
floating point calculations more accurately than my dual core cpu
desktop.

I'm not up to date with calculators (the last one I bought was an HP-48
20 years ago), but frankly, I doubt that it is more accurate. It has
probably less than 15 digits of mantissa. It probably does its
computations in decimal, which makes them even less accurate, but the
errors *match* *your* *expectations*, so you don't notice then.


Granted, it's a calculator, but I have often wondered why it
seems to be able to handle such calculations better than a CPU that's
over 400 times faster.

Different target. Calculators can be slow - they do only primitive
computations, and if they finish them in a short but noticable time its
still "fast enough". A modern CPU is supposed to be able to do hundreds
of millions such computations per second. Calculators are also rarely
used for computations where accuracy is much of an issue - 8 or 12
digits are enough. But they are used by people who expect 0.1 * 10 to be
1.0 but aren't overly surprised if 1/3*3 is 0.9999999.

In short it is able to "handle such calculations" because it has been
designed to do so. Floating point hardware has been designed to give the
most accurate result in a very short time. You can always implement
decimal arithmetic yourself or use a library[1] - it will still be a lot
faster than your calculator.


hp

[1] Incidentally, I know of one modern processor (the IBM Power6) which
implements full decimal floating point arithmetic in hardware.
.

Relevant Pages

  • Re: FAQ 4.2 Why is int() broken?
    ... To express 1/10 in binary you need an infinite ... number of digits, just like you need an infinite number of digits ... Even among different types of computers floating point calculations are ...
    (comp.lang.perl.misc)
  • Re: Rounding errors
    ... >>number of random digits following the point of rounding, ... > an infinite number of digits right of decimal. ... multiplication nor what the number of digits in the calculations was. ...
    (comp.lang.cobol)
  • Re: sin (M_PI)
    ... exactly without giving an infinite number of digits (what- ... computer you can only store a finite number of digits. ... but an approximation. ... proximate calculations of functions on approximate values. ...
    (comp.lang.c)
  • Re: The Modified Halting Problem, Take ??? .
    ... What you write is not the same as saying all digits can be computed. ... With an infinite number the same process is used, ... We have infinitely many halting TMs, ... first you see 3 on the first tape, then you see 3.1 on the second tape, ...
    (sci.logic)
  • Re: The Modified Halting Problem, Take ??? .
    ... What you write is not the same as saying all digits can be computed. ... With an infinite number the same process is used, ... first you see 3 on the first tape, then you see 3.1 on the second tape, ... There are countably infinite Turing machines (meaning exactly TMs ...
    (sci.logic)