Floating point bug?

[Mensanator]

It ensures that your fraction's denominator doesn't grow indefinitely, at
the cost of some precision. In principle, fraction denominators can grow
exponentially. In practice, probably less quickly, but still quickly
enough that people on this list have reported that adding two fractions
lead to millions of digits in each denominator and massive paging as
their computer struggled to perform the addition.

Ok, but I've never seen that happen with the rationals
of the gmpy module. I'm getting the feeling that this
fear of rationals is overrated.

But maybe it's because I know what I'm doing.

Naw, that can't be it.

The beauty of fractions is that they give you infinite precision. The
danger of fractions is that it takes a lot of memory to store infinitely
precise numbers

Frankly, I think that for most real-world data, it's unlikely to be a
problem,

My guess is that you're right.

but Guido's experiences with ABC were the opposite. But then we
don't know how naive the ABC fraction libraries were. For all I know they
did this:

1/2 + 1/2 = 4/4
4/4 - 1/2 = 4/8
4/8 + 1/2 = 16/16
etc.

Perhaps Guido should have an occasional peek
at the monster he's created. The gmpy library
always reduces to lowest denominator, so the
above couldn't happen.

 

[Mel]

I decided to keep the num/den limit low (10) because higher values
might obscure the fact that it do have limits. [ ... ]

Out of curiosity, of what use is denominator limits?

The problems where I've had to use rationals have
never afforded me such luxury, so I don't see what
your point is.

In calculations dealing only with selected units of measure: dollars
and cents, pounds, ounces and tons, teaspoons, gallons, beer bottles
28 to a case, then the denominators would settle out pretty quickly.

In general mathematics, not.

I think that might be the point.

Mel.

 

[Mensanator]

I decided to keep the num/den limit low (10) because higher values
might obscure the fact that it do have limits. [ ... ]

Out of curiosity, of what use is denominator limits?

The problems where I've had to use rationals have
never afforded me such luxury, so I don't see what
your point is.

In calculations dealing only with selected units of measure: dollars
and cents, pounds, ounces and tons, teaspoons, gallons, beer bottles
28 to a case, then the denominators would settle out pretty quickly.
Ok.


In general mathematics, not.

But that doesn't mean they become less manageable than
other unlimited precision usages. Did you see my example
of the polynomial finder using Newton's Forward Differences
Method? The denominator's certainly don't settle out, neither
do they become unmanageable. And that's general mathematics.

I think that might be the point.

If the point was as SDA suggested, where things like 16/16
are possible, I see that point. As gmpy demonstrates thouigh,
such concerns are moot as that doesn't happen. There's no
reason to suppose a Python native rational type would be
implemented stupidly, is there?

 

[casevh]

But that doesn't mean they become less manageable than
other unlimited precision usages. Did you see my example
of the polynomial finder using Newton's Forward Differences
Method? The denominator's certainly don't settle out, neither
do they become unmanageable. And that's general mathematics.

Since you are expecting to work with unlimited (or at least, very
high) precision, then the behavior of rationals is not a surprise. But
a naive user may be surprised when the running time for a calculation
varies greatly based on the values of the numbers. In contrast, the
running time for standard binary floating point operations are fairly
constant.

If the point was as SDA suggested, where things like 16/16
are possible, I see that point. As gmpy demonstrates thouigh,
such concerns are moot as that doesn't happen. There's no
reason to suppose a Python native rational type would be
implemented stupidly, is there?

In the current version of GMP, the running time for the calculation of
the greatest common divisor is O(n^2). If you include reduction to
lowest terms, the running time for a rational add is now O(n^2)
instead of O(n) for a high-precision floating point addition or O(1)
for a standard floating point addition. If you need an exact rational
answer, then the change in running time is fine. But you can't just
use rationals and expect a constant running time.

There are trade-offs between IEEE-754 binary, Decimal, and Rational
arithmetic. They all have there appropriate problem domains.

And sometimes you just need unlimited precision, radix-6, fixed-point
arithmetic....

casevh

 

[Mensanator]

Since you are expecting to work with unlimited (or at least, very
high) precision, then the behavior of rationals is not a surprise. But
a naive user may be surprised when the running time for a calculation
varies greatly based on the values of the numbers.

Well, that applies equally to Python long ints
which can be intractable compared to gmpy's
long ints.

In contrast, the
running time for standard binary floating point operations are fairly
constant.




In the current version of GMP, the running time for the calculation of
the greatest common divisor is O(n^2). If you include reduction to
lowest terms, the running time for a rational add is now O(n^2)
instead of O(n) for a high-precision floating point addition or O(1)
for a standard floating point addition. If you need an exact rational
answer, then the change in running time is fine. But you can't just
use rationals and expect a constant running time.

Well, _I_ don't expect constant run time, but I usually
need tractable run-time. And since Python's built-ins
can't always cut it compared to gmpy, I suppose a fraction
type probably couldn't hold a candle to gmpy either.

So even if implemented correctly to prevent runaway
denominators, the fraction type would likely
end up being as worthless to me as the current long
ints are.

There are trade-offs between IEEE-754 binary, Decimal, and Rational
arithmetic. They all have there appropriate problem domains.

Of course. And design decisions shouldn't be based
on bad algorithms, but those that are appropriate
to the problem domain.

 

[Carl Banks]

Repeated Addition and subtraction can't make fractions grow
infinitely, only multiplication and division could.

What part of "repeated additions and divisions" don't you understand?



Carl Banks

 

[Carl Banks]

But that doesn't mean they become less manageable than
other unlimited precision usages. Did you see my example
of the polynomial finder using Newton's Forward Differences
Method? The denominator's certainly don't settle out, neither
do they become unmanageable. And that's general mathematics.

No, that's a specific algorithm. That some random algorithm doesn't
blow up the denominators to the point of disk thrashing doesn't mean
they won't generally.

Try doing numerical integration sometime with rationals, and tell me
how that works out. Try calculating compound interest and storing
results for 1000 customers every month, and compare the size of your
database before and after.


Carl Banks

 

[Paul Rubin]

Try doing numerical integration sometime with rationals, and tell me
how that works out. Try calculating compound interest and storing
results for 1000 customers every month, and compare the size of your
database before and after.

Usually you would round to the nearest penny before storing in the
database.

 

[Carl Banks]

Usually you would round to the nearest penny before storing in the
database.

I throw it out there as a hypothetical, not as a real world example.
"This is why we don't (usually) use rationals for accounting."


Carl Banks

 

[Dennis Lee Bieber]

Usually you would round to the nearest penny before storing in the
database.

Tell that to the payroll processing at Lockheed... My paycheck tends
to vary from week to week as the database apparently carries amount to
at least 0.001 resolution, only rounding when distributing among various
taxes for the paycheck itself. Tedious data entry in Quicken as I have
to keep tweaking various tax entries by +/- a penny each week.

Oh... And M$ -- the currency type in VB is four decimal places.
--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/

 

[M.-A. Lemburg]

If you're interested in rationals, then you might want to have a look
at mxNumber which is part of the eGenix mx Experimental
Distribution:

http://www.egenix.com/products/python/mxExperimental/mxNumber/

It provides fast rational operations based on the GNU MP
library.

No, that's a specific algorithm. That some random algorithm doesn't
blow up the denominators to the point of disk thrashing doesn't mean
they won't generally.

Try doing numerical integration sometime with rationals, and tell me
how that works out. Try calculating compound interest and storing
results for 1000 customers every month, and compare the size of your
database before and after.

It is well possible to limit the denominator before storing it
in a database or other external resource using Farey neighbors:

http://en.wikipedia.org/wiki/Farey_sequence#Farey_neighbours

mxNumber implements an algorithm for this (not the most efficient
one, but it works nicely).

--
Marc-Andre Lemburg
eGenix.com

Professional Python Services directly from the Source (#1, Feb 25 2008)________________________________________________________________________

:::: Try mxODBC.Zope.DA for Windows,Linux,Solaris,MacOSX for free ! ::::


eGenix.com Software, Skills and Services GmbH Pastor-Loeh-Str.48
D-40764 Langenfeld, Germany. CEO Dipl.-Math. Marc-Andre Lemburg
Registered at Amtsgericht Duesseldorf: HRB 46611

 

[Jorge Godoy]

Usually you would round to the nearest penny before storing in the
database.

There are cases where the law requires a higher precision or where the
rounding has to be a floor or...

Some things make no sense and when dealing with money things make even less
sense to either protect the customer or to grant the State getting its
share of the transaction.

Here in Brasil, for example, gas stations have to display the price with 3
decimal digits and round the end result down (IIRC). A truck filling 117
liters at 1.239 reais per liter starts making a mess... If the owner wants
to track "losses" due to rounding or if he wants to make his inventory of
fuel accurately, he won't be able to save just what he billed the customer
otherwise things won't match by the end of the month.

 

[Mensanator]

No, that's a specific algorithm. �That some random algorithm doesn't
blow up the denominators to the point of disk thrashing doesn't mean
they won't generally.

Try doing numerical integration sometime with rationals, and tell me
how that works out. �Try calculating compound interest and storing
results for 1000 customers every month, and compare the size of your
database before and after.

Nobody said rationals were the appropriate solution
to _every_ problem, just as floats and integers aren't
the appropriate solution to _every_ problem.

Your argument is that I should be forced to use
an inappropriate type when rationals _are_
the appropriate solution.

I have never used the Decimal type, but I'm not
calling for it's removal because I know there are
cases where it's useful. If a rational type were
added, no one would force you to use it for
numerical integration.

 

[Steven D'Aprano]

Tell that to the payroll processing at Lockheed...My paycheck
tends to vary from week to week as the database apparently carries
amount to at least 0.001 resolution, only rounding when distributing
among various taxes for the paycheck itself. Tedious data entry in
Quicken as I have to keep tweaking various tax entries by +/- a penny
each week.

"Worst practice" in action *wink*

I predict they're using some funky in-house accounting software they've
paid millions to a consultancy firm (SAP?) for over the decades, written
by some guys who knows lots of Cobol but no accounting, and the internal
data type is a float.

[snip]

Oh... And M$ -- the currency type in VB is four decimal places.

Accounting standards do vary according to context: e.g. I see that
offical Australian government reporting standards for banks is to report
in millions of dollars rounded to one decimal place. Accountants can
calculate things more or less any way they like, so long as they tell
you. I found one really dodgy example:

"The MFS Water Fund ARSN 123 123 642 (‘the Fund’) is a registered managed
investment scheme. ... MFS Aqua may calculate the Issue Price to the
number of decimal places it determines."

Sounds like another place using native floats. But it's all above board,
because they tell you they'll use an arbitrary number of decimal places,
all the better to confuse the auditors my dear.

 

[Steven D'Aprano]

I throw it out there as a hypothetical, not as a real world example.
"This is why we don't (usually) use rationals for accounting."

But since accountants (usually) round to the nearest cent, accounting is
a *good* use-case for rationals. Decimal might be better, but floats are
worst.

I wonder why you were doing numerical integration with rationals in the
first place? Are you one of those ABC users (like Guido) who have learnt
to fear rationals because ABC didn't have floats?

 

[M.-A. Lemburg]

But since accountants (usually) round to the nearest cent, accounting is
a *good* use-case for rationals. Decimal might be better, but floats are
worst.

That's not necessarily true in general: finance libraries usually try
to always do calculations at the best possible precision and then only
apply rounding at the very end of a calculation. Most of the time a float
is the best data type for this.

Accounting uses a somewhat different approach and one which various
between the different accounting standards and use cases. The decimal
type is usually better suited for this, since it supports various
ways of doing rounding.

Rationals are not always the best alternative, but they do help
in cases where you need to guarantee that the sum of all parts
is equal to the whole for all values. Combined with interval
arithmetic they go a long way towards more accurate calculations.

--
Marc-Andre Lemburg
eGenix.com

Professional Python Services directly from the Source (#1, Feb 25 2008)________________________________________________________________________

:::: Try mxODBC.Zope.DA for Windows,Linux,Solaris,MacOSX for free ! ::::


eGenix.com Software, Skills and Services GmbH Pastor-Loeh-Str.48
D-40764 Langenfeld, Germany. CEO Dipl.-Math. Marc-Andre Lemburg
Registered at Amtsgericht Duesseldorf: HRB 46611

 

[Carl Banks]

Nobody said rationals were the appropriate solution
to _every_ problem, just as floats and integers aren't
the appropriate solution to _every_ problem.

I was answering your claim that rationals are appropriate for general
mathematical uses.

Your argument is that I should be forced to use
an inappropriate type when rationals _are_
the appropriate solution.

I don't know where you got that idea.

My argument is that rationals aren't suitable for ordinary uses
because they have poor performance and can easily blow up in your
face, trash your disk, and crash your program (your whole system if
you're on Windows).

In other words, 3/4 in Python rightly yields a float and not a
rational.


Carl Banks

 

[Grant Edwards]

In other words, 3/4 in Python rightly yields a float

Unless you're in the camp that believes 3/4 should yield the
integer 0.

 

[Steve Holden]

Unless you're in the camp that believes 3/4 should yield the
integer 0.

No, that wouldn't be rational ;-)

 

[J. Cliff Dyer]

Unless you're in the camp that believes 3/4 should yield the
integer 0.

I'm in the camp that believes that 3/4 does indeed yield the integer 0,
but should be spelled 3//4 when that is the intention.

Cheers,
Cliff