HELP: restore my faith in Python

[Tim Peters]

[bunching together several replies here]

[Tim]
>     int(0.999999999999999999993427) == 1
>     int(0.99999999999999999993427) == 1
>     int(0.9999999999999999993427) == 1
>     int(0.999999999999999993427) == 1
>
> and so on?  So long as you draw the line *somewhere*, you haven't solved
> anything, you've merely moved the surprises from where they're
> predictable across *all* IEEE-754 platforms to something unique to Python.
>
> The problems with floating-point are deep and can't be patched
> over.  "Quick hacks" always backfire.  If somebody wants to indulge in a
> notion of "safe epsilon", there's nothing to stop them from writing
> that explicitly.

[Konrad Hinsen]
> APL has a "comparison tolerance", implemented as a global (but
> localizable) variable that can be changed by the user, and which
> specifies the maximum relative error that is considered zero for the
> purpose of comparisons. It's a handy feature for quick calculator-type
> calculations, but it can get in the way when implementing more complex
> algorithms.

Note that the original poster was aiming at "fuzzing" float->int, though.
Fudging fp comparisons can almost be made principled, but e.g. there's no
reasonable way to do it without making it possible to find distinct x, y and
z s.t. x==y and y==z but NOT x==z.  Note too that APL is rife with implicit
"under the covers" float->int conversions, while Python has none (i.e., the
Python programmer must always say explicitly how they want float->int to get
done).

[John W. Baxter]
> ...
> 4.  A decimal floating point class could certainly be written for
> Python.

Such have been; AFAIK almost nobody uses them, though.  There's more call
for it in the business world, where a penny rounded away is a billion-dollar
lawsuit <wink>.

[Neel Krishnaswami]
> ...
> Is this possible? I've forgotten most of my analysis, but I was under
> the impression that you could divide the continuum as follows:
>
>   o Rationals -- eg 2/3. Countably infinite.
>   o Algebraic irrationals -- eg sqrt(2). Countably infinite.
>   o Transcendental numbers -- everything else. Uncountably infinite.
>
> So presumably you could write numeric classes that properly (if you
> don't care about speed or memory usage) handle rationals and algebraic
> irrationals, but the full transcendentals are just plain impossible.
> Maybe some interesting subset of the transcendentals are possible;
> if you throw in e and pi most people will be happy most of the time?
> Though on reflection this is getting pretty close to a full symbolic
> computation package.

What you're groping for is called the "constructive" or "computable" reals.
There's a well-developed theory, and a few scattered implementation pkgs.
The most recent influential text is by Pour-El and Richards -- curiously
enough, I studied mathematical logic under the former and real analysis
under the latter, so can vouch for their sterling characters <wink>.  A
sketchy intro to the main results can be found in Jean Vuillemin's "Exact
Real Computer Arithmetic with Continued Fractions", IEEE Transactions on
Computers, Vol 39 No 8, August 1990.  H-J Boehm did a widely used
implementation in the now-defunct Russell language, still available (last I
checked) from Rice University.  Just last year he released a more accessible
(but plainer) implementation in Java, available from somewhere or other on
the SGI web site.

As I said at the start, though, *all* approaches to real arithmetic suck in
deep ways.  For example, while exp(log(pi + 1e-5000)) is exactly equal to pi
+ 1e-5000 under the computable reals, equality is in general undecidable,
float->int also, and even figuring out the first digit of a constructive
real's decimal expansion is in general undecidable too.

> I guess Mathematica is that expensive for a reason -- arithmetic is
> harder than I thought. :)

Check out Macsyma (http://www.macsyma.com/).  A sixth the price and more
than adequate for most anything you'd like to explore.  It does not
implement the constructive reals, though.

[Michael Hudson]
> Food for thought: the computable numbers are countable.
>
> Proof left as an exercise for the reader (it's not hard!).
>
> (Is it even meaningful to ask whether they are [recursively]
> enumerable?)

Sure!  That's meaningful for any countable set.  It turns out that while
they're countable, they're not recursively enumerable.  If they were, you'd
have an effective algorithm for computing one not in the enumeration, via
the usual diagonalization trick.  Since you *can* enumerate all possible
programs, this may appear paradoxical.  The "out" is that deciding whether a
program produces a computable real is undecidable.  And if your programming
language is so weak that that question *is* decidable, then the same
diagonalization argument proves that it's not strong enough to capture the
notion of computable reals.

almost-as-much-fun-as-continuations<wink>-ly y'rs  - tim