Re: demonic problem descriptions

From: Cameron MacKinnon (cmackin+nn_at_clearspot.net)
Date: 02/09/05 

Date: Wed, 09 Feb 2005 14:56:30 -0500

Duane Rettig wrote:
> So why the apparent schizophrenia in an otherwise corretness-driven
> culture? Well, given that hardware floats exist and need to be
> supported (more on that later), I think that the biggest reason for
> this is surprisingly simple: computers and humans don't think in the
> same radix. Here's my logic:
>
> In your early schoolwork, when you are taught about the difference
> between three different kinds of fractions: normal rationals,
> repeating rationals, and irrationals, you are also given trivial ways
> to recognize them. Perhaps they are so trivial, that we don't even
> realize that we are using the techniques. I've seen several uses of
> the distinction between .1111 and .1111... in this thread, but I
> don't recall if anything has been explicitly said about their
> repeatability. [Note also that in higher education (sometimes
> introduced earlier) a distinction is made between .1111 and
> 1111/10000 in applied mathematics, where 1111/10000 is a precise
> number but .1111 is a number accurate to 4 decimal places; that is
> why you might also see the number .1100, which has the same value as
> .11 but a different precision]
>
> Now, a number that can't be represented in a computer will not be as
> accurate as one which can; it will instead be an approximation.

I submit that any number can be represented in a computer, in either n
bits per digit or a small amount of code. Further, it is trivial to say
that the numbers we've been talking about in this thread are represented
exactly in the computer -- in the input stream. It is only when they get
converted to our favourite FP format that they can no longer be exactly
represented. Sorry to be pedantic, but by using phrases like "a number
that can't be represented in a computer" you're suggesting to the
suggestible that this is an inherent property of computation with binary
machines, rather than one of our chosen format.

> So the candidates for ratio-ization are those which can be accurately
> represented - .5 could potentially be read and ratio-ized as 1/2 in
> "a Lisp that is not CL". So what's the problem? All we need to do
> is to read the numbers, and if they are non-repeating, simply make
> ratios out of them! But hang on; what about .1? It is indeed a
> non-repeating rational (or is it?):
>
> CL-USER(1): .1 0.1 CL-USER(2): :i * A NEW single-float = 0.1
> [#x3dcccccd] @ #x10632482 CL-USER(3):
>
> Why did .1 turn out to be a repeating rational instead of the
> obviously clear-cut rational 1/10? It is because our input is in
> base 10, and the representation within the computer is in binary,
> base 2, and sometimes a base-10 number that is not repeating will
> become repeating in binary. Therefore, it is no longer acccurate.

Here I must object to your use of the word "sometimes" as it drastically
understates the extent of the problem. Approximately EVERY base-10 float
that a user could write down repeats in base-2. Wade Humeniuk and others
did the math on this last December in a thread entitled "Floating-point
arithmetic in CL."

> Now, many of the hand-calculators of today do indeed read and store
> in rational format; they convert the digits read int BCD notation,
> and they do their calculations in BCD - essentially, they do not
> convert from one base to another, but do all their calculations in
> base 10. They pay a price; the calculations are slower than binary
> calculations, but this is not bothersome for calculators, since their
> operation is done within the limits of human data-entry time.

What about DBMSs? Don't they pay a price in order to accurately
calculate in BCD?

> It should be noted that financial institutions that are customers
> sometimes complain to us about the fact that conversions to binary
> and then back to decimal introduce roundoff errors in financial
> calculations, and they ask us for BCD support from the language. It
> would be a nice thing to provide...

Whenever some poor programmer makes the mistake of using FP for currency
calculations, there's a Greek chorus of grizzled hackers singing that he
should have known better. But people keep doing it -- it's natural
behaviour. How many million transactions per day do you suppose are
handled with floating point software that gets the pennies wrong when
the numbers exceed a certain size? It's all buggy software, and a
misapplication of FP, but it is a common trap. Every day, somewhere,
more code with this bug goes into production.

> And finally, the question of why we (Lisp) must support
> floating-point hardware is answered in one word: speed. Not the
> kind of speed gain that you might get from eliminating the
> fixnum-to-bignum overflow test, but the thousandsfold increases that
> occur when ffts and simple logarithms are done; the speed-vs-accuracy
> tradeoff is much easier to judge when your lisp program is still
> crunching some signal-processing calculations when the C code has
> been done hours ago.

I don't think anyone is suggesting that Lisp stop supporting binary
floating point hardware. In fact, I'd argue that the standard should be
updated to BETTER support modern FP hardware - at least to expose to the
programmer all of the IEEE behaviour that the CPU does.

FFT? Please. That's another large group of FP programmers who have left
the scene. Today, if you need really fast FFT you buy a $10 chip from
Texas Instruments. If you need fast FFTs on general purpose hardware you
FFI to the Fastest Fourier Transform in the West. [Aside: FFTW
was a real eye opener for me when I was a C drone. What the heck was
Objective Caml, and who used it for high performance numerics? Could it
be that there were smarter languages for smarter programmers?]

Most programmers and most programs need reliable decimal numeric
manipulation more than they need fast approximate binary answers. The
ones who DO need approximate answers usually need more error interval
analysis than they've bothered doing (i.e. their programs may or may not
be buggy). The percentage of floating point code out there which isn't
broken now but might break if the default input format were to change
(i.e. was coded competently for binary FP) is very, very small.

Binary FP is really good at what it is good at. But since most
programmers don't understand it, most extant code that uses it is buggy
(or works by accident rather than design). Many of the people who have
needed speed the most have moved to special purpose hardware (3D
Graphics Processing Units, floating point DSPs). So why should it
continue to be the default format for programming general purpose CPUs?
We know from experience that as long as it is, ignorance about its
stunningly unintuitive properties will continue to be the cause of a
good fraction of the most insidious bugs known to programmers.

Relevant Pages

  • Re: status of quadruple precision arithmetic in g95 and gfortran?
    ... right now, g95 doesn't support real*16, but does support real*10 on the ... course that if the hardware doesn't support real*16 it is not only very ... implement all operations required for real*16 calculations. ...
    (comp.lang.fortran)
  • Re: !p+, and thank you Jeff
    ... traditional Forth programmers, ... It is why our hardware can be simpler and our software can ... It was fun trying to write small and fast ... ANS Forth looks the way it does is because of Pentium ...
    (comp.lang.forth)
  • Re: Sound after upgrade to 11.1
    ... And many people have no problem with sound -- whereas ... I've been using SUSE since 7.0 and have heard the same complaints at ... to strenuously test their OS on *every possible combination of hardware ... There are thousands of programmers working on the kernel and all the ...
    (alt.os.linux.suse)
  • Re: Sound after upgrade to 11.1
    ... I've been using SUSE since 7.0 and have heard the same complaints at ... of hardware available*. ... There are thousands of programmers working on the kernel and all the ... Linux is *still* a largely volunteer environment. ...
    (alt.os.linux.suse)
  • Re: Programming "efficiently" on given hardware - what does it mean really?
    ... I think it just means that instead of judging efficiency in relation ... > than Win3.1 did on way primative hardware. ... the general virtue of energy conservation later. ... You don't hear programmers lament about the 'bloat' they have to add ...
    (comp.programming)