Rounding error, (100.0 * 9.95).to_i == 994

[trans. (T. Onoma)]

| > On Wednesday 27 October 2004 04:36 pm, Hal Fulton wrote:
| > | Jason DiCioccio wrote:
| > | > I'm confused now.. 100.0 * 9.95 is clearly 995. So what exactly is
| > | > the issue with floating point numbers is making this come out to
| > | > 994.999999999983 (or wahtever )? If every language is plagued by
| > | > this problem, then I'd be curious to know the history behind it..
| > | >
| > | It's not history, it's math.
| > |
| > | Here's the short explanation.
| > |
| > | Remember repeating decimals, which you learned about in elementary
| > | school? For example, 1/3 = 0.33333... can't be expressed in a finite
| > | number of digits.
| >
| > Not exactly, '1/3' is finite.
|
| ... That's not what I learned in school. How many decimal digits does it
| take to express 1/3, then?

One, if you put a line over it --that's my point, any rational can be
represented in a finite amount of space.

T.

 

[trans. (T. Onoma)]

| > On Wednesday 27 October 2004 04:36 pm, Hal Fulton wrote:
| > | Jason DiCioccio wrote:
| > | > I'm confused now.. 100.0 * 9.95 is clearly 995. So what exactly is
| > | > the issue with floating point numbers is making this come out to
| > | > 994.999999999983 (or wahtever )? If every language is plagued by
| > | > this problem, then I'd be curious to know the history behind it..
| > | >
| > | It's not history, it's math.
| > |
| > | Here's the short explanation.
| > |
| > | Remember repeating decimals, which you learned about in elementary
| > | school? For example, 1/3 = 0.33333... can't be expressed in a finite
| > | number of digits.
| >
| > Not exactly, '1/3' is finite. Rational numbers can be expressed.
| > Irrationals cannot. But current standards do not attempt to deal with
| > repeating decimals, even though they could. The reason for this seems to
| > be a matter of history related to an ability to test inequalities
| > quickly.
|
| Expressed as a single number in either base 10 or 2, 0.333... requires an
| infinite number of digits (which is all I said).
|
| Knowing that it is rational, you could separately store the two numbers
| expressing that ratio. But that is completely different from traditional
| floating-point storage, and the simple traditional methods of (e.g.)
| addition and subtraction would not work.
|
| > IEEE754 is now 20 years old, and is showing its age. I have actually been
| > thinking of working on a improved version myself. But there's many
| > details to deal with, so who knows... maybe.
|
| Good idea, go for it.

Well, some group in San Fran is busy screwing it up (IEEE-754r) and have been
doing so since 2000 with plans to complete the screw-up in Decemeber of 2005.
I shouldn't be so harsh. But from reading it over it becomes clear that they
are simply cowing to current systems, rather then setting a high-mark
standard. Plan example:

"Decimal arithmetic, compatible with that used in Java, C#, PL/I, COBOL,
REXX, etc.,"

I thought languages were built to meet standards, not the other way around.
BTW: They've added a new decimal specification and compressed decimal format.

T.

 

[Steven Jenkins]

Expressed as a single number in either base 10 or 2, 0.333... requires an
infinite number of digits (which is all I said).

Knowing that it is rational, you could separately store the two numbers
expressing
that ratio. But that is completely different from traditional
floating-point storage,
and the simple traditional methods of (e.g.) addition and subtraction
would not
work.

It's been done. Google for "matula floating slash". As a graduate
student long ago, I did a little Fortran programming on the topic for
David Matula.

It's also worth pointing out that, from an information-theoretic point
of view, you can also represent irrational numbers in a finite number of
bits. For example, 'pi' or 'sqrt(2)'. But, as you note, that may not be
the most convenient representation for doing arithmetic.

Steve

 

[trans. (T. Onoma)]

On Wednesday 27 October 2004 06:14 pm, Steven Jenkins wrote:
| It's been done. Google for "matula floating slash". As a graduate
| student long ago, I did a little Fortran programming on the topic for
| David Matula.

Nice. I'm impressed. Unfortunately I couldn't find anything very detailed on
that method. (Have a good link?) But I did discover SLI arithmetic --not
perfect but it is more precise then f.p. and apparently is poised to have
great effects in supercomputing.

But what was more interesting were the very real and practical solutions
coming into play. Take one part GMP and add:

MPFR: http://www.mpfr.org/

or

ARITHMOS: http://www.win.ua.ac.be/~cant/arithmos/

and presto! That was easy Looks like the standards guys are way behind.

So are there bindings to GMP for Ruby? I beleive I've heard them mentioned...

(Note: ARITHMOS looks more promising, but MPFR may make it's way into GMP)

| It's also worth pointing out that, from an information-theoretic point
| of view, you can also represent irrational numbers in a finite number of
| bits. For example, 'pi' or 'sqrt(2)'. But, as you note, that may not be
| the most convenient representation for doing arithmetic.

He he. Well, there's a difference between a representation and computationally
useful notation. But, hey, who's counting?

Thanks Steve,
T.

 

[markus]

I'm not sure it's *just* in the multiplication... 0.95 can't
be stored exactly in binary, can it?

It can, but not using only a (binary) mantisa & (binary) exponent.
You could, for example, use offset decimal exponents (so incrementing the
exponent by 1 effectively multiplies the result by ten instead of two), or
by storing them as a numerator and denomonator (e.g. Rational). Or you
could cheat and use BCD.

My favorite trick is storing a "repeat length" that works like the
bar you use when dealing with repeated decimals on paper. I once saw a
very clever description of how to make that work. But (so far as I know),
no FPU designers read the same paper.

-- Markus

 

[trans. (T. Onoma)]

On Wednesday 27 October 2004 08:22 pm, (e-mail address removed) wrote:
| My favorite trick is storing a "repeat length" that works like the
| bar you use when dealing with repeated decimals on paper.  I once saw a
| very clever description of how to make that work.  But (so far as I know),
| no FPU designers read the same paper.

That was I was thinking. Do you know where your read it?

T.

 

[Mark Hubbart]

... That's not what I learned in school. How many decimal digits does it
take to express 1/3, then?

Reconfigure your misconceptions: decimal numeric notation has no basis
in reality. It is simply a way for humans to write down numbers.

Decimal, like binary, is a notation, a way to represent finite
numbers. It can not represent all finite numbers satisfactorily,
though; the notation has it's failings. One of the failings is shown
when representing finite rational numbers where the denominator is not
solely a multiple of powers of 2 and 5 (the factors of ten).

1/5 => 0.2
1/2 => 0.5
1/4 => 0.25
1/7 => 0.142857142857143.... (whoops)

In binary notation, you can only have finite representations of
rational numbers whose denominators are powers of two (the factors
of... two). The examples above translated into simple binary math:

1/101 => 0.0011001100110011.... (repeats)
1/10 => 0.1
1/100 => 0.01
1/111 => 0.0010010010010010.... (repeating)

To further confuse the subject. What you are representing when you
write the decimal number 42.23 is the rational number, 4223/100; aka
42 23/100, forty-two and twenty-three hundredths. That is a fraction;
a rational number. Decimal notation is simply a more convenient way of
writing it down, for making calculations or keeping records or
whatever.

In closing: Decimal numbers are made up! They aren't real! They are
all in your head!

cheers,
Mark
ps: I know this doesn't give a straight answer to your question. I'm
just arguing out that the question is somewhat irrelevant, since 1/3
is a rational number, and decimal notation is a flawed way of
representing rational numbers. A convenient way, but flawed
nonetheless.

 

[Dan Janowski]

I just want to thank all of you for a stimulating, interesting and, in
the end, informational discussion. Now I know why COBOL uses V99
numbers!

Has there been any consideration of using a Numeric class that is fixed
point? Something that is more like 995/100 representation internally?
There is sense is storing money in pennies instead of decimal dollars,
but it makes things a little more messy.

Dan

 

[jim]

I just want to thank all of you for a stimulating, interesting and, in
the end, informational discussion. Now I know why COBOL uses V99
numbers!

Has there been any consideration of using a Numeric class that is fixed
point? Something that is more like 995/100 representation internally?
There is sense is storing money in pennies instead of decimal dollars,
but it makes things a little more messy.

There's always Rational and BigDecimal.

 

[trans. (T. Onoma)]

On Thursday 28 October 2004 11:06 am, Dan Janowski wrote:
| I just want to thank all of you for a stimulating, interesting and, in
| the end, informational discussion. Now I know why COBOL uses V99
| numbers!

My father was a professional Cobol programmer for ~25 years. I always loved
all those strange and wondrous PIC declarations.

| Has there been any consideration of using a Numeric class that is fixed
| point? Something that is more like 995/100 representation internally?
| There is sense is storing money in pennies instead of decimal dollars,
| but it makes things a little more messy.

How 'bout a good Money class ?

T.


Sorry had to do it

000100 IDENTIFICATION DIVISION.
000200 PROGRAM-ID. TheTowersOfHanoi.
000300 AUTHOR. Amit Singh <http://hanoi.kernelthread.com>.
000400
000500 ENVIRONMENT DIVISION.
000600
000700 CONFIGURATION SECTION.
000800 SOURCE-COMPUTER. ALMOST-PORTABLE.
000900 OBJECT-COMPUTER. ALMOST-PORTABLE.
001000
001100 DATA DIVISION.
001200
001300 WORKING-STORAGE SECTION.
001400
001500 01 STACK-SPACE.
001600 02 ESP PIC S9(3) COMP.
001700 02 STACK-FRAME OCCURS 1024.
001800 03 S-N PIC 9(2).
001900 03 S-FROM PIC X(2).
002000 03 S-USING PIC X(2).
002100 03 S-TO PIC X(2).
002200 03 S-PROC PIC 9(1).
002300
002400 01 CURRENT-FRAME.
002500 02 CN PIC 9(2) VALUE 3.
002600 02 CFROM PIC X(2) VALUE "1".
002700 02 CUSING PIC X(2) VALUE "2".
002800 02 CTO PIC X(2) VALUE "3".
002900 02 CPROC PIC 9(1) VALUE 0.
003000
003100 01 TMP-FRAME.
003200 02 TN PIC 9(2) VALUE 3.
003300 02 TFROM PIC X(2) VALUE "1".
003400 02 TUSING PIC X(2) VALUE "2".
003500 02 TTO PIC X(2) VALUE "3".
003600 02 TPROC PIC 9(1) VALUE 0.
003700
003800 PROCEDURE DIVISION.
003900 BEGIN-PROGRAM.
003910 PERFORM GET-DISKS
004000 MOVE 1 TO ESP
004100 MOVE CURRENT-FRAME TO STACK-FRAME (ESP)
004150 PERFORM DO-HANOI
004200 UNTIL ESP = ZERO
004300 .
004500 STOP RUN
004600 .
004700
004800 DO-HANOI.
004900 MOVE STACK-FRAME (ESP) TO CURRENT-FRAME
005000 SUBTRACT 1 FROM ESP
005100 IF CPROC = 0
005200 IF CN = 1
005300 PERFORM MOVE-DISK
005400 ELSE
005500 MOVE CN TO TN
005600 MOVE CFROM TO TFROM
005700 MOVE CUSING TO TUSING
005800 MOVE CTO TO TTO
005900 MOVE 1 TO TPROC
006000 ADD 1 TO ESP
006100 MOVE TMP-FRAME TO STACK-FRAME (ESP)
006200 MOVE CN TO TN
006300 SUBTRACT 1 FROM TN
006400 MOVE CFROM TO TFROM
006500 MOVE CTO TO TUSING
006600 MOVE CUSING TO TTO
006700 MOVE 0 TO TPROC
006800 ADD 1 TO ESP
006900 MOVE TMP-FRAME TO STACK-FRAME (ESP)
006950 END-IF
007000 ELSE
007100 PERFORM MOVE-DISK
007200 MOVE 0 TO TPROC
007300 MOVE CTO TO TTO
007400 MOVE CFROM TO TUSING
007500 MOVE CUSING TO TFROM
007600 MOVE CN TO TN
007700 SUBTRACT 1 FROM TN
007800 ADD 1 TO ESP
007900 MOVE TMP-FRAME TO STACK-FRAME (ESP)
008000 END-IF
008100
008200 MOVE-DISK.
008300 DISPLAY CFROM
008400 "--> "
008500 CTO
008600
008700 GET-DISKS.
008800 DISPLAY "How many disks to solve for? " NO ADVANCING
008900 ACCEPT CN
009000 IF CN < 1 OR CN > 10
009100 DISPLAY "Invalid number of disks (1 <= N <= 10)."
009200 EXIT PROGRAM
009300 END-IF
009400
009500 .

 

[Markus]

On Wednesday 27 October 2004 08:22 pm, (e-mail address removed) wrote:
| My favorite trick is storing a "repeat length" that works like the
| bar you use when dealing with repeated decimals on paper. I once saw a
| very clever description of how to make that work. But (so far as I know),
| no FPU designers read the same paper.

That was I was thinking. Do you know where your read it?

No. I think it was an ACM or IEEE paper from the early eighties.
But I can't even swear to that. The basic idea was that:

1. You don't have to worry about repeat lengths greater than your
mantissa length
2. Repeats automatically "end align"
3. Non-repeating decimals can be thought of as having a repeat
length of one on the terminal bit
4. Repeats combine with an LCM rule, which can be computed in
hardware comparable in complexity to the exponent logic or
stored if you accept some limitations
5. Detecting reductions in repeat length could be done by using
some sort of shift xor thing that was described (IIRC) as being
simple but seemed complex to me
6. It doesn't matter if it ever get implemented as long as the
author can add the paper about how it could be done to his
publications list

-- Markus

 

[Gavin Sinclair]

Has there been any consideration of using a Numeric class that is fixed
point? Something that is more like 995/100 representation internally?
There is sense is storing money in pennies instead of decimal dollars,
but it makes things a little more messy.

I'd like a class that does fixed-point. Never heard any consideration
of it, though.

Gavin

 

[Charles Mills]

How 'bout a good Money class ?

IMHO a good Money class would be priceless
There was an interesting article in Dr. Dobbs about a java money class
a while back. Below is the extract (registration required for full
article).
Anyway if you do a lot of monetary calculations using floating point
you can get some pretty hefty round off error... as you guys have been
discussing.

-Charlie

www.ddj.com/documents/ddj0405i/
------------------------------------------------------------------------
---------
Java & Monetary Data

Dr. Dobb's Journal May 2004

A standalone class to tackle the problem

By John N. Armstrong
John is a senior partner and owner of Objective Logic L.L.P. in
McKinney, Texas, a software consulting firm specializing in
Java-centric architectures and solutions. He can be reached at
(e-mail address removed).
Decimal Data

Java and J2EE have become ubiquitous as a platform of choice for
creating robust enterprise e-commerce applications. Although these
kinds of applications typically involve operations on monetary data
(computing unit and extended prices, tax amounts, shipping costs, and
so on), Java does not provide suitable mechanisms for dealing with this
type of data.

Consequently, programmers are often faced with the problem of how to
reliably represent, store, and manipulate monetary data. Obviously,
when dealing with money, the importance of "getting it right" cannot be
overstated. For these and similar reasons, an e-commerce application
architecture should include a consistent mechanism for dealing with
monetary data.

In this article, I'll examine some of the more common techniques for
dealing with monetary data, and show why these techniques are less than
optimal. I also present Money, a standalone Java class that addresses
the problem of dealing with monetary data.

 

[James Edward Gray II]

IMHO a good Money class would be priceless

This could make a great Ruby Quiz, if written up correctly, I think...

James Edward Gray II

 

[Guillaume Marcais]

Reconfigure your misconceptions: decimal numeric notation has no basis
in reality. It is simply a way for humans to write down numbers.

Decimal, like binary, is a notation, a way to represent finite
numbers. It can not represent all finite numbers satisfactorily,
though; the notation has it's failings. One of the failings is shown
when representing finite rational numbers where the denominator is not
solely a multiple of powers of 2 and 5 (the factors of ten).

1/5 => 0.2
1/2 => 0.5
1/4 => 0.25
1/7 => 0.142857142857143.... (whoops)

Another funny failing of the notation is that not everything that looks
like a number actually represents a number. The following is quite
intriging:

x = 0.99999... (infinite serie of 9s)
10*x = 9.99999...
10*x - x = 9*x = 9
So x = 1!

IIRC, any 'word' that ends with an infinite serie of 9s does not
represent an actual real number.

Guillaume.

 

[Volkard Henkel]

Hello Guillaume,

x = 0.99999... (infinite serie of 9s)
10*x = 9.99999...
10*x - x = 9*x = 9
So x = 1!

IIRC, any 'word' that ends with an infinite serie of 9s does not
represent an actual real number.

you prooved, that 0.999999...=1
so 0.999999... IS a real number because 1 is one.

 

[Steven Jenkins]

On Wednesday 27 October 2004 06:14 pm, Steven Jenkins wrote:
| It's been done. Google for "matula floating slash". As a graduate
| student long ago, I did a little Fortran programming on the topic for
| David Matula.

Nice. I'm impressed. Unfortunately I couldn't find anything very detailed on
that method. (Have a good link?) But I did discover SLI arithmetic --not
perfect but it is more precise then f.p. and apparently is poised to have
great effects in supercomputing.

I was never involved in the analysis; I just wrote some code. Matula and
Kornerup published a few papers, but I don't know whether they're on the
web or not.

But what was more interesting were the very real and practical solutions
coming into play. Take one part GMP and add:

MPFR: http://www.mpfr.org/

or

ARITHMOS: http://www.win.ua.ac.be/~cant/arithmos/

and presto! That was easy Looks like the standards guys are way behind.

It was never the intent of IEEE 754 to prescribe optimal numerical
properties. Like all industry standards, its purpose was to balance
competing interests: numerical properties, performance,
manufacturability, etc. Some of the companies that participate in the
standards process are implementing these algorithms in proprietary code
or silicon. They're not about to adopt a 'new' approach that has
marginally better numerical properties if it puts them at a significant
competitive disadvantage in terms of performance or cost.

Also, bear in mind that for many types of problems, the error in the
mathematical approximations used to pose the problem and/or the
algorithms used to solve it are considerably larger than the errors in
the FP implementation. Additional precision there may cost you a lot and
do you no good.

Steve

 

[trans. (T. Onoma)]

12 AM, trans. (T. Onoma) wrote:
| > How 'bout a good Money class ?
|
| IMHO a good Money class would be priceless
| There was an interesting article in Dr. Dobbs about a java money class
| a while back. Below is the extract (registration required for full
| article).
| Anyway if you do a lot of monetary calculations using floating point
| you can get some pretty hefty round off error... as you guys have been
| discussing.
|
| -Charlie
|
| www.ddj.com/documents/ddj0405i/

Alas, I don't have that class of Money to subscribe

T.

 

[Steven Jenkins]

Another funny failing of the notation is that not everything that looks
like a number actually represents a number. The following is quite
intriging:

x = 0.99999... (infinite serie of 9s)
10*x = 9.99999...
10*x - x = 9*x = 9
So x = 1!

IIRC, any 'word' that ends with an infinite serie of 9s does not
represent an actual real number.

Sure it does. As you just showed, .9999... == 1.0.

Decimal notation is just convention. We take it for granted, but it's
convention. Any infinite decimal expanson is interpreted as a power
series. Such series always converge, and you can show (as you just did)
that any repeating decimal expansion converges to a rational number.

It's not a trick. They really are equal. Because we say so.

Steve

 

[Edgardo Hames]

On Thu, 2004-10-28 at 04:23, Mark Hubbart wrote:

Another funny failing of the notation is that not everything that looks
like a number actually represents a number. The following is quite
intriging:

x = 0.99999... (infinite serie of 9s)
10*x = 9.99999...
10*x - x = 9*x = 9
So x = 1!

0.9999... (infinite serie of 9s) is the standard (not IEEE, but plain
math) of the real number 1. Do you remember how to transform a
periodic number to a quotient? That's the integer part of the number
plus (the periodical part divided by as many nines as the periodical
part's digits). For example:

1.333... = 1 + 3/9
8.577577577... = 8 + 577/999

So,

0.99999... = 0 + 9/9 which is clearly 1.

Regards,
Ed