Rational arithmetic is a red herring

It's a traditional question: what's 1 / 3?

Depending on the language, the result may be the integer 0, a floating-point approximation 0.33333333333..., or the exact ratio 1/3. Languages supporting the last often tout it as one of their advantages: they give correct results for integer division, unlike those other languages that only give almost-correct ones, or, worse, compute some other function entirely and call it division.

I used to agree with this. Exact arithmetic is a nice feature, to be sure, and I've happily used it in a few toy programs. But as far as I can remember, I've never wanted it in a real program. Somehow, whenever I need real arithmetic for a real problem, some of the input is already approximate, so I don't mind a little more rounding. Rational arithmetic looks nice on a feature checklist, but it rarely makes my life easier.

It's also not as special as it sounds. Ratios are a simple case of symbolic arithmetic: keeping the result as something expression-like, instead of approximating it by a mere number. But division isn't the only operation that's commonly available only in approximate form. We don't expect square roots or trigonometry to be done symbolically; usually we settle for numerical approximations. Why should division be different?

While I'm complaining about rationals, I should mention a common practical problem: most languages with rationals print them as ratios, which can be quite inconvenient for humans to read. It's annoying to use a language's REPL as a calculator, and to discover that you have accidentally gotten an exact result, and must introduce some inexactness into the computation in order to be able to understand the result. (Frink can handle this nicely, by printing both the ratio and decimal forms, although for some reason this no longer works in the convenient online version.) This is a superficial UI problem, and really has nothing to do with rational arithmetic, but if it's not addressed — and it rarely is — it interferes with the utility of the language far more than mere rounding.

3 comments:

  1. O hai! The problem with the Frink web-based interface not showing approximations has been fixed.

    I've found that there are many, many cases where rational arithmetic is necessary to get a repeatable, reversible answer, especially as I'm turning Frink into not only a traditional programming language with imperative, fail-fast constructs, but also a system that can perform symbolic math, rearranging mathematical expressions for you, and lazily waiting for you to fill in the values of undefined variables. The two goals are mutually at odds, which makes this interesting research.

    When you use floating-point math, the result you get may be dependent on the order that you perform the operations in, which is ugly, especially for many cases of combinatorical problems, where you want lots of little fractions to cancel exactly. (I just solved one such problem on the Project Euler friendly programming contest last night.)

    With finite floating-point, you'll have other failures of representation (like not even being able to store the value 0.1 and get it back exactly!) This sort of floating-point error has led to famous disasters such as that of the Patriot missile batteries.

    When you're working with symbolic math, or units of measure, there is a huge, worlds-wide difference between x^2 and x^1.9999999999, and not using exact rational numbers leads to disaster. (Note that some systems of units like Gaussian units or Lorentz-Heaviside or many quantum calculations require exponents of units to be fractions, like meters^(3/2) kg^(1/2).

    You'll also note that (all?) successful symbolic math packages *do* tend to keep transcendental numbers such as sqrt[2] in that form, so calculations can be exactly reversed. (I still need to do this in Frink.)

    Here's a fun one for you. Have your language of choice calculate:

    x=77617
    y=33096
    ((333 + 3/4) - x^2) y^6 + x^2 (11x^2 y^2 - 121 y^4 - 2) + (5 + 1/2) y^8 + x/(2y)

    I'll bet it won't even get the *sign* right. The answer should be:

    -0.82739605994682136814

    Here's another more esoteric example. What is the cube root of -8? In other words, (-8)^(1/3) ?

    Well, that's interesting. -2 is a solution to this. But the answer can only be a real number iff the exponent is an exact rational number with an odd denominator! If you calculate (-8)^(0.3333333333) you'll get a complex number. This gets interesting.

    Having floating-point in your language is really nice and simply eliminates a large class of mathematical errors. It's not hard to implement, and should be more widespread in my opinion.

    ReplyDelete
  2. Thanks for fixing Frink's printing. As it happened, I noticed the fix an hour before I read the comment. :)

    I agree that exact arithmetic is valuable for algebra. What I'm arguing against is the idea that it's essential for correctness, and languages without exact representations for everything are broken.

    Okay, in a sense they are broken. But this breakage rarely matters except to certain mathematical programs. Most programs use only a small part of numeric space: small exact integers and, sometimes, inexact reals. So it's not unreasonable for a language to omit the rest. It's okay to ship a language with no ratios, no complexes, even no bignums. If the effort saved goes into the collections or I/O library or FFI instead, that's probably a win, because it's much more common for programs to run into language limitations in these areas than in numerics.

    ReplyDelete
  3. Chicken Scheme has a nice compromise: if you load the numbers egg, you get a full Scheme numeric tower; if not, you get fixnums and flonums, but fixnum operations overflow into flonums rather than producing garbage.

    Here's a classification of Scheme implementations along four orthogonal axes: whether exact numbers are closed under arithmetic operations other than division, whether they are closed under division, whether inexact numbers are provided, and whether complex numbers are provided. (A fifth axis is non-orthogonal: if complex numbers exist at all, do exact complex numbers exist? All Lisp standards are silent on this point.) A few implementations of other languages are mentioned, including several CLs, Elisp, ISLisp, and C.

    ReplyDelete

It's OK to comment on old posts.