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
···
On Thu, 28 Oct 2004, Hal Fulton wrote:
David G. Andersen wrote:
> The problem in this case isn't actually in the storage
> of 9.95 or 995 in floating point; it comes in when you do the
> multiplication.
I'm not sure it's *just* in the multiplication... 0.95 can't
be stored exactly in binary, can it?
One, if you put a line over it --that's my point, any rational can be
represented in a finite amount of space.
T.
···
On Wednesday 27 October 2004 04:57 pm, Jamis Buck wrote:
trans. (T. Onoma) wrote:
> 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?
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.
···
On Wednesday 27 October 2004 04:54 pm, Hal Fulton wrote:
trans. (T. Onoma) wrote:
> 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.
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.
That was I was thinking. Do you know where your read it?
T.
···
On Wednesday 27 October 2004 08:22 pm, markus@reality.com 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.
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).
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:
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.
···
On Thu, 28 Oct 2004 05:57:53 +0900, Jamis Buck <jgb3@email.byu.edu> wrote:
trans. (T. Onoma) wrote:
> 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?
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:
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.
···
On Wednesday 27 October 2004 06:14 pm, Steven Jenkins 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!
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
···
On Oct 28, 2004, at 04:23, Mark Hubbart wrote:
On Thu, 28 Oct 2004 05:57:53 +0900, Jamis Buck <jgb3@email.byu.edu> > wrote:
trans. (T. Onoma) wrote:
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?
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).
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:
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.
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
···
On Wed, 2004-10-27 at 17:40, trans. (T. Onoma) wrote:
On Wednesday 27 October 2004 08:22 pm, markus@reality.com 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?
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.
···
On Thu, 2004-10-28 at 04:23, Mark Hubbart wrote:
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).
* Dan Janowski <danj@3skel.com> [2004-10-29 00:06:46 +0900]:
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.
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 .
···
On Thursday 28 October 2004 11:06 am, Dan Janowski wrote:
I'd like a class that does fixed-point. Never heard any consideration
of it, though.
Gavin
···
On Friday, October 29, 2004, 1:06:46 AM, Dan wrote:
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.
> 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:
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
···
On Wednesday 27 October 2004 06:14 pm, Steven Jenkins 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!
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.
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
···
On Fri, 29 Oct 2004 02:40:14 +0900, Guillaume Marcais <guslist@free.fr> wrote:
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!
--
Despite the surge of power you feel upon learning Ruby,
resist the urge to trip others or slap them in the bald head.
DO NOT LORD YOUR RUBYNESS OVER OTHERS!
No doubt, there are some difficulties, but it certainly seems completely
doable. And #6 sounds about right! Leave it to human beings to go on and on
bitching and dealing with rounding issues and what not, rather then taking
stock and fixing the problem. But maybe there are alternative reasons for it.
Wasn't it Richard Pryor in Superman 4 that got rich off this bug?
T.
···
On Thursday 28 October 2004 12:13 pm, Markus wrote:
On Wed, 2004-10-27 at 17:40, trans. (T. Onoma) wrote:
> On Wednesday 27 October 2004 08:22 pm, markus@reality.com 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
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.
On Oct 28, 2004, at 9:12 AM, trans. (T. Onoma) wrote:
How 'bout a good Money class ?
---------------------------------------------------------------------------------
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 john@objectivelogic.com.
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.
-------------------------------------------------------------------------------------
It's not history, it's math.